Изменения

Перейти к: навигация, поиск

Задача о счастливых билетах

64 байта добавлено, 18:10, 1 марта 2018
Решение путем интегрирования
Упростим многочлен <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_0int\limits_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_0int\limits_0^{2\pi}\left(\dfrac{2-2\cos(10\phi)}{2-2cos\phi}\right)^3d\phi=\dfrac{1}{2\pi}\displaystyle\int_int\limits_{0}^{2\pi}\left(\dfrac{\sin^2(5\phi)}{\sin^2(\frac{\phi}{2})}\right)^3d\phi=\dfrac{1}{\pi}\displaystyle\int_0int\limits_0^{\pi}\left(\dfrac{\sin(10\phi)}{\sin\phi}\right)^6d\phi=\dfrac{1}{\pi}\displaystyle\int_int\limits_{-\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>\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 2300</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_int\limits_{-\pi/10}^{\pi/10}f^td\phi=\displaystyle\int_int\limits_{-\pi/10}^{\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 \left(1 - \dfrac{33}{2}\phi^2\right)</tex>, а <tex>\ln{f}(\phi) \approx \ln 10 - \dfrac{33}{2}\phi^2</tex>. При больших <tex>t </tex> получим: <tex>{\displaystyle\int_int\limits_{-\pi/10}^{\pi/10}\exp(t(\ln 10 - \frac{33}{2}\phi^2))d\phi=10^t \int_int\limits_{-\pi/10}^{\pi/10}\exp(-\frac{33}{2}\phi^2)d\phi=\sqrt{\dfrac{\pi}{66t}} \cdot \mathrm{erf}\left(\sqrt{\dfrac{33t}{2}\phi}\right)\bigg\rvert_{-\pi/10}^{\pi/10}}</tex>, где <tex>\mathrm{erf}(z)</tex> {{---}} функция ошибок <ref>[http://mathworld.wolfram.com/Erf.html Erf -- from Wolfram MathWorld]</ref>. Заметим, что при <tex>z > 2 </tex> <tex>\mathrm{erf}(z) \approx 1</tex>, поэтому интеграл примерно равен <tex>10^t \sqrt{\dfrac{2\pi}{33t}}</tex>.
Полагая <tex>t=6</tex> и вспоминая выражение для <tex>p_0</tex>, получаем приближенное равенство:
: <tex>p_0 \approx \dfrac{10^6}{3\sqrt{11\pi}} \approx 56700</tex>
Этот результат с хорошей точностью (отклонение составляет не более <tex>3\%</tex>) приближает искомое значение.
 
== Способ с конечной суммой ==
Рассмотрим функцию <tex>g(\phi)=H(e^{i\phi})=\left(\dfrac{\sin{5\phi}}{\sin{\frac{\pi}{2}}}\right)^6</tex>. Как доказано выше, <tex>L_6=\dfrac{1}{2\pi}\displaystyle\int_0^{2\pi}g(\phi)d\phi</tex>. Для интеграла можно выписать приближенную формулу и получить <tex>L_6 \approx \dfrac{1}{N}\sum\limits_{k=0}^{N-1}g(\dfrac{2\pi k}{N})</tex>. Интересно, что при достаточно большом <tex>N</tex> это равенство становится точным.
Анонимный участник

Навигация