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> и получим, что <tex>G^{2n}(z)=(1-z^{10})^{2n}(1-z)^{-2n}=\sum\limits_{k=0}^{2n}\binom{2n}{k}(-z^{10})^k\sum\limits_{j=0}^{\infty}\binom{-2n}{j}(-z)^k</tex>. Так как <tex>\binom{-2n}{k}=(-1)^k\binom{2n+k-1}{k}</tex>, <tex>[z^{9n}]G^{2n}(z)=\sum\limits_{j=0}^{\lfloor{\frac{9n}{10}}\rfloor}(-1)^j\binom{2n}{j}\binom{11n-10j-1}{9n-10j}</tex>, что при <tex>n=3</tex> дает <tex>\binom{6}{0}\binom{32}{27}-\binom{6}{1}\binom{22}{17}+\binom{6}{2}\binom{12}{7}=55252</tex>.
== Решение с помощью формулы включения-исключения <ref>[http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%B2%D0%BA%D0%BB%D1%8E%D1%87%D0%B5%D0%BD%D0%B8%D1%8F-%D0%B8%D1%81%D0%BA%D0%BB%D1%8E%D1%87%D0%B5%D0%BD%D0%B8%D1%8F Формула включения-исключения — Викиконспекты]</ref>==
Как было замечено вышемы заметили раньше, ответ на задачу равен количеству шестизначных билетов с суммой <tex>27</tex>. Рассмотрим расстановки целых неотрицательных чисел на шести позициях, дающих в сумме <tex>27</tex>; обозначим их множество <tex>A</tex>. Выделим шесть множеств его подмножеств <tex>C_i, i = 1 \ldots 6</tex>, где <tex>i</tex>-е множество состоит из расстановок, у которых в <tex>i</tex>-й позиции стоит число, не меньшее <tex>10</tex>. Число счастливых билетов равно числу расстановок, не принадлежащих ни одному из множеств. Расстановке <tex>(a_1,a_2 \ldots a_n)</tex> из <tex>n</tex> чисел с суммой <tex>k</tex> сопоставим сочетание с повторениями <ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5#.D0.A1.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D1.8F_.D1.81_.D0.BF.D0.BE.D0.B2.D1.82.D0.BE.D1.80.D0.B5.D0.BD.D0.B8.D1.8F.D0.BC.D0.B8 Сочетание — Википедия]</ref> из <tex>n</tex> по <tex>k</tex>, в котором <tex>i</tex>-й элемент повторяется <tex>a_i</tex> раз. Так как это сопоставление взаимно-однозначно, количество расстановок равно количеству сочетаний с повторениями, т.е. <tex>\binom{n+k-1}{n-1}</tex>. Число <tex>\left\vert{A}\right\vert</tex> всех расстановок неотрицательных целых чисел с суммой <tex>27</tex> в шесть позиций равно <tex>\binom{32}{5}</tex> . Число расстановок <tex>\left\vert{C_i}\right\vert</tex> одинаково для всех <tex>i</tex> и равно <tex>\binom{22}{5}</tex>. В самом деле, мы можем поставить в <tex>i</tex>-ю позицию число <tex>10</tex>, а оставшуюся сумму <tex>17</tex> произвольно распределить по шести позициям. Аналогично, число расстановок <tex>\left\vert{C_i \cap C_j}\right\vert</tex> одинаково для любой пары <tex>i, j, i \neq j</tex> и равно <tex>\binom{12}{5}</tex>: мы выбираем две позиции и ставим в них <tex>10</tex> и произвольно распределяем оставшуюся сумму <tex>7</tex> по шести позициям. Таким образом, искомое количество расстановок равно <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\limits_{i=0}^{27}[z^i]G^3(z)\cdot [z^{-i}]G^3(z^{-1})=\sum\limits_{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 Интегральная формула Коши — Википедия]
: <tex>p_0=\dfrac{1}{2\pi i}{\displaystyle \int} \dfrac{p(z)}{z} dz</tex>, где интегрирование происходит по любой окружности, ориентированной против часовой стрелки и содержащей внутри себя начало координат.
}}
Упростим многочлен <tex>H(z)</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_{-\frac{\pi}{2}}^{\frac{\pi}{2}}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi</tex>
Полагая <tex>t=6</tex> и вспоминая выражение для <tex>p_0</tex>, получаем приближенное равенство:
: <tex>p_0 \approx \dfrac{10^6}{3\sqrt{11\pi}} \approx 56700</tex>
== Способ с конечной суммой ==
Рассмотрим функцию <tex>g(\phi)=H(e^{i\phi})=\left(\dfrac{\sin{5\phi}}{\sin{\frac{\pi}{2}}}\right)^6</tex>. Как доказано в предыдущем разделевыше, <tex>L_nL_6=\dfrac{1}{2\pi}\displaystyle\int_0^{2\pi}g(\phi)d\phi</tex>. Для интеграла можно выписать приближенную формулу и получить <tex>L_n L_6 \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 L_6 = \dfrac{1}{N}\sum\limits_0limits_{k=0}^{N-1}g(\phi_k)</tex>, где <tex>\phi_k=\phi_0+\dfrac{2\pi k}{N}), k > 0</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(z)</tex>. Обозначим <tex>gr(\phi)=a_0+\sum\limits_{j=1}^{27}a_j(e^{ij\phi}+e^{-ij\phi}), g(\phi)=a_0+r(\phi)</tex>. Тогда искомая сумма равна Докажем, что <tex>\dfracsum\limits_{1k=0}^{N-1}g(\phi_k)=0</tex>. Раскроем <tex>g(\phi_k)</tex>:<tex>\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}})=\sum\limits_{k=0}^{N-1}e^{\frac{2ijk\pi}{N}}+\sum\limits_{k=0}^{N-1}e^{-\frac{2ijk\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>. Значит искомая сумма равна <tex>\dfrac{1-e^{2ij\pi}}{1-e^{\frac{2ij\pi}{N}}}+\dfrac{1-e^{-2ij\pi}}{1-e^{-\frac{2ij\pi}{N}}}=0</tex> (можем воспользоваться формулой для суммы геометрической прогрессии, т.к. ее знаменатель не равен так как <tex>e^{2\pi i}=1</tex>: .Таким образом, <tex>\dfrac{1}{N>j }\sum\implies elimits_{k=0}^{N-1}g(\fracphi_k)=\dfrac{2ij\pi1}{N}}\neq 1, e^{-sum\fraclimits_{2ij\pik=0}^{N-1}}(a_0+g(\neq 1phi_k))=a_0</tex>, а свободный член <tex>H(z)</tex> равен <tex>L_6</tex>, как известно из предыдущего раздела.
}}
