news.shamcode.ru | Задача про счастливые билетики и ТФКП

Здравствуйте, друзья!

Сегодня рассмотрим бородатую задачку про "счастливые" билетики. Наверняка опытные искатели интересных задач уже сталкивались с ней. Но хоть эта задача и не нова, она всё равно вызывает интерес, так как решить её можно бесчисленным количеством способов. Сейчас мы рассмотрим один из самых простых, но в то же время интересных путей её решения, по моему мнению. А именно — через теорию функций комплексного переменного.

Этот билет не счастливый, но в следующий раз вам точно повезет!

Постановка задачи

Представьте, что у вас есть билет на автобус с шестизначным номером. Если сумма первых трёх цифр совпадает с суммой трёх последних, билет считается «счастливым». С какой вероятностью вам выпадет такой билет?

Теперь давайте переформулируем её на языке математики.

Запишем номер билета как:

где каждый номер может принимать 10 значений: от 0 до 9.

Тогда условие на «счастливый» билетик, будет выглядеть следующим образом:

Решаем задачу

Теперь посчитаем, сколько всего таких билетиков существует. Очевидно, что каждая цифра может принимать 10 значений, а значит, число всевозможных билетиков:

$N = \sum_{n_1=0}^9\sum_{n_2=0}^9\sum_{n_3=0}^9\sum_{n_4=0}^9\sum_{n_5=0}^9\sum_{n_6=0}^9= 10^6$

И наконец, переходим к самому сложному этапу: нам необходимо посчитать число всех «счастливых» билетиков. Для этого воспользуемся символом Кронекера, который будет учитывать наше условие:

$M=\sum_{[n_i]=0}^9 \delta_{n_1+n_2+n_3,n_4+n_5+n_6}$

Эта сумма пробегает по каждому номеру и учитывает все возможные перестановки.

В игру входит ТФКП

А теперь применим интегральное представление символа Кронекера:

$\delta_m^n=\frac{1}{2\pi i} \oint \frac{dz}{z^{m-n+1}}$

Давайте, чтобы все было честно, докажем это тождество. Тут-то нам и понадобятся знания ТФКП! Ведь этот интеграл мало того, что содержит мнимое число, так еще и содержит в себе особую точку в нуле. Эта точка является полюсом m ‑ n + 1 порядка, из теории вычетов мы знаем как вычисляется вычет в полюсе n‑го порядка в нуле:

$Resf(z) = \frac{1}{(n-1)!}\displaystyle \lim_{ z\to 0}\frac{\mathrm{d}^{n-1} }{\mathrm{d} z^{n-1}}(f(z)z^n)$

Подставим нашу функцию:

$Res(\frac{1}{z^{m-n-1}}) = \frac{1}{(n-m)!}\displaystyle \lim_{ z\to 0}\frac{\mathrm{d}^{n-m} }{\mathrm{d} z^{n-m}}(1) = \delta_{nm}$

Таким образом мы доказали интегральное представление дельта‑символа.

Напишем, с учетом этого выражения чему равняется наше искомое число «счастливых» билетиков:

$M = \frac{1}{2 \pi i}\oint \frac{dz}{z}\sum_{[n_i]=0}^{9}z^{-n_1-n_2-n_3+n_4+n_5+n_6}$

Теперь можно разделить суммы и заметить, что индексы не зависят от друг друга:

$M = \frac{1}{2 \pi i}\oint \frac{dz}{z}\sum_{n_1=0}^{9}z^{-n_1}\cdots \sum_{n_6=0}^{9}z^{n_6} = \frac{1}{2 \pi i}\oint \frac{dz}{z}(\sum_{n=0}^{9}z^{-n})^3(\sum_{n=0}^{9}z^{n})^3$

Как видно две суммы представляют собой геометрические прогрессии, тогда:

$M = \frac{1}{2 \pi i}\oint \frac{dz}{z}\left ( \frac{1-\frac{1}{z^{10}}}{1-\frac{1}{z}} \right )^3 \left ( \frac{1-z^{10}}{1-z} \right )^3 = \frac{1}{2 \pi i}\oint \frac{dz}{z^{28}}\left ( \frac{1-z^{10}}{1-z} \right )^6$

Для вычисления этого интеграла нам необходимо найти коэффициент в ряду Лорана при минус первой степени. Чтобы это сделать давайте вспомним:

$\frac{1}{1-z}= \sum_{n=0}^{\infty}z^n$

Теперь для разложения исходной функции нам достаточно заметить что она является шестой производной данной функции.

$\frac{1}{(1-z)^2}=\frac{\mathrm{d} }{\mathrm{d} z}\left ( \frac{1}{1-z} \right )= \frac{\mathrm{d} }{\mathrm{d} z}\sum_{n=0}^{\infty}z^n =\sum_{n=0}^{\infty}(n+1)z^n$

Продолжая дифференцировать, получим:

$\frac{1}{(1-z)^6}=\frac{1}{120}\sum_{n=0}^{\infty}(n+1)(n+2)(n+3)(n+4)(n+5)z^n$

Вторая функция раскладывается элементарно:

$(1-z^{10})^6 = 1 - 6z^{10} + 15z^{20} - 20 z^{30} + 15z^{40} - 6z^{50} +z^{60}$

Остается только собрать коэффициенты минус первой степени,

им соответствуют n = 27,17 и 7. Дальше подставляем эти номера в наше выражение и считаем на калькуляторе, чтобы не ошибиться.

$M = C_{-1} = \frac{1}{120}(24165120 - 6*3160080 + 15*95040) = 55252$

Ну и наконец, найдем вероятность выпадения нашего билета:

$P = \frac{M}{N}\approx 0,055$

Поздравляю! Мы только что решили задачу.

Этот подход не только элегантен, но и демонстрирует мощь аналитических методов в дискретной математике. Надеюсь, вам было интересно и вы узнали что‑то новое!