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

в 6:09, , рубрики: билеты, счастливые билеты, счастье, ТФКП

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

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

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

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

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

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

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

n_1n_2n_3n_4n_5n_6

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

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

n_1+n_2+n_3=n_4+n_5+n_6

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

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

N=sum_{n_1=0}^9sum_{n_2=0}^9sum_{n_3=0}^9sum_{n_4=0}^9sum_{n_5=0}^9sum_{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}{2pi i} oint frac{dz}{z^{m-n+1}}

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

Resf(z)=frac{1}{(n-1)!}displaystyle lim_{ zto 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_{ zto 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

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

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

Автор: LeonidBad

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js