Я ехал по Ленинграду в трамвае со своим племянником Мишей. Опустив в кассу 6 копеек, я оторвал два билета.

— Чур этот билет мой! — сказал Миша.

— Пожалуйста, бери любой из них. Они ведь совершенно одинаковые, с любым из них можно проехать весь маршрут.

— Одинаковые, да не совсем. Этот билет самый обыкновенный, на нем номер 286 357. А следующий билет с номером 286 358 — «счастливый», сумма первых трёх цифр совпадает с суммой последних трёх.

Тут я вспомнил, что уже не раз слышал о распространённом поверье: билет с одинаковыми суммами цифр приносит счастье. В данном случае Мише достался билет 286 358, в котором 2+8+6=3+5+8.

— И часто тебе попадаются «счастливые» билеты? — спросил я.

— Да нет, очень редко. Примерно раз в месяц. А так как я езжу в институт и обратно каждый день, кроме выходных, то, значит, в среднем один «счастливый» билет приходится на 50 обычных.

— Чепуха, — вмешался один из наших попутчиков; — Я вошёл на предыдущей остановке и в той же кассе вытянул тоже «счастливый» билет — 286 349. Да и сейчас кто-то отрывает билет 286 367, тоже «счастливый»; скоро появится — 286 376, затем 286 385. Так что в каждом десятке билетов есть один «счастливый».

— Это не вполне верно, — возразил новый пассажир, оторвавший «счастливый» билет 286 367. — Ваш пример ничего не доказывает. В следующем десятке будет ещё один «счастливый» билет — 286 394. А затем «счастливых» билетов долго не будет, вплоть до номера 286 439, так что здесь между двумя «счастливыми» билетами будет интервал в 45 билетов. Таких примеров можно привести много. В этой же катушке билетов, начальные цифры которых 286, между билетами 286 097 и 286 169, то есть среди 71 билета, нет ни одного «счастливого».

— Вот я и говорю, — подхватил Миша, — в среднем один «счастливый» билет попадается на полсотни.

— Это тоже опрометчивое заявление, — заметил я. — Чтобы правильно отнетить на этот вопрос, нужно его исследовать. А сначала нужно точно его сформулировать. Скажем, так: сколько существует «счастливых» шестизначных чисел от 000 000 до 999 999, то есть чисел, у которых равны суммы цифр первых трёх и последних трёх разрядов?

— Ну что же, — сказал Миша после недолгого размышления, — я сейчас не могу точно ответить на этот вопрос, но могу описать способ, позволяющий его решить, по крайней мере, в принципе. Выпишем подряд все числа от 000 000 до 999 999 и проверим каждое из них. Таким образом мы сможем пересчитать число «счастливых» билетов.

— Да, такой метод решения возможен. Он называется методом перебора. Им можно решать задачи, в которых исследуются свойства конечного набора каких-либо чисел или других объектов. Однако метод перебора имеет два недостатка. Прежде всего, он очень трудоёмок. Рассуди сам, необходимо проверить миллион чисел. Если на проверку каждого из них тратить всего 1 секунду, то потребуется 1 000 000 секунд, то есть почти 278 часов. При восьмичасовой ежедневной работе это займет 35 дней.

— Но ведь можно поручить это электронной вычислительной машине!

— Можно, конечно, но стоит ли «палить из пушки по воробьям»? Кроме того, метод перебора имеет и другой недостаток, который сохраняется и при расчете на ЭВМ. При переборе получается решение только одной конкретной задачи, которое обычно не позволяет произвести обобщения или вскрыть какие-либо неизвестные закономерности. Поэтому-то переборные методы решения в известном смысле неинтересны.

— Разрешите мне опять вмешаться в ваш разговор, — сказал обладатель счастливого билета 286 367. — Я заинтересовался вашей задачей и уже нашел её решение, правда, не точное, а приближённое, вернее то, что мы, математики, называем оценкой. Да, я не представился, зовут меня Георгий Владимирович, я доцент кафедры математики одного из технических вузов. Так вот, молодой человек, — обратился он к Мише, — давайте введём новое определение «счастливого» билета, или, лучше даже, введём новый термин, например, «красивый» билет. Будем называть билет «красивым», если сумма первых трёх цифр даёт тот же остаток при делении на 9, что и сумма следующих трёх цифр. Понятно?

— Понятно, — ответил /Миша, — но почему именно на 9?

— А потому, что в нашей десятичной системе счисления всякое число даёт тот же остаток при делении на 9, что и сумма его цифр. Это свойство даёт возможность легко найти число «красивых» билетов. Действительно, среди чисел от 1 до 999 ровно 111 дают при делении на 9 остаток 1, столько же остаток 2, и так далее.

Сколько же существует различных «красивых» чисел с остатком 1? На первом месте может стоять 111 чисел и для каждого из них следом можно поставить любое из тех же 111 чисел. Таким образом, получаем 111·111 = 12 321 «красивых» билетов с остатком 1. Такое же число «красивых» билетов дают остатки 2, 3 и так далее. А к числам с остатком 0 или, как мы привыкли говорить, делящимся без остатка, нужно еще прибавить число 000, поэтому их будет не 111, а 112, откуда следует, что «красивых» чисел с остатком 0 будет 112·112 = 12 544. Итак, всего «красивых» чисел будет 8·12 321 + 12 544 = 111 112.

— А при чём же здесь «счастливые» билеты? — спросил Миша.

— Это уже совсем просто! Ведь если равны суммы цифр, то равны и их остатки при делении на 9, следовательно, каждый «счастливый» билет является «красивым». Однако не всякий «красивый» билет будет «счастливым». Например, билет 100 748 будет «красивым», но не будет «счастливым». Итак, если обозначить число «счастливых» билетов через C, то можно написать неравенство

— Но это всё-таки не полное решение задачи, — сказал Миша. — Мы получаем, что «счастливых» билетов меньше 111 112, но не знаем, насколько. А можно ли показать, что их больше какого-то числа? Я слышал, что это называется «оценкой снизу».

— Можно дать и оценку снизу,— ответил Георгий Владимирович,—боюсь только, что она будет довольно грубой. Назовём «прекрасными» билетами такие, у которых номер состоит из двух совершенно одинаковых половинок, например 287 287. Таких билетов ровно 1000, а именно, 000 000, далее 001 001, 002 002, ... до 999 999. «Прекрасных» билетов, естественно, меньше, чем «счастливых», поэтому мы можем записать такую оценку:

Здесь оценка сверху более чем в 100 раз превышает оценку снизу, так что вряд ли такой результат можно считать решением поставленной задачи.

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

— Что это за признак? — спросил Миша. — Мы его не проходили.

— Он очень прост. Сложим все цифры, стоящие в нечётных разрядах, потом отдельно сложим числа, стоящие в чётных разрядах. Так вот, если разность полученных сумм делится на 11, то и всё число делится на 11, и наоборот, любое число, делящееся на 11, обладает этим свойством.

— Какое же отношение этот признак имеет к «счастливым» билетам?— удивлённо спросил Миша.

— Самое прямое, но скажи сначала, слышал ли ты о билетах, «счастливых по-московски»?

— Ах, да! Москвичи считают билет «счастливым», если сумма цифр, стоящих на чётных местах, равна сумме цифр, стоящих на нечётных местах. Вот чудаки!

— Во-первых, чудаком являешься ты, если веришь, что «счастливые» билеты могут приносить удачу, а во-вторых, москвичи называют «счастливыми» те же самые билеты, что и ленинградцы, а билеты, которые мы называем «счастливыми по-московски», они называют «счастливыми по-ленинградски». Так «американские горки» в Америке называют «русскими». Но не в этом дело. Совсем легко проверить, что номера билетов, которые ты называешь «счастливыми по-московски», делятся на 11. Верно?

— Верно, — ответил Миша.

— И этих билетов не больше, чем чисел от 0 до 999 999, делящихся на 11.

— То есть не больше 90 910! — воскликнул Георгий Владимирович.

— А каких билетов больше, — спросил Миша, — «счастливых» или «счастливых по-московски»?

— Совсем нетрудно установить, что одних столько же, сколько и других, — ответил я.

— Скажете тоже, «нетрудно», — хмыкнул Миша, — мы же не знаем, столько тех и других.

— А это и не нужно, — заметил Георгий Владимирович. — Расставь первые три цифры «счастливого» билета на чётные места, последние три цифры на нечётные места, и ты получишь из «счастливого» билета билет, «счастливый по-московски». И обратно, если у билета, «счастливого по-московски», собрать все цифры, стоящие на чётных местах, в первой половине номера, а остальные — во второй, то ты получишь «счастливый» билет. Таким образом, мы установили взаимно однозначное соответствие между теми и другими билетами. А отсюда следует, что их одинаковое количество. Верно?

— Верно! —воскликнул Миша.— Вот здорово! Значит, мы доказали, что «счастливых» билетов меньше, чем 90 910.

— А какова будет сумма цифр у номера, если в «счастливом» билете заменить три последние цифры на разности между 9 и этими цифрами?— спросил Георгий Владимирович.

— Сейчас, — задумался Миша, — та-а-к, ... трижды девять — двадцать семь... минус... плюс... Получается 27! А ведь опять получается взаимно однозначное соответствие! Георгий Владимирович, отсюда следует, что «счастливых» билетов столько же, сколько билетов с суммой цифр 27.

— Правильно, — ответил он.

— Но сколько же все-таки «счастливых» билетов? — взглянув на меня, спросил Миша.

— Ответ я тебе скажу сейчас: 55 252, то есть в среднем каждый 18-й билет «счастливый». А почему их столько, я расскажу тебе как-нибудь в следующий раз. Прощайся с Георгием Владимировичем и пойдём — нам пора выходить.

Л. М. Финк Ещё раз о счастливых билетах

Вчера мой племянник Миша вбежал ко мне с возгласом: «Дядя, я, кажется, решил!»

— Что ты решил?

— Задачу о счастливом билете. Помнишь, как-то в трамвае мы с тобой пытались посчитать, сколько существует «счастливых» трамвайных билетов, у которых сумма первых трёх цифр номера равна сумме последних трёх цифр?

— Как же, помню. Об этом нашем разговоре даже напечатали в «Кванте» (см. № 7 за 1975 г., с. 67–70). Значит, ты нашёл точное число счастливых билетов, не пользуясь при этом методом перебора?

— Почти.

— Что значит «почти»? Почти точное число?

— Нет, число-то точное. Но я всё-таки пользуюсь методом перебора. Правда, просматриваю не миллион шестизначных чисел, а в тысячу раз меньше.

— Расскажи-ка, как ты это делаешь.

— Я вычислил, сколько счастливых билетов имеют заданную сумму первых и последних трёх цифр, равную определённому числу, например k. Обозначим количество трёхзначных номеров с суммой цифр, равной k, через N(k). Чтобы получить счастливый билет с суммой трёх первых и трёх последних цифр, равной k, можно выбрать любой из этих N(k) трёхзначных номеров для левой половины номера билета и любой другой (или тот же самый) — для правой. Например, с суммой цифр k=1 есть три трёхзначных номера: 001, 010 и 100. Комбинируя их, получим 9 шестизначных номеров счастливых билетов:

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

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

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

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

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

— Я пробовал, дядя, честное слово! Но ничего не получилось.

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

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

— То, что мы рассматриваем трёхзначные номера.

— Но это и так ясно!

— Дело не в этом. Мы обобщим задачу и будем искать N_n(k) — количество n-значных номеров с суммой цифр, равной k.

— Дядя, я не могу решить задачу для трёхзначных номеров, а ты хочешь решать её и для четырёхзначных, и для пятизначных... Ведь это значительно труднее!

— Конечно, труднее, если пользоваться перебором. Но легче, если рассуждать логически. Между прочим, в истории математики известно немало задач, решить которые удалось лишь после того, как они были сформулированы в общем виде. Попробуй для начала найти N₁(k).

— Сейчас подумаю. Нужно определить, сколько однозначных чисел имеет сумму цифр k. Но для однозначного числа сумма цифр совпадает с самим числом. Тут и решать нечего. Есть одно однозначное число с суммой цифр, равной нулю, — это 0; одно однозначное число с суммой цифр, равной единице, — это 1, одно число с суммой цифр, равной двум, — 2, и т.д. Значит

— Отлично! Пойдём дальше. Предположим теперь, что мы уже знаем значения N_n–1(k) для всех k. Попробуем выразить через них N_n(k). Другими словами, попробуем найти количество n-значных номеров с суммой цифр, равной k, предполагая, что для (n–1)-значных номеров задача уже решена.

— Ясно, — ответил Миша. Значения N₁(k) мы уже знаем; поэтому нужно найти только способ перехода от n–1 к n. Тогда мы сможем последовательно определить значения N₂(k), N₃(k) и т.д. Ну что же, попробуем. Пусть первой цифрой n-значного номера является число l. Чтобы сумма цифр этого номера была равна k, остальные его цифры должны в сумме дать k–l. Таких (n–1)-значных номеров существует N_n–1(k–l). Цифра l может быть любым целым однозначным числом, не превосходящим k (то есть 0≤l≤9, l≤k), и каждой из этих цифр соответствует N_n–1(k–l) n-значных номеров с суммой цифр, равной k, причём все эти номера различны. Значит, всего таких номеров будет

причём, если k<9, то для l>k соответствующие значения N_n–1(k–l) мы будем считать равными нулю.

По формуле (*) можно вычислить значения N_n(k) для всех k, если известны значения N_n–1(k). А так как значения N₁(k) мы уже знаем, то задача решена!

— Совершенно верно, — сказал я. — Формулы, аналогичные формуле (*), называются рекуррентными. Конечно, чтобы по формуле (*) вычислить все значения N₃(k), нужно потрудиться, но не целый день, а минут 10–15. Но дело не во времени, а в получении регулярного, непереборного решения. Пользуясь полученной формулой, можно вычислить количество счастливых билетов не только для наших трамваев, но и для трамваев с восьмизначными, десятизначными и вообще 2n-значными номерами. Помнится, я читал в одном фантастическом романе, что в автобусах главной планеты системы α Центавра для билетов используются именно восьмизначные номера. Давай-ка найдём, чаще ли жителям этой планеты попадаются счастливые билеты, чем нам?

Миша взял листок бумаги и начал рисовать таблицу. Прежде всего он заполнил столбец для n=1 единицами при k в пределах от 0 до 9. Остальные клетки этого столбца можно было заполнить нулями, но он решил их не писать. Столбец для n=2 Миша получил по рекуррентной формуле (*), сложив соответствующие значения N₁(k), N₁(k–1), ..., N₁(0). Так

Затем по той же формуле были построены столбцы для n=3 и n=4.

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

Проделав это, Миша получил:

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

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

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

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

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

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

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

Н. Я. Виленкин Счастливые троллейбусные билеты

В этой книге задаче о счастливых билетах посвящено всего два абзаца, а математические приготовления к её решению изложены, как мне кажется, не лучшим образом — слишком много места уделено биномиальным коэффициентам и слишком мало производящим функциям. Так что я добавил сюда изложение похожей задачи из «Конкретной математики» Р. Грэхема, Д. Кнута и О. Паташника, в которой роль производящих функций показана гораздо чётче. — E.G.A.

Производящие функции

Выражение (1 + x)ⁿ тесно связано с биномиальными коэффициентами

— эти числа являются коэффициентами при x^k в разложении (1 + x)ⁿ по степеням x. Вообще выражение  f (x) называют производящей функцией для чисел a₀, ..., a_k, ..., если разложение  f (x) по степеням x имеет вид

Найдём, например, производящую функцию для числа способов представить N в виде суммы n слагаемых, каждое из которых равно одному из чисел k₁, ..., k_m. Чтобы в показателе степени получились такие слагаемые, надо возводить в степень сумму x^k1 + ... + x^km. А так как число слагаемых равно n, то и возводить надо в n-ю степень. Иными словами, при разложении (x^k1 + ... + x^km)ⁿ по степеням x коэффициентом при x^N и окажется искомое число способов.

В частности, если допустимыми значениями слагаемых являются числа 0, 1, ..., m–1, то число способов получить сумму N, складывая n слагаемых, равно C_m(n,N). Поэтому

Производящую функцию для чисел C_m(n,N) можно записать по-другому, если воспользоваться формулой для суммы геометрической прогрессии:

Разлагая (1 – x^m)ⁿ и (1 – x)^–n по формулам бинома Ньютона

	n						∞
(1 – xm)n =	∑	(–1)k	(	n k	)	xmk,     (1 – x)–n =	∑	(	k+n–1 n–1	)	xk,
	k=0						k=0

получаем

где суммирование ведётся по всем k от 0 до min (n, N/m).

Производящие функции можно написать для всех задач, решённых выше методом рекуррентных соотношений. Например, для задачи об уплате суммы в N коп. монетами достоинством в k₁, ..., k_m коп., причём каждая монета используется лишь один раз, производящая функция имеет вид

Счастливые троллейбусные билеты

Некоторые люди считают шестизначные номера троллейбусных билетов «счастливыми», если сумма первых 3 цифр равна сумме последних 3 цифр. Например, билет 615 372 «счастливый», так как 6+1+5 = 3+7+2 = 12.

Чтобы найти число счастливых билетов, заменим последние 3 цифры их дополнениями до 9. Например, вместо 615 372 возьмём 615 627. Тогда получится билет, сумма цифр которого равна 27 (например, 6+1+5+6+2+7 = 27). Так как цифры в билете принимают значения от 0 до 9, число цифр в каждом номере равно 6, а их сумма равна 27, то подсчёт счастливых билетов сводится к отысканию значения C₁₀(6, 27). А это значение можно найти по формуле (*)

	2
C10(6, 27) =	∑	(–1)k	(	6 k	)(	32–10k 5	)	=
	k=0

=

(

32 5

)

–

(

6 1

)(

22 5

)

+

(

6 2

)(

12 5

)

= 55 252.

Ещё одно отвлечение внимания от рассказа о счастливых билетах: фраза про «цифры и их дополнения до 9» напомнила один мелкий математический фокус. — E.G.A.

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

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

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

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

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

π    C2n =   1  π  ∫  ( sin 10x sin x ) 2n dx.   0

(1)

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

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

Так как n-значное число с суммой цифр k получается из (n–1)-значного числа с суммой цифр l (где k–9≤l≤k) добавлением цифры k–l, можно написать

	k
Nn(k) =	∑	Nn–1(l).
	l=k–9

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

Как пользоваться этим соотношением для вычисления N_n(k)? Взгляните на рисунок.

Если при фиксированном n известны все N_n–1(k) (т.е. вся (n–1)-я строчка) и хотя бы один элемент N_n(k₀) n-й строчки, то формула (2) позволяет, двигаясь вправо и влево, вычислить остальные элементы n-й строчки (поясните!). Но для любого n

и

N1(k) =  ì  1, если   0 ≤ k ≤ 9, í î  0, если   k < 0   или   k > 9.

(2")

Таким образом, формулы (2), (2'), (2") позволяют вычислить все числа N_n(k).

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

Формула (3) даёт возможность вычислить число C_2n.

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

π    Nn(k) =   1  π  ∫  ( sin 10x sin x ) n cos(9n – 2k)x dx.   0

(4)

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

Из формул (3), (5) и (4) сразу следует (1). Таким образом, нам остаётся доказать (5), для чего достаточно проверить, что числа N_n(k) удовлетворяют равенствам (2), (2'), (2"). Подставляя (4) в (2), получим соотношение

	π
1  π	∫	(	sin 10x sin x	)	n	[cos(9n – 2k – 2)x – cos(9n – 2k)x] dx =
	0

		π
=	1  π	∫	(	sin 10x sin x	)	n–1	[cos(9n – 9 – 2k – 2)x – cos(9n – 9 – 2k + 18)x] dx,
		0

равносильное соотношению

	π
1  π	∫	(	sin 10x sin x	)	n–1	[	sin 10x sin x	{cos(9n – 2k – 2)x –
	0

– cos(9n – 2k)x} – {cos(9n – 2k – 11)x – cos(9n – 2k + 9)x}] dx = 0,

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

Таким образом, рекуррентное соотношение (2) для N_n(k) выполнено. Осталось проверить базис индукции (2') и (2"). Второе из этих соотношений проверяется непосредственно (например, при n=1 и k>9 подынтегральное выражение преобразуется в сумму косинусов углов кратных x), а вот (2') доказывается не так просто, и нам придётся предпринять обходной манёвр.

Вспомним, что вместо (2') достаточно проверить любое другое соотношение на n-й строчке, например, N_n(10n) = 0. Это уже не сложное (но громоздкое) упражнение на тригонометрические преобразования, которое мы оставим читателю. На этом доказательство формулы (5) заканчивается.

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

В заключение предлагаем читателям доказать следующее обобщение формулы (1) для числа счастливых 2n-значных чисел в системе счисления по основанию m:

		π
C2n, m =	1  π	∫	(	sin mx sin x	)	2n	dx.
		0

Снова о счастливых билетах

«Квант» уже не раз писал о счастливых билетах (1975, № 7, 1976, № 12, 1978, № 11, 1988, № 1 и № 4), т.е. билетах, сумма первых трех цифр которых равна сумме трех последних цифр. Число счастливых билетов C_6, 10 выражается с помощью интеграла:

π    C6, 10 =   1  π  ∫  ( sin 10x sin x ) 6  dx.   0

(1)

В этой замечательной формуле число 6 показывает, что вычисляется число шестизначных счастливых билетов, а число 10 указывает на десятичную систему счисления. Если число цифр билета и основание системы счисления иные (скажем, 2n и m соответственно), то формулу нужно изменить очевидным образом:

		π
C2n, m =	1  π	∫	(	sin mx sin x	)	2n	dx.
		0

Г. А. Гальперин из Москвы и А. В. Корлюков из Гродно задались вопросом: что будет, если вычислять число счастливых билетов C_2n, m по приближённой формуле

N–1    C2n, m =  1 N  ∑   f (xk),     где   xk =  a +   kπ N  ,    f (x) =  ( sin mx sin x ) 2n .   k=0

(2)

Они обнаружили, что при любом N ≥ 1 + n(m–1) и любом a равенство (2) является точным! (Для шестизначных билетов и десятичной системы счисления нужно брать N ≥ 28.)

Доказательство можно получить, слегка модифицировав вывод формулы (1), приведённый в «Кванте» № 11 за 1978 год. Другой способ доказательства основан на том, что дробь

можно представить как «тригонометрический многочлен»

	n0
f (x) =	∑	(ak cos kx + bk sin kx);
	k=0

для всякого такого многочлена выполнено равенство

	π			N–1
1 π	∫	f (x) dx =	1 N	∑	f	(	a +	kπ N	)
	0			k=0

при достаточно большом N (подумайте, как связано N со «степенью» n₀ тригонометрического многочлена!).

Вычислять число счастливых билетов на компьютере удобнее по формуле (2), чем (1), тем более, что интеграл всё равно заменяется на приближённое значение. Кроме того, из формулы (2) можно получить интересные следствия.

Пусть, например, длина билета равна 2, а система счисления десятичная. Тогда в формуле (2) достаточно взять 10 слагаемых. В качестве точек x_k берём π/20, 3π/20, ..., 19π/20. Число C_2, 10 очевидно равно 10, a sin² (10x_k) = 1 для всех k. Поэтому

При других n и m читатели могут получить аналогичные равенства самостоятельно.

А. А. Михайлов из г. Стучка Латвийской ССР предлагает новый подход к задаче о счастливых билетах длины 2n в m-ичной системе счисления. Вот его рассуждение. Прежде всего, число счастливых билетов равно числу билетов, сумма цифр которых равна n(m–1) (попробуйте это доказать!). Это число, в свою очередь равно коэффициенту при x^n(m–1) многочлена

Чтобы найти этот многочлен, можно воспользоваться биномом Ньютона

	m
(1 + t)m =	∑	(	m k	)	tk,
	k=0

где биномиальные коэффициенты

(  m k )  =

ì í î

m! k! · (m – k)!    при 0 ≤ k ≤ m, 0    при 0 ≤ m < k.

Биномиальная формула верна и для отрицательных показателей m; при этом

Если выразить оба сомножителя, входящих в  f (x), с помощью бинома, то нетрудно найти коэффициент при x^n(m–1). Окончательная формула А. А. Михайлова для числа счастливых билетов выглядит так:

[n – n/m]  C2n, m = ∑ (–1)k (  2n k )(  (n – k)m + n – 1 2n – 1 ) , k=0

(3)

где квадратные скобки обозначают целую часть числа. Частный случай этой формулы для десятичной системы обнаружили также студенты из Иркутска Д. Балябин и С. Кривошеин.

Для числа обычных счастливых билетов получаем

Как видите, формула (3) позволяет вычислить число счастливых билетов довольно просто!

Для C_2n, 2 есть ещё более простое выражение. Действительно, в этом случае  f (x) = (1 + x)²ⁿ, поэтому

Кроме того, А. А. Михайлов отмечает, что число счастливых билетов совпадает с числом целых точек, лежащих строго внутри 2n-мерного куба [0, m+1]²ⁿ на проходящей через его центр гиперплоскости, перпендикулярной главной диагонали. Это число часто встречается в работах по современной вещественной алгебраической геометрии и называется числом Петровского (в честь академика И. Г. Петровского (1901–1973); см. комментарий в книге И. Г. Петровского «Избранные труды», выпущенной в 1986 году издательством «Наука»).

Рассмотрим одну популярную в начале 70-х годов задачу, ею как-то А. А. Кириллов открывал свой семинар для младшекурсников. В те времена человек, едущий в городском транспорте в Москве, должен был купить билет в автоматической кассе или у кондуктора. На билетах стояли шестизначные номера.

Билет назывался счастливым, если сумма первых трёх цифр его номера равнялась сумме последних трёх цифр.

Так, билеты с номерами 000 000 и 123 060 — счастливые, а билет с номером 123 456 — несчастливый. Считалось, что счастливый билет приносит счастье (особенно, если его съесть).

Возникает вопрос, сколько всего существует счастливых билетов? Или: какова вероятность покупки счастливого билета?

Человеку, владеющему элементарными навыками программирования, нетрудно написать программу для подсчёта числа счастливых билетов. Простейшая такая программа перебирает все номера от 000 000 до 999 999, отбирая среди них счастливые. Давайте, однако, попробуем обойтись без машины.

Разобьём все счастливые билеты на классы, в каждом из которых сумма первых трёх цифр одинакова. Эта сумма может принимать значения от 0 (для тройки цифр 000) до 27 (для тройки 999). Поэтому число классов равно 28. Обозначим через a_n число различных троек цифр с суммой цифр n. Первые несколько значений a_n нетрудно вычислить:

Легко видеть, что число счастливых билетов, сумма первых трёх цифр которых равна n, есть (a_n)². Действительно, как в начале, так и в конце номера счастливого билета можно поставить любую тройку цифр с суммой n. Таким образом, для подсчёта числа счастливых билетов нам достаточно вычислить числа a_n, а затем найти сумму квадратов этих 28 чисел.

Для вычисления значений a_n попробуем подсчитать сначала число одно- и двузначных чисел с суммой цифр n. Для каждого n = 0, 1, 2 ..., 9 существует ровно одно однозначное число с суммой цифр n (запись этого числа совпадает с записью числа n). Будем описывать однозначные числа многочленом

Смысл у этого многочлена следующий: коэффициент при sⁿ в многочлене A₁ равен числу однозначных чисел, сумма цифр которых равна n.

Другими словами, коэффициент при sⁿ в многочлене A₁ равен 1, если 0≤n≤9, и равен 0, если n>9.

Выпишем теперь многочлен A₂(s), описывающий двузначные числа. Коэффициент при sⁿ в многочлене A₂(s) равен числу двузначных чисел с суммой цифр n. (Мы рассматриваем и такие двузначные числа, в которых первая цифра или даже обе цифры могут равняться нулю.)

Нетрудно видеть, что степень многочлена A₂ равна 18. Действительно, 18 — наибольшая возможная сумма цифр двузначного числа. Несложно сосчитать и первые несколько коэффициентов этого многочлена:

Оказывается, многочлен A₂ легко строится по многочлену A₁.

ПРЕДЛОЖЕНИЕ 1. A₂(s) = (A₁(s))².

ДОКАЗАТЕЛЬСТВО. Произведение мономов s^k и s^m даёт вклад в коэффициент при мономе sⁿ многочлена (A₁(s))² в том и только в том случае. если n=k+m. Поэтому коэффициент при мономе sⁿ в многочлене (A₁(s))² есть в точности число способов представить число n в виде суммы n=k+m,   k, m = 0, 1, ..., 9. Таким образом, многочлен в правой части равенства совпадает с многочленом A₂.

Теперь нетрудно выписать и многочлен A₃(s) = a₀ + a₁s + ... + a₂₇s²⁷.

ПРЕДЛОЖЕНИЕ 2. A₃(s) = (A₁(s))³.

ДОКАЗАТЕЛЬСТВО. Доказательство практически дословно совпадает с доказательством предыдущего утверждения: коэффициент при sⁿ в многочлене (A₁(s))³ равен числу представлений числа n в виде суммы трёх цифр n=l+k+m,   l, k, m = 0, 1, ..., 9.

Итак, задача о числе счастливых билетов свелась к следующему: надо подсчитать число p₀ — сумму квадратов коэффициентов многочлена (A₁(s))³.

Обратите внимание на то, что умножение на многочлен A₁(s) — очень простая операция. Вычисления можно провести вручную, затратив на них около десяти минут. Надобность в написании программы отпадает.

Однако можно не останавливаться на достигнутом и пойти дальше. Подставим вместо s выражение e^iφ. Тогда A₃(e^iφ) = (A₁(e^iφ))³ будет тригонометрическим полиномом 27-й степени:

Воспользовавшись тем, что

2π 1  2π   ∫   eikφ · e–imφ dφ = 0

ì  1,   k = m, í î  0,   k ≠ m,

получим

	2π			2π	27		27		27
1  2π	∫	| A3(eiφ)|2 dφ =	1  2π	∫	∑	ak eikφ ·	∑	am e–imφ dφ =	∑	ak2.
	0			0	k=0		m=0		k=0

Суммируя геометрическую прогрессию и пользуясь тем, что

получаем

откуда искомая величина равна

2π π/2  p0 =  1  2π   ∫  ( sin2 (5φ) sin2 (φ/2) ) 3  dφ =  1  π   ∫  ( sin 10φ sin φ ) 6  dφ. 0 –π/2

(1)

Попробуем оценить значение интеграла (1). График функции  f (φ) = sin(10φ)/sin φ на отрезке [–π/2; π/2] выглядит так, как показано на рисунке. В нуле функция достигает своего максимума, равного 10. Вне отрезка [–π/10; π/10] величина функции  f  не превосходит 1/sin (π/10) ≈ 3. Поэтому вклад дополнения к отрезку [–π/10; π/10] в интеграл (1) не превосходит π·3⁶ ≈ 2100 (на самом деле он значительно меньше).

Вид графика функции  f (φ) =   sin(10φ)  sin φ  .

Основная же составляющая интеграла (1) сосредоточена на отрезке [–π/10; π/10]. Для оценки вклада этого отрезка воспользуемся методом стационарной фазы. Этот метод позволяет оценить значение интеграла

π/10		π/10
∫	f t dφ =	∫	et ln f dφ
–π/10		–π/10

при t → ∞. При больших значениях t величина интеграла определяется поведением функции ln f  («фазы») в окрестности своей стационарной точки 0 (точки, в которой (ln f )′ = 0, или, что то же самое,  f ′ = 0). В окрестности нуля  f (φ) ≈ 10·(1 – 33φ²/2), а ln f (φ) ≈ ln 10 – 33φ²/2. При больших t имеем

π/10		π/10
∫	et(ln 10 – 33φ²/2) dφ = et ln 10	∫	e–33tφ²/2 dφ ≈ et ln 10	√2π  √33t	.
–π/10		–π/10

Полагая t=6 и вспоминая формулу (1), получаем приближённое равенство

Полученный результат с хорошей точностью (отклонение составляет не более 3%) приближает искомое значение ^*.

На основании рассмотренного примера можно сделать некоторые выводы о комбинаторных задачах и методах их решения.

Задачи перечислительной комбинаторики состоят в подсчёте числа объектов, принадлежащих некоторому семейству конечных множеств. У каждого множества семейства имеется свой номер (в задаче о числе счастливых билетов таким номером была сумма цифр трёхзначного числа) .

Как правило, задача перечислительной комбинаторики «в принципе» разрешима: для каждого множества из семейства можно выписать все его элементы и таким образом узнать их число. Проблема, однако, состоит в том. чтобы найти «хорошее» решение, не требующее выписывания всех элементов изучаемых множеств.

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

При решении задач перечислительной комбинаторики очень полезно рассматривать производящие многочлены (или, более общо, производящие ряды). В нашем случае пользу принёс производящий многочлен A₃. Операции с комбинаторными объектами очень естественно выражаются в терминах производящих функций. Так, переход от однозначных чисел с заданной суммой цифр к трёхзначным числам состоял просто в возведении производящего многочлена A₁ в куб.

Привлечение методов из смежных областей математики (например, из анализа) позволяет по-иному взглянуть на перечислительную задачу и найти новые, зачастую неожиданные, подходы к её решению.