Ещё раз о счастливых билетах

68

Л. Финк

Еще раз о счастливых билетах

Вчера мой племянник Миша вбежал ко мне с возгласом: «Дядя, я, кажется, решил!»
— Что ты решил?
— Задачу о счастливом билете. Помнишь, как-то в трамвае мы с тобой пытались посчитать, сколько существует «счастливых» трамвайных билетов, у которых сумма первых трех цифр номера равна сумме последних трех цифр?
— Как же, помню. Об этом нашем разговоре даже напечатали в «Кванте» (см. № 7 за 1975 г., с. 67—70). Значит, ты нашел точное число счастливых билетов, не пользовы при этом методом перебора?
— Почти.
— Что значит «почти»? Почти точное число?
— Нет, число-то точное. Но я все-таки пользовусь методом перебора. Правда, просматрию не миллион шестизначных чисел, а в тысячу раз меньше.
— Рассказки-ка, как ты это делешь.
— Я вычислил, сколько счастливых билетов имеют заданную сумму первых и последних трех цифр, равную определенному числу, например $k$. Обозначим количество трех значений номеров с суммой цифр, равной $k$, через $N(k)$. Что бы получить счастливый билет с суммой трех первых и трех последних цифр, равной $k$, можно выбрать любой из этих $N(k)$ трехзначных номеров для левой половины номера билета и любой другой (или тот же самый) — для правой. Например, с суммой цифр $k = 1$ есть три трехзначных номера: 001, 010 и 100. Комбинируя их, получим 9 шестизначных номеров счастливых билетов:

$$\begin{array}{ccc} 001001 & 001010 & 001100 \\ 010001 & 010010 & 010100 \\ 100001 & 100010 & 100100 \end{array}$$

В обшем же случае счастливых билетов с суммой цифр, равной $k$ в каждой «половинке», будет $[N(k)]^2$. Наименьшее возможное значение $k$ равно 0 (для номера 000), а наиболее — 27 (для номера 999). Просуммировав значение $[N(k)]^2$ по $k$ от 0 до 27, мы получим число всех возможных счастливых билетов. Сделав это, я нашел ответ — число счастливых билетов $C = 55252$. То есть в среднем один из 18 билетов является счастливым.

Миша радовался так, будто оторвал сразу несколько счастливых билетов.

Поздравляю тебя с решением, — сказал я. — Вот только мне не ясно, каким образом ты определял значения $N(k)$.

— Очень просто. Выписал тысячу трехзначных чисел от 000 до 999 и подсчитал сумму цифр у каждой. Я справился с этим без всяких вычислительных машин — всего за одно воскресе, — гордо ответил Миша.

— Что же, пожалуйста, полезнее было бы понять формулу или правило, позволяющее нахождение $N(k)$ без перебора.
— Я пробовал, дядя, чистное слово! Но ничего не получилось.

— Давай попытаемся вместе. Для начала следует изменить обозначение: вместо $N(k)$ будет писать $N_3(k)$.

— А что означает эта тройка визу?

69

То, что мы рассматрием трехзначные номера.
Но это и так ясно!
Дело не в этом. Мы обобщим задачу и будем искать $N_n(k)$ — количество $n$-значных номеров с суммой цифр, равной $k$.
Дяя, я не могу решить задачу для трехзначных номеров, а ты хочешь решать ее и для четырехзначных, и для пятизначных … Ведь это значительно труднее!
Конецно, труднее, если пользоваться перебором. Но легче, если рассуждать логически. Между прочим, в истории математики известно немало задач, решить которые удалось лишь после того, как они были формированы в общем виде. Попробуй для начала найти $N_1(k)$.
Сейчас подумаю. Нужно определить, сколько однозначных чисел имеет сумму цифр $k$. Но для однозначного числа сумма цифр совпадает с самим числом. Тут и решать нечего. Есть одно однозначное число с суммой цифр, равной нулю, — это 0; одно однозначное число с суммой цифр, равной единице, — это 1, одно число с суммой цифр, равной двум, — 2, и т. д. Значит $N_1(k) = 1$, если $k$ принимает значения от 0 до 9, а при других значениях $k - N_1(k) = 0$.
Отлично! Пойдем дальше. Предположим теперь, что мы уже знаем значения $N_{n-1}(k)$ для всех $k$. Попробуем выразить через них $N_n(k)$. Другими словами, попробуем найти количество $n$-значных номеров с суммой цифр, равной $k$, предполагая, что для $(n-1)$-значных номеров задача уже решена.
Ясно, — ответил Миша. Значения $N_1(k)$ мы уже знаем; поэтому нужно найти только способ перехода от $n-1$ к $n$. Тогда мы сможем последовательно определить значения $N_2(k)$, $N_3(k)$, и т. д. Ну что же, попробуем. Пусть первый цифрой $n$-значного номера является число $l$. Чтобы сумма цифр этого номера была равна $k$, остальные его цифры должны в сумме дать $k-l$. Таких $(n-1)$-значных номеров существует $N_{n-1}(k) - l$. Цифра $l$ может быть любым целым однозначным числом, не превысodiaщим $k$ (то есть $0 \leqslant l \leqslant 9$, $l \leqslant k$), и каждой из этих цифр соответствует $N_{n-1}(k-l)$ $n$-значных номеров с суммой цифр, равной $k$, причем все эти номера различны. Значит, всего таких номеров будет
$N_n(k) = N_{n-1}(k) + N_{n-1}(k-1) + N_{n-1}(k-2) + N_{n-1}(k-3) + N_{n-1}(k-4) + N_{n-1}(k-5) + N_{n-1}(k-6) + N_{n-1}(k-7) + N_{n-1}(k-8) + N_{n-1}(k-9)$; () причем, если $k < 9$, то для $l > k$ соответствующего значения $N_{n-1}(k-l)$ мы будем считать равными нулю.
По формуле () можно вычислить значения $N_n(k)$ для всех $k$, если известны значения $N_{n-1}(k)$. А так как значения $N_1(k)$ мы уже знаем, то задача решена!
Совершенно верно, — сказал я. Формулы, аналогичные формуле (), называются рекуррентными. Конечно, чтобы по формуле () вычислить все значения $N_3(k)$, нужно потребиться, но не целый день, а минут 10—15. Но дело не во времени, а в получении регулярного, непереборного решения. Пользоваться полученной формулой, можно вычислить количество счастливых билетов не только для наших трамваев, но и для трамваев с восемизначными, десятизначными и вообще 2$n$-значными номерами. Помнится, я читал в одном фантастическом романе, что в автобухах главной планеты системы $\alpha$ Центавра для билетов используется именно восемизначные номера. Давай-ка найдем, чаше ли жителям этой планеты попадаются счастливые билеты, чем нам?
Миша взял листок бумаги и начал рисовать таблицу. Прежде всего он заполнил столбец для $n=1$ единицами при $k$ в пределах от 0 до 9. Остальные клетки этого столбца можно было заполнить нулями, но он решил их не писать. Столбец для $n=2$ Миша получил по рекуррентной формуле (*), сложив соответствующие значения $N_1(k)$, $N_1(k-1)$, …, $N_1(0)$

70

Так, $N_2(6) = N_1(6) + N_1(5) + N_1(4) + N_1(3) + N_1(2) + N_1(1) + N_1(0) = 7$. Затем по той же формуле были построены столбцы для $n = 3$ и $n = 4$.

Таблица значений $N_n(k)$

| $k$ | 1 | 2 | 3 | 4 |
| :— | :— | :— | :— | :— |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 2 | 3 | 4 |
| 2 | 1 | 3 | 6 | 10 |
| 3 | 1 | 4 | 10 | 20 |
| 4 | 1 | 5. | 15 | 35 |
| 5 | 1 | 6 | 21 | 56 |
| 6 | 1 | 7 | 28 | 84 |
| 7 | 1 | 8 | 36 | 120 |
| 8 | 1 | 9 | 45 | 165 |
| 9 | 1 | 10 | 55 | 220 |
| 10 | | 9 | 63 | 282 |
| 11 | | 8 | 69 | 348 |
| 12 | | 7 | 73 | 415 |
| 13 | | 6 | 75 | 480 |
| 14 | | 5 | 75 | 540 |
| 15 | | 4 | 73 | 592 |
| 16 | | 3 | 69 | 633 |
| 17 | | 2 | 63 | 660 |
| 18 | | 1 | 55 | 670 |
| 19 | | | 45 | 660 |
| 20 | | | 36 | 633 |
| 21 | | | 28 | 592 |
| 22 | | | 21 | 540 |
| 23 | | | 15 | 480 |
| 24 | | | 10 | 415 |
| 25 | | | 6 | 348 |
| 26 | | | 3 | 282 |
| 27 | | | 1 | 220 |
| 28 | | | | 165 |
| 29 | | | | 120 |
| 30 | | | | 84 |
| 31 | | | | 56 |
| 32 | | | | 35 |
| 33 | | | | 20 |
| 34 | | | | 10 |
| 35 | | | | 4 |
| 36 | | | | 1 |

Проделав это, Миша получил:
для двузначных номеров $C = 10$,
для четырехначных $C = 670$,
для шестиначных $C = 55252$,
для восмыначных $C = 4840030$.

— Таким образом, — подытожил Миша, — на планете системы α Центавра на 100 миллионов билетов приходится чуть больше чем 4,8 миллиона счастливых. В среднем — примерно один счастливый билет из 21, а не из 18, как у нас. Им потруднее, чем нам, добавить свое «счастье».

— Вот теперь, — сказал я, — можно считать поставленную задачу решенной.

— А нет ли других способов ее решения? — спросил Миша.

— Вероятно, есть. Может быть, их придумают читатели «Кванта» и поделятся с нами? Не обязательно статья найти точное число счастливых билетов, можно ограничиться оценкой или приближенной формулировкой эти оценки обеспечивают небольшую относительную погрешность. Вот, например, одна простая формула, выражающая количество $2n$-значных счастливых билетов при любом $n$ с относительной погрешностью не более 4%:

$$C \approx 10^{2n} / \sqrt{33n\pi}.$$

С увеличением $n$ относительной погрешности быстро уменьшается.

— Как ты получил эту формулу, дядя?

— Сейчас это объяснить трудно. Я воспользовался методами теории вероятности; найдюсь, что через несколько лет ты с этой теорией познакомилась.

— Теперь, — сказал Миша закончив таблицу, — можно подчитать число счастливых билетов с двумя значениями, четырехзначными, шестизначными и восмынающими номерами. Для этого числа в $n$-м столбце моей таблицы нужно возвести в квадрат и сложить.