64
правки
Изменения
Нет описания правки
__TOC__
== Общие идеи ==
Обозначим количество <tex>n</tex>-значных чисел с суммой <tex>k</tex> как <tex>D_n^k</tex> (число может содержать ведущие нули). <tex>2n</tex>-значный счастливый билет состоит из двух частей: левой (<tex>n</tex> цифр) и правой (тоже <tex>n</tex> цифр), причём в обеих частях сумма цифр одинакова. Зафиксируем <tex>2nx</tex> {{---}} <tex>n</tex>-значное число с суммой <tex>k</tex> в левой части (всего таких чисел <tex>D_n^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>2n</tex>-значных чисел с суммой <tex>9n</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>D_{2n}^{9n}</tex>, алгоритм будет работать за <tex>O(n^2)</tex>.
Действительно, однозначное число с суммой цифр <tex>k</tex> (для <tex>k=0,\ldots,9</tex>) можно представить одним способом. Для <tex>k>9</tex> — ноль способов. Заметим, что <tex>G^n(z)</tex> — производящая функция для чисел <tex>D_n^k</tex>, поскольку коэффициент при <tex>z^k</tex> получается перебором всех возможных комбинаций из <tex>n</tex> цифр, равных в сумме <tex>k</tex>. Ответом на задачу будет <tex>[z^{9n}]G^{2n}(z)</tex>. Перепишем производящую функцию в ином виде: <tex>
G(z) = 1+z+\ldots+z^9 = \dfrac{1-z^{10}}{1-z}
</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>{\displaystyle [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>f(\phi)=\dfrac{\sin(10\phi)}{\sin\phi}</tex> на <tex>\left[-\dfrac{\pi}{2},\dfrac{\pi}{2}\right]</tex>. Вне отрезка <tex>\left[\dfrac{-\pi}{10},\dfrac{\pi}{10}\right]
f(\phi) \leqslant \dfrac{1}{\sin\frac{\pi}{10}}\approx 3</tex>, значит интеграл по этой части не больше <tex>3^6\pi \approx 21002300</tex>, основная часть сосредоточена на <tex>\left[-\dfrac{\pi}{10},\dfrac{\pi}{10}\right]</tex>. Оценим интеграл по этому промежутку с помощью метода стационарной фазы. <ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%81%D1%82%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B9_%D1%84%D0%B0%D0%B7%D1%8B Метод стационарной фазы — Википедия]</ref> Этот метод позволяет оценить значение интеграла
: <tex>\displaystyle\int_{-\frac{\pi}{10}}^{\frac{\pi}{10}}f^td\phi=\displaystyle\int_{-\frac{\pi}{10}}^{\frac{\pi}{10}}e^{t\ln{f}}d\phi</tex>. При <tex>t \rightarrow \infty</tex> значение интеграла определяется поведением его фазы, т.е. <tex>\ln{f}</tex>, в окрестности стационарной точки <tex>0</tex> (точки, где <tex>(\ln{f})'=0</tex>, или, что то же самое, <tex>f'=0</tex>). Вблизи <tex>0</tex> <tex>f(\phi) \approx 10 (1 - \frac{33}{2}\phi^2)</tex>, а <tex>\ln{f}(\phi) \approx \ln 10 - \frac{33}{2}\phi^2</tex>. При больших <tex>t </tex> получим
: <tex>\displaystyle\int_{-\frac{\pi}{10}}^{\frac{\pi}{10}}e^{t(\ln 10 - \frac{33}{2}\phi^2)}d\phi=10^t \displaystyle\int_{-\frac{\pi}{10}}^{\frac{\pi}{10}}e^{-\frac{33}{2}\phi^2}d\phi=\sqrt{\dfrac{\pi}{66t}}erf\left(\sqrt{\dfrac{33t}{2}\phi}\right)\bigg\rvert_{-\frac{\pi}{10}}^{\frac{\pi}{10}}</tex>, где <tex>erf(z)</tex> {{---}} функция ошибок <ref>[http://mathworld.wolfram.com/Erf.html Erf -- from Wolfram MathWorld]</ref>. Заметим, что при <tex>z > 2 </tex> <tex>erf(z) \approx 1</tex>, поэтому интеграл примерно равен <tex>10^t \sqrt{\dfrac{2\pi}{33t}}</tex>.
