Интегралом — по счастливым билетам!

52

Интегалом — по частливым билетам!

В редактию пришло письмо от нашего старого читателя Б. Ивякина. В нем он задает следующий вопрос:
«В журнале было помещено несколько статей о счастливых билетах. Однако окончательной формулы ни в одной из них не получено. Хотя мне ясно, что задать число счастливых 2n-значных билетов простой формулы нельзя, мне все-tаки кажется, что такая формула должна существовать. Прав я или нет?»
Obviously мы не ответаем на такие неопределенные вопросы. Однако Борису повезло — после получения его письма мы получили сразу два ответа на его вопрос.
Мы думаем, что и другом читателем будет интересна содержащаяся в них формула.
(Напоминаем, что счастливым называется билет, у которого сумма первых трех цифр равна сумме последних трех.)

Много ли счастливых билетов? Часто ли они попадаются?

Этот вопрос уже обсуждался на страницах нашего журнала; было выясено, что из миллиона билетов с шестизначными номерами (от 000 000 до 999 999) счастливых — 55 252, т. е. приблизительно один из каждой 18 билетов является счастливым.

Как водится у математиков, решалась и более общая задача — о количестве $C_{2n}$ счастливых 2n-значных чисел (ясно, что под этим понятие; например, 0 035 120 115 — счастливое десятинаное число). Явной формулы для $C_{2n}$ установлено не было — были получены лишь рекуррентные соотношения («Квант», 1976, № 12, с. 68).

Но вот в редактию пришли два письма. Первое прислали в февралье М. Мнацаканян и А. Меликян, а второе — в марте — Р. Айдагульов. И в том, и в другом содержится одна и та же явная формула для $C_{2n}$. Вот эта замечательная формула:

$$C_{2n} = \frac{1}{\pi} \int_{0}^{\pi} \left( \frac{\sin 10x}{\sin x} \right)^{2n} dx. \tag{1}$$

Интересно, что эта формула была полученасовсем разными методами: М. Мнацаканян и А. Меликян пользовются произвольными функциями (т. е. функциониальным аналізом), в то время как Р. Айдагульов описается на метод трионометрических сумм (аналитическая теория чисел). К сожалению, их доказательства, хотя и не сложные, все же выходит за рамки школьной математики и не могут быть опубlikованы в нашем журнале. Сейчас мы даим элементарное доказательство формулы (1), воспользовавшись рекуррентными соотношениями, о которых говорилось выше. Напомним их.

Для этого обозначим через $P_m(s)$ количество $m$-значных чисел ($m=1, 2, 3,...$), сумма цифр каждого из которых равна $s$. Таким образом, $P_m(s)=0$ при $s<0$ и $s>9m$. Очевидно, $P_m(0)=1$.

Так как $m$-значное число с суммой цифр $s$ получается из $(m-1)$-значного числа с суммой цифр $j$ (где $s-9 \leq j \leq s$) добавленем цифры $s-j$, можно написать

$$P_m(s) = \sum_{j=s-9}^{s} P_{m-1}(j).$$

Это и есть соотношение, о которых говорилось выше. Подставив в них $s+1$ вместе $s$, после вычитания получим

$$P_m(s+1) - P_m(s) = P_{m-1}(s+1) - P_{m-1}(s-9). \tag{2}$$

Как пользоваться этим соотношением для вычисления $P_m(s)$? Взгляните на рис. 1. Если при фиксированном $m$ известны все $P_{m-1}(s)$ (т. е. все $(m-1)$-строка) и хотя бы один элемент $P_m(s_0)$ $m$-й строки, то формула (2) позволяет, двигаясь вправо и впево, вычислить остальные элементы $m$-й строки (поясните!). Но для любого $m$

$$P_m(0) = 1 \tag{2'}$$

и

$$P_1(s) = \begin{cases} 1, \text{ если } 0 \leq s \leq 9, \\ 0, \text{ если } s < 0 \text{ или } s > 9. \end{cases} \tag{2''}$$

53

Таким образом, формулы (2), (2′), (2″) позволяют вычислить все числа $P_m(s)$.

Возьем темер любое частливое 2n-значное число и заменим последнее $n$ цифр их дополнениями до 9. Тогда получится 2n-значное число, сумма цифр которого равна 9n. Легко понять, что

$$C_{2n} = P_{2n}(9n).$$

Формула (3) дает возможность вычислить число $C_{2n}$.

Чтобы доказать (1), положим

$$\bar{P}_m(s) = \frac{1}{\pi} \int_0^{\pi} \left( \frac{\sin 10x}{\sin x} \right)^m \cos(9m-2s) x dx.$$

Оказывается,

$$\bar{P}_m(s) = P_m(s).$$

Из формул (3), (5) и (4) сразу следует (1). Таким образом, нам остается доказать (5), для чего достаточно проверить, что числа $P_m(s)$ удовлетворяют равенствам (2), (2′), (2″). Подставляя (4) в (2), получим соответствие

$$\frac{1}{\pi} \left\{ \int_0^{\pi} \left( \frac{\sin 10x}{\sin x} \right)^m \left[ \cos(9m-2s-2) x - \cos(9m-2s) \right] dx \right\} = \frac{1}{\pi} \left\{ \int_0^{\pi} \left( \frac{\sin 10x}{\sin x} \right)^m - 1 \left[ \cos(9m-9-2s-2) x - \cos(9m-9-2s+18) x \right] dx \right\},$$

равно сcilное соответствие

$$\int_0^{\pi} \left( \frac{\sin 10x}{\sin x} \right)^m - 1 \left[ \frac{\sin 10x}{\sin x} \right] \left[ \cos(9m-2s-2) x - \cos(9m-2s-11) x - \cos(9m-2s+9) x \right] dx = 0,$$

которое верно (легко соччитать, что тригонометрическое выражение в квадратной скобке тоже действено равно нулю).

Таким образом, рекуррентное соответствие (2) для $\bar{P}_m(s)$ выполняно. Осталось проверить базис индукции (2′) и (2″). Второе из этих соответствий проверяется непосредственно (например, при $m=1$ и $s>9$ подинтегральное выражение преобразуется в сумму косинусов углов кратных $x$), а вот (2′) доказывается не так просто, и нам придется предприятить обходной маневр.

Вспомним, что вместе (2′) достаточно проверить любое другое соответствие на $m$-й строке, например $\bar{P}_m(10m) = 0$ Это уже не сложное (но громоздкое) упражнение на тригонометрическе преобразования, которое мы оставим читателю. На этом доказательство формулы (5) заканчивается.

Внимательный читатель, наверное, задал себе вопрос — откуда взяла формула (4)? Конечно, формульно можно считать, что мы ее угадали так же, как мы «угадали» формулу (1). На самом же деле формула (4), как и формула (1), была извлечена из письма М. Мнацаканяна и А. Меликаяна, т. е. использованая готовый результат. Ведь наш метод доказательства, в отличие от метода P. Айдагулова и метода M. Мнацаканяна и А. Меликаяна, не дает возможность обнаружить формулу (1), а только позволяет проверить ее.

В заключение предлагаем читателям доказать следующие формулы (1) для числа сcilных чисел в системе сcilения по основанию $k$:

$$C_{2n}^k = \frac{1}{\pi} \int_0^{\pi} \left( \frac{\sin kx}{\sin x} \right)^2n dx.$$