64
правки
Изменения
Нет описания правки
}}
__TOC__
== Решение с помощью Метод динамического программирования ==
Обозначим количество <tex>n</tex>-значных чисел с суммой <tex>k</tex> как <tex>D_n^k</tex> (число может содержать ведущие нули). <tex>2n</tex>-значный счастливый билет состоит из двух частей: левой (<tex>n</tex> цифр) и правой (тоже <tex>n</tex> цифр), причём в обеих частях сумма цифр одинакова. Зафиксируем <tex>2n</tex>-значное число с суммой <tex>k</tex> в левой части (это можно сделать <tex>D_n^k</tex> способами), для него будет существовать <tex>D_n^k</tex> возможных вариантов числа в правой части, следовательно количество счастливых билетов с суммой <tex>k</tex> в одной из частей равно <tex>(D_n^k)^2</tex>. Значит общее число билетов равно <tex>L_n = \sum\limits_{k=0}^{9n} (D_{n}^{k})^2</tex>. Верхний индекс суммирования равен <tex>9n</tex>, так как максимальная сумма цифр в одной части билета равна <tex>9n</tex>. Также можно сопоставить счастливому билету <tex>a_1a_2\ldots a_n b_1b_2 \ldots b_n</tex> <tex>2n</tex>-значное число с суммой <tex>9n</tex>: <tex>a_1a_2\ldots a_n (9-b_1)(9-b_2) \ldots (9-b_n)</tex>, причем это соответствие взаимно-однозначно, поэтому <tex>L_n=D_{2n}^{9n}</tex>.
Осталось научиться вычислять <tex>D_n^k</tex>. Положим <tex>D_0^k=\begin{cases}1,&k=0\\0,&k>0\end{cases}</tex>. При <tex>n>0</tex> количество <tex>n</tex>-значных чисел с суммой цифр <tex>k</tex> можно выразить через количество <tex>(n-1)</tex>-значных чисел, добавляя к ним <tex>n</tex>-ю цифру, которая может быть равна <tex>0, 1, \ldots, 9</tex>: <tex>D_n^k=\sum\limits_{j=0}^{9}D_{n-1}^{k-j}</tex>.
== Решение с помощью Метод производящей функции ==
Выпишем производящую функцию <tex>G(z)</tex>, коэффициент при <tex>z^k</tex> у которой будет равен <tex>D_1^k</tex>:
<tex>
: <tex>p_0 \approx \dfrac{10^6}{3\sqrt{11\pi}} \approx 56700</tex>
Полученный результат с хорошей точностью (отклонение составляет не более <tex>3\%</tex>) приближает искомое значение.
== Способ с конечной суммой ==
Рассмотрим функцию <tex>g(\phi)=\left(\dfrac{\sin{5\phi}}{\sin{\frac{\pi}{2}}}\right)^6</tex>. Как доказано в предыдущем разделе, <tex>L_n=\dfrac{1}{2\pi}\displaystyle\int_0^{2\pi}g(\phi)d\phi</tex>. Для интеграла можно выписать приближенную формулу <tex>L_n \approx \dfrac{1}{N}\sum\limits_{k=0}^{N-1}g(\dfrac{2\pi k}{N})</tex>. Интересно, что при достаточно большом <tex>N</tex> это равенство становится точным.
{{Утверждение
|statement=При <tex>N \geqslant 28</tex> и любом <tex>\phi_0</tex> <tex>L_n = \dfrac{1}{N}\sum\limits_0^{N-1}g(\phi_0+\dfrac{2\pi k}{N})</tex>
|proof=<tex>g(\phi)=H(e^{i\phi})=\sum\limits_{j=-27}^{27}a_je^{ij\phi}</tex>, где <tex>a_j</tex> {{---}} коэффициенты многочлена <tex>H</tex>. <tex>g(\phi)=a_0+\sum\limits_{j=1}^{27}a_j(e^{ij\phi}+e^{-ij\phi})</tex>. Тогда искомая сумма равна <tex>\dfrac{1}{N}\sum\limits_{k=0}^{N-1}\sum\limits_{j=1}^{27}a_j(e^{ij(\phi_0+\frac{2\pi k}{N}} + e^{-ij(\phi_0+\frac{2\pi k}{N} )})= \dfrac{1}{N}e^{ij\phi_0}\sum\limits_{j=1}^{27}a_j\sum\limits_{k=0}^{N-1}(e^{ij\frac{2\pi k}{N}} + e^{-ij\frac{2\pi k}{N} })</tex>. Рассмотрим внутреннюю сумму:
<tex>\sum\limits_{k=0}^{N-1}(e^{\frac{2ijk\pi}{N}}+e^{-\frac{2ijk\pi}{N}})=\dfrac{1-e^{2ij\pi}}{1-e^{\frac{2ij\pi}{N}}}+\dfrac{1-e^{-2ij\pi}}{1-e^{-\frac{2ij\pi}{N}}}</tex> (можем воспользоваться формулой для суммы геометрической прогрессии, т.к. ее знаменатель не равен <tex>1</tex>: <tex>N>j \implies e^{\frac{2ij\pi}{N}}\neq 1, e^{-\frac{2ij\pi}{N}}\neq 1</tex>)
}}
== См. также ==
* [[Производящая функция]]
