Задача о счастливых билетах — различия между версиями
Rgolchin (обсуждение | вклад) |
Rgolchin (обсуждение | вклад) |
||
Строка 32: | Строка 32: | ||
Рассмотрим функцию <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] | Рассмотрим функцию <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 2100</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> Этот метод позволяет оценить значение интеграла | f(\phi) \leqslant \dfrac{1}{\sin\frac{\pi}{10}}\approx 3</tex>, значит интеграл по этой части не больше <tex>3^6\pi \approx 2100</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>). Вблизи 0 <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}}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>. | : <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>. | ||
Полагая <tex>t=6</tex> и вспоминая выражение для <tex>p_0</tex>, получаем приближенное равенство: | Полагая <tex>t=6</tex> и вспоминая выражение для <tex>p_0</tex>, получаем приближенное равенство: | ||
Строка 42: | Строка 42: | ||
|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> | |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>. Рассмотрим внутреннюю сумму: | |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>) | + | <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}}}=0</tex> (можем воспользоваться формулой для суммы геометрической прогрессии, т.к. ее знаменатель не равен <tex>1</tex>: <tex>N>j \implies e^{\frac{2ij\pi}{N}}\neq 1, e^{-\frac{2ij\pi}{N}}\neq 1</tex>) |
}} | }} | ||
Версия 13:06, 11 июня 2017
Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например,
. Известно, что количество счастливых билетов из шести цифр равно .Задача: |
Для натурального | найти количество -значных счастливых билетов .
Содержание
Метод динамического программирования
Обозначим количество
-значных чисел с суммой как (число может содержать ведущие нули). -значный счастливый билет состоит из двух частей: левой ( цифр) и правой (тоже цифр), причём в обеих частях сумма цифр одинакова. Зафиксируем -значное число с суммой в левой части (это можно сделать способами), для него будет существовать возможных вариантов числа в правой части, следовательно количество счастливых билетов с суммой в одной из частей равно . Значит общее число билетов равно . Верхний индекс суммирования равен , так как максимальная сумма цифр в одной части билета равна . Также можно сопоставить счастливому билету -значное число с суммой : , причем это соответствие взаимно-однозначно, поэтому . Осталось научиться вычислять . Положим . При количество -значных чисел с суммой цифр можно выразить через количество -значных чисел, добавляя к ним -ю цифру, которая может быть равна : .Метод производящей функции
Выпишем производящую функцию
, коэффициент при у которой будет равен : Действительно, однозначное число с суммой цифр (для ) можно представить одним способом. Для — ноль способов. Заметим, что — производящая функция для чисел , поскольку коэффициент при получается перебором всех возможных комбинаций из цифр, равных в сумме . Ответом на задачу будет . Перепишем производящую функцию в ином виде: и получим, что . Так как , , что при дает .Решение с помощью формулы включения-исключения [1]
Как было замечено выше, ответ на задачу равен количеству шестизначных билетов с суммой [2] из по , в котором -й элемент повторяется раз. Так как это сопоставление взаимно-однозначно, количество расстановок равно количеству сочетаний с повторениями, т.е. . Число всех расстановок неотрицательных целых чисел с суммой в шесть позиций равно Число расстановок одинаково для всех и равно . В самом деле, мы можем поставить в -ю позицию число , а оставшуюся сумму произвольно распределить по шести позициям. Аналогично, число расстановок одинаково для любой пары и равно : мы выбираем две позиции и ставим в них и произвольно распределяем оставшуюся сумму по шести позициям. Таким образом, искомое количество расстановок равно
. Рассмотрим расстановки целых неотрицательных чисел на шести позициях, дающих в сумме ; обозначим их множество . Выделим шесть множеств , где -е множество состоит из расстановок, у которых в -й позиции стоит число, не меньшее . Число счастливых билетов равно числу расстановок, не принадлежащих ни одному из множеств. Расстановке из чисел с суммой сопоставим сочетание с повторениямиРешение путем интегрирования
Рассмотрим многочлен Лорана (т.е. многочлен, в котором допускаются отрицательные степени) [3] из комплексного анализа:
. Заметим, что его свободный член равен . Воспользуемся теоремой КошиТеорема (Коши): |
Для любого многочлена Лорана его свободный член равен
|
Упростим многочлен
:- и применим замену :
Рассмотрим функцию [4] Этот метод позволяет оценить значение интеграла
на . Вне отрезка , значит интеграл по этой части не больше , основная часть сосредоточена на . Оценим интеграл по этому промежутку с помощью метода стационарной фазы.- . При значение интеграла определяется поведением его фазы, т.е. , в окрестности стационарной точки (точки, где , или, что то же самое, ). Вблизи , а . При больших получим
- [5]. Заметим, что при , поэтому интеграл примерно равен . , где — функция ошибок
Полагая
и вспоминая выражение для , получаем приближенное равенство:Полученный результат с хорошей точностью (отклонение составляет не более
) приближает искомое значение.Способ с конечной суммой
Рассмотрим функцию
. Как доказано в предыдущем разделе, . Для интеграла можно выписать приближенную формулу . Интересно, что при достаточно большом это равенство становится точным.Утверждение: |
При и любом |
, где — коэффициенты многочлена . . Тогда искомая сумма равна . Рассмотрим внутреннюю сумму: (можем воспользоваться формулой для суммы геометрической прогрессии, т.к. ее знаменатель не равен : ) |
См. также
Примечания
Источники информации
- Ландо С. К., Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144с. ISBN 978-5-94057-042-4