64
правки
Изменения
Нет описания правки
Как было замечено выше, ответ на задачу равен количеству шестизначных билетов с суммой <tex>27</tex>. Рассмотрим расстановки целых неотрицательных чисел на шести позициях, дающих в сумме 27; обозначим их множество <tex>A</tex>. Выделим шесть множеств <tex>C_i, i = 1 \ldots 6</tex>, где <tex>i</tex>-е множество состоит из расстановок, у которых в i-й позиции стоит число, не меньшее 10. Число счастливых билетов равно числу расстановок, не принадлежащих ни одному из множеств. Посмотрим на расстановку n чисел с суммой k как на сочетание с повторениями из n по k, число означает количество повторений элемента, значит количество расстановок равно <tex>\binom{n+k-1}{n-1}</tex>. Число <tex>\left\vert{A}\right\vert</tex> всех расстановок неотрицательных целых чисел с суммой 27 в шесть позиций равно <tex>\binom{32}{5}</tex> Число расстановок <tex>\left\vert{C_i}\right\vert</tex> одинаково для всех i и равно <tex>\binom{22}{5}</tex>. В самом деле, мы можем поставить в i-ю позицию число 10, а оставшуюся сумму 17 произвольно распределить по шести позициям. Аналогично, число расстановок <tex>\left\vert{C_i \cap C_j}\right\vert</tex> одинаково для любой пары <tex>i, j, i \neq j</tex> и равно <tex>\binom{12}{5}</tex>: мы выбираем две позиции и ставим в них 10 и произвольно распределяем оставшуюся сумму 7 по шести позициям. Таким образом, искомое количество расстановок равно <tex>\left\vert{A}\right\vert - \binom{6}{1}\left\vert{C_i}\right\vert+\binom{6}{2}\left\vert{C_i \cap C_j}\right\vert = \binom{32}{5}-6\binom{22}{5}+15\binom{12}{5} = 55252</tex>
== Решение путем интегрирования ==
Рассмотрим многочлен Лорана (т.е. многочлен, в котором допускаются отрицательные степени) <tex>H(z)=G^3(z)G^3(1/z)</tex>. Заметим, что его свободный член равен <tex>\sum_{i=0}^{27}[z^i]G^3(z)\cdot [z^{-i}]G^3(z^{-1})=\sum_{i=0}^{27}(D_3^i)^2</tex>. Воспользуемся теоремой Коши <ref>[https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D0%B3%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%9A%D0%BE%D1%88%D0%B8 Интегральная формула Коши — Википедия]
</ref> из комплексного анализа:
{{Теорема
|id=th1
|author=Коши
|statement=Для любого многочлена Лорана p(z) его свободный член p_0 равен
: <tex>p_0=\dfrac{1}{2\pi i}{\displaystyle \int} \dfrac{p(z)}{z} dz</tex>, где интегрирование происходит по любой окружности, ориентированной против часовой стрелки и содержащей внутри себя начало координат.
}}
Упростим многочлен <tex>H</tex>:
: <tex>H(z)=\left( \dfrac{1-z^{10}}{1-z} \right) ^3\left(\dfrac{1-z^{-10}}{1-z^{-1}}\right)^3=\left(\dfrac{2-z^{10}-z^{-10}}{2-z-z^{-1}}\right)^3</tex> и применим замену <tex>z=e^{i\phi}</tex>:
: <tex>p_0=\dfrac{1}{2\pi}\displaystyle\int_0^{2\pi}\left(\dfrac{2-e^{10i\phi}-e^{-10i\phi}}{2-e^{i\phi}-e^{-i\phi}}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int_0^{2\pi}\left(\dfrac{2-2\cos(10\phi)}{2-2cos\phi}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int_{0}^{2\pi}\left(\dfrac{\sin^2(5\phi)}{\sin^2(\frac{\phi}{2})}\right)^3d\phi=\dfrac{1}{\pi}\displaystyle\int_0^{\pi}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi=\dfrac{1}{\pi}\displaystyle\int_{-\pi/2}^{\pi/2}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi</tex>
Рассмотрим функцию <tex>f(\phi)=\dfrac{\sin(10\phi)}{\sin\phi}</tex> на <tex>[-\pi/2,\pi/2]</tex>. Вне отрезка <tex>[-\pi/10,\pi/10]
f(\phi) \leqslant \dfrac{1}{\sin\frac{\pi}{10}}\approx 3</tex>, значит интеграл по этой части не больше <tex>\pi3^6 \approx 2100</tex>, основная часть сосредоточена на <tex>[-\pi/10,\pi/10]</tex>. Оценим интеграл по промежутку с помощью метода стационарной фазы.
== См. также ==
* [[Динамическое программирование]]
== Примечания ==
<references />
