Решение задачи от Таксы Дуси

Условие задачи можно посмотреть тут. Довольно неожиданно, но задача оказывается не задачей по комбинаторике, а задачей про многочлены! Потому Такса Дуся любит не только теорию вероятностей, но и алгебру 🔥

Давайте начнем с того, что изучим ситуацию, когда у нас есть два кубика. Пусть вероятность выпадания числа n на первом кубике равна a_n, а на втором — b_n. Какова вероятность того, что при броске двух кубиков в итоге выпадет число m?

Выпадение числа m это событие, когда на первом кубике выпало некоторое число n, а на втором — число k = m - n (и оба этих числа от 1 до 6). Вероятность этого события равна a_n * b_k, тогда итоговая вероятность выпадания m это sum a_n * b_k по всем n + k = m.

Ничего не напоминает? Это в точности правило умножение многочленов! А именно, рассмотрим многочлены P(x) =
sum a_i * x^i и Q(x) = sum b_i x^i по i от 1 до 6. Теперь рассмотрим многочлен S(x) = P(x)Q(x). Коэффициент при степени m этого многочлена это в точности sum a_n * b_k по всем n + k = m

Такое же правило работает, когда кубиков много: чтобы понять распределение чисел, которые выпадают при броске 20 кубиков, нужно для каждого кубика построить его многочлен, перемножить все многочлены, и его коэффициенты как раз и будут искомыми вероятностями.

В нашем случае, мы должны получить многочлен 1/101( x^20 + x^21 + … + x^120), перемножив 20 многочленов, каждый из которых делится на x. Сократим все на x^20 и для удобства умножим все на 101. Теперь 1 + x^2+ … + x^101 равен произведению 20 полиномов пятой степени.

У полинома пятой степени есть вещественный корень, а вот у 1 + x^2+ … + x^100 такого корня быть не может, так как это суммируется по формуле геометрической прогрессии как (x^101 - 1) / (x - 1), а числитель и знаменатель одного знака, поскольку x и x^101 одновременно больше или меньше 1. Противоречие: одна часть уравнения обращается в ноль при некотором x, а вторая всегда положительна.

Задача на дом: подумайте, как обобщить это рассуждение на любое количество кубиков > 1. Таким образом, на самом деле нельзя никаким количеством неправильных кубиков сгенерировать равновероятное распределение чисел, что интуитивно совсем не очевидно!