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

Материал из Циклопедии
Перейти к: навигация, поиск
Счастливый билет

Задача о счастливых билетах — условное название комбинаторной задачи подсчета количества последовательностей цифр длины 6, начиная с 000000 и до 999999, у которых сумма первых трех цифр равна сумме трех последних. Система счисления при этом предполагается десятичной, то есть цифры берутся от 0 до 9. Название задачи происходит от используемого в некоторых течениях городской культуры в СССР и России термина «счастливый билет» в отношении билетов общественного транспорта с суммой первых трех цифр равной сумме трех последних цифр или аналогичными свойствами. Задача может быть решена перебором, существуют и явные формулы ее решения. Возможное обобщение задачи — решать ее при четном числе цифр 2n и в m-ичной системе счисления (m, n — натуральные числа), то есть вычислять количество последовательностей цифр длины 2n, у которых сумма первых n цифр равняется сумме n последних цифр, а сами цифры берутся от 0 до m. Разбиралась в нескольких публикациях в журнале «Квант» в 1970-х и 1980-х годах, согласно С. К. Ландо предлагалась А. А. Кирилловым на своем семинаре в МГУ в 1970-е годы.

Содержание

[править] Явные формулы решения

Методом производящих функций в книге С. К. Ландо «Производящие функции» выводится следующая формула для числа 6-значных счастливых билетов в десятичной системе счисления.

Обозначим многочлен [math]A_1(s) = 1 + s + s^2 + ... + s^9[/math]. Он обладает свойством, что коэффициент при [math]s^n[/math] равен числу однозначных чисел, сумма цифр которых равна [math]n[/math]. Отсюда следует, что коэффициент при [math]s^n[/math] в многочлене [math]A_3(s) = (A_1(s))^3[/math] равен числу представлений числа [math]n[/math] в виде суммы трех цифр (принимающих значения от 0 до 9). Поэтому число счастливых 6-значных билетов в десятичной системе счисления равно сумме квадратов коэффициентов многочлена [math]A_3(s)[/math], что дает более простой по сравнению с полным перебором способ вычисления числа счастливых билетов.

Этот результат можно привести к явным формулам, использующим интеграл от тригонометрических функций, приписываемых в книге С. Ландо математику В. Дринфельду, который получил их будучи десятиклассником. В публикациях журнала «Квант» говорится, что формулы в виде интегралов прислали в журнал читатели.

Из предыдущего результата следует, что число счастливых билетов равно свободному члену (коэффициенту [math]p_0[/math] при члене [math]s_0[/math]) многочлена Лорана [math]A_3(s)A_3(\frac{1}{s})[/math]. Отсюда с помощью этого многочлена Лорана и примененной к нему теоремы Коши о вычетах выводится, что число счастливых билетов равно:

[math]p_0 = \frac{1}{\pi} \int\limits_0^{\pi} \left ( \frac{\sin 10 x }{\sin {x}} \right ) ^{6} dx.[/math]

Аналогично выводится общая формула для нахождения количества [math]2n[/math]-значных счастливых билетов в [math]m[/math]-ичной системе счисления:

[math]C_{2n,m} = \frac{1}{\pi}\int\limits_0^{\pi} \left ( \frac{\sin m x }{\sin {x}} \right ) ^{2n} dx.[/math]

Также число счастливых билетов совпадает с числом целых точек, лежащих строго внутри [math]2n[/math]-мерного куба [math][0, m+1]^{2n}[/math] на проходящей через его центр гиперплоскости, перпендикулярной главной диагонали, которое называется числом Петровского (в честь академика И. Г. Петровского).

[править] Решение методом включения-исключения

Рассмотрим конечное множество [math]B[/math], элементы которого обладают некоторыми из свойств [math]c_1, ..., c_r[/math]. Обозначим [math]N(c_i)[/math] — число элементов множества [math]B[/math], обладающих свойством [math]c_i[/math], через [math]N(c_i,c_j)[/math] — число элементов множества [math]B[/math], обладающих свойствами [math]c_i[/math] и [math]c_j[/math] ([math]i \ne j[/math]) и т. д. Пусть [math]|B|[/math] — общее число элементов множества [math]B[/math].

При этих обозначениях число элементов множества [math]B[/math], для которых не выполнено ни одно из свойств [math]c_i[/math] ([math]i = 1, …, r[/math]) равно (принцип включения-исключения):

[math]|B| - N(c_1) - … - N(c_r) + N(c_1, c_2) + … - N(c_1, c_2, c_2) - …[/math]

Число 10-ичных шестизначных счастливых билетов равно числу билетов с суммой цифр, равной 27 (это следует из того, что каждому счастливому билету с десятичной записью [math]a_1b_1c_1a_2b_2c_2[/math] можно взаимно-однозначно сопоставить билет с десятичной записью [math]a_1b_1c_1(9-a_2)(9-b_2)(9-c_2)[/math], который имеет сумму цифр 27. Введем множество [math]B[/math] всех расстановок неотрицательных целых чисел с суммой 27 в шести позициях, а также определим 6 свойств [math]c_1, ..., c_6,[/math] где свойство [math]c_i[/math] обозначает, что число в [math]i[/math]-й позиции не меньше 10. Число способов расставить [math]p[/math] неотрицательных целых чисел с суммой [math]q[/math] выражается через число сочетаний и равно [math]C^{p-1}_{p+q-1}[/math]. Поэтому имеем [math]|B| = C^5_{32}[/math] (число способов распределить 27 в 6 позиций), [math]N(c_i) = C^5_{22}[/math] (ставим в [math]i[/math]-ю позицию число 10, а оставшуюся сумму 17 распределяем произвольно по 6 позициям), [math]N(c_i, c_j) = C^5_{12}[/math] (ставим в i-ю и j-ю позицию число 10, а оставшуюся сумму 7 распределяем произвольно по 6 позициям), [math]N(c_i,c_j,c_k)=0[/math] (общая сумма 27 меньше, чем 30).

Таким образом, по принципу включения-исключения число 6-значных 10-ичных счастливых билетов равно

[math]C_{32}^5 - 6C_{22}^5+15C_{12}^5 = 55252.[/math]

Аналогично выполняется общая формула для нахождения количества [math]2n[/math]-значных счастливых билетов в [math]m[/math]-ичной системе счисления, которое равно числу билетов с суммой цифр [math]n(m–1)[/math]:

[math]C_{2n,m} = \sum\limits_{k=0}^{[\frac{(m-1)n}{m}]} (-1)^k C_{2n}^k C_{(m-1)n+2n-1-mk}^{2n-1}[/math]

Ее также можно вывести с помощью производящих функций.

[править] Рекуррентное соотношение, позволяющее найти число счастливых билетов

Table bilety.gif

Обозначим через [math]N_n(k)[/math] количество [math]n[/math]-значных [math]m[/math]-ичных чисел ([math]n=1, 2, 3, ...[/math]), сумма цифр каждого из которых равна [math]k[/math]. В частности, [math]N_n(k) = 0[/math] при [math]k\lt0[/math] и [math]k\gt(m-1)n.[/math] Очевидно, [math]N_n(0) = 1[/math].

Поскольку [math]n[/math]-значное число с суммой цифр [math]k[/math] получается из [math](n–1)[/math]-значного числа с суммой цифр [math]l[/math] (где [math]k–(m-1)≤l≤k[/math]) путем добавления цифры [math]k–l[/math], то:

[math]N_n(k) = \sum\limits_{l=k-(m-1)}^k N_{n–1}(l).[/math]

Отсюда получается рекуррентное соотношение, с помощью которого можно последовательно вычислять числа [math]N_n(k)[/math]:

[math]N_n(k + 1) – N_n(k) = N_{n–1}(k + 1) – N_{n–1}(k – (m-1)).[/math]

Имеем, что число счастливых [math]2n[/math]-значных [math]m[/math]-ичных билетов [math]C_{2n,m} = N_{2n}((m-1)n),[/math] так как оно равно числу билетов с суммой цифр [math]n(m–1).[/math]

С помощью данного рекуррентного соотношения можно дать элементарное (не использующее теорию функций комплексного переменного) доказательство формулы для числа счастливых билетов в виде интеграла.

[править] Литература

  • Ландо С. К. Лекции о производящих функциях — М.: МЦНМО, 2004. ISBN 5-94057-042-9

[править] Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты