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

[ последовательностей ]

Одним из классических примеров использования производящих функций является задача о счастливых билетах.

Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, 024321. Первая цифра номера билета может быть нулём. Известно, что количество счастливых билетов из шести цифр равно 55252. Но как это число было получено? Вообще, как решать более сложную задачу: для любого положительного целого n указать количество 2n -значных счастливых билетов?

Здесь будут рассмотрены некоторые известные методы решения данной задачи. Количество счастливых билетов из 2n цифр будем обозначать символом L_n .

Метод динамического программирования

Введём обозначение: — количество n -значных чисел с суммой цифр, равной k (число может начинаться с цифры 0). Понятно, что любой билет состоит из двух частей: левой ( n цифр) и правой (тоже n цифр), причём в обеих частях сумма цифр одинакова. Количество счастливых билетов с суммой k в одной из частей, очевидно, равно . Значит общее количество 2n -значных счастливых билетов равно

Верхний индекс суммирования равен 9n , так как максимальная сумма цифр в одной части билета равна 9n .

Теперь осталось найти все значения . Количество n -значных чисел с суммой цифр k можно выразить через количество (n-1) -значных чисел, добавляя к ним n -ю цифру, которая может быть равна 0, 1, . 9:

Здесь неявно предполагается, что для n≥0 . Положим по определению .

Вычисление значений по указанной формуле лучше представить с помощью таблицы:

Любое число в этой таблице (кроме ) получается если просуммировать 10 элементов, стоящих слева и сверху от него. Например, в таблице красным цветом выделено число 73, а серым — числа, сумме которых оно равно. Само это число 73 означает, что именно столько существует трёхзначных чисел с суммой цифр 12.

Теперь нужно просуммировать квадраты чисел, стоящих в столбце n=3 : 1 2 +3 2 +6 2 +⋅⋅⋅=55252 . Если нужно было бы подсчитать восьмизначные билеты, то потребовалось бы вычислять столбец n=4 до значения k=36 .

Метод производящих функций

Билет состоит из двух частей. Рассмотрим произвольный счастливый билет, скажем, 271334 и заменим цифры второй его части на величину, которой им не хватает до 9. То есть 271665 . Теперь сумма всех цифр билета равна 27. Легко заметить, что такой фокус проходит с любым счастливым билетом. Таким образом, количество счастливых билетов из 2n цифр равно количеству 2n -значных чисел с суммой цифр, равной 9n . То есть

Теперь можно было бы воспользоваться техникой предыдущего пункта и найти число, стоящее в столбце n=6 и в строке k=27 . Получилось бы в точности 55252 . Но здесь можно воспользоваться техникой производящих функций.

Выпишем производящую функцию G(z) , коэффициент при z k у которой будет равен :

Действительно, однозначное число с суммой цифр k (для k=0. 9 ) можно представить одним способом. Для k>9 — ноль способов.

Заметим, что если возвести функцию G в квадрат, то коэффициент при z k будет равен числу способов получить сумму k с помощью двух цифр от 0 до 9:

В общем случае, G n (z) — это производящая функция для чисел , поскольку коэффициент при z k получается перебором всех возможных комбинаций из n цифр от 0 до 9, равных в сумме k . Перепишем производящую функцию в ином виде:

В итоге, нам требуется отыскать

Для этого посмотрим, что будет получаться, если раскрывать скобки в следующем выражении (нас интересует только коэффициенты при z 27 ):

Решение путём интегрирования

Внимание, данный раздел предназначен для тех, кто знаком с курсом ТФКП.

Воспользуемся производящей функцией G(z) из предыдущего раздела:

Составим ряд Лорана следующим образом:

Значение a₀ в данном разложении будет в точности равно [ проверьте ]

Интегральная теорема Коши говорит, что

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

Теперь подставим сюда H(z) :

Нетрудно видеть, что в общем случае

Отметим, что в реальности решать эту задачу путём интегрирования чрезвычайно затруднительно. На практике лучше работает метод динамического программирования.

Также в одном из упражнений будет предложено вывести формулу:

вычисление по которой представляется на сегодняшний день очень эффективным.

Рассмотрена классическая задача о подсчёте счастливых троллейбусных билетов. Приводится формула.

Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, [math]024321[/math] . Известно, что количество счастливых билетов из шести цифр равно [math]55252[/math] .

Содержание

Общие идеи [ править ]

Обозначим количество [math]n[/math] -значных чисел с суммой [math]k[/math] как [math]D_n^k[/math] (число может содержать ведущие нули). [math]2n[/math] -значный счастливый билет состоит из двух частей: левой ( [math]n[/math] цифр) и правой (тоже [math]n[/math] цифр), причём в обеих частях сумма цифр одинакова. Зафиксируем [math]x[/math] — [math]n[/math] -значное число с суммой [math]k[/math] в левой части (всего таких чисел [math]D_n^k[/math] , значит это можно сделать [math]D_n^k[/math] способами). Для него будет существовать [math]D_n^k[/math] возможных вариантов числа в правой части, следовательно количество счастливых билетов с суммой [math]k[/math] в одной из частей равно [math](D_n^k)^2[/math] . Значит общее число билетов равно [math]L_n = sumlimits_^ <9n>(D_^)^2[/math] . Верхний индекс суммирования равен [math]9n[/math] , так как максимальная сумма цифр в одной части билета равна [math]9n[/math] . Также можно сопоставить счастливому билету [math]a_1a_2ldots a_n b_1b_2 ldots b_n[/math] [math]2n[/math] -значное число с суммой [math]9n[/math] : [math]a_1a_2ldots a_n (9-b_1)(9-b_2) ldots (9-b_n)[/math] , причем это соответствие взаимно-однозначно, значит множества счастливых билетов и [math]2n[/math] -значных чисел с суммой [math]9n[/math] равномощны, поэтому [math]L_n=D_<2n>^<9n>[/math] .

Метод динамического программирования [ править ]

Научимся вычислять [math]D_n^k[/math] . Положим [math]D_0^k=egin1,&k=0\0,&kgt 0end[/math] . При [math]ngt 0[/math] количество [math]n[/math] -значных чисел с суммой цифр [math]k[/math] можно выразить через количество [math](n-1)[/math] -значных чисел, добавляя к ним [math]n[/math] -ю цифру, которая может быть равна [math]0, 1, ldots, 9[/math] : [math]D_n^k=sumlimits_^<9>D_^[/math] . Ответ — в [math]D_<2n>^<9n>[/math] , алгоритм будет работать за [math]O(n^2)[/math] .

Метод производящей функции [ править ]

Выпишем производящую функцию [math]G(z)[/math] , коэффициент при [math]z^k[/math] у которой будет равен [math]D_1^k[/math] : [math] G(z) = 1+z+z^2+z^3+z^4+z^5+z^6+z^7+z^8+z^9.[/math] Действительно, однозначное число с суммой цифр [math]k[/math] (для [math]k=0,ldots,9[/math] ) можно представить одним способом. Для [math]kgt 9[/math] — ноль способов. Заметим, что [math]G^n(z)[/math] — производящая функция для чисел [math]D_n^k[/math] , поскольку коэффициент при [math]z^k[/math] получается перебором всех возможных комбинаций из [math]n[/math] цифр, равных в сумме [math]k[/math] . Ответом на задачу будет [math][z^<9n>]G^<2n>(z)[/math] . Перепишем производящую функцию в ином виде: [math] G(z) = 1+z+ldots+z^9 = dfrac<1-z^<10>> <1-z>[/math] и получим, что [math]G^<2n>(z)=(1-z^<10>)^<2n>(1-z)^<-2n>=displaystylesumlimits_^<2n>inom<2n>(-z^<10>)^k[/math] [math]Big(sumlimits_^<infty>inom<-2n>(-z)^jBig)[/math] . Так как [math]dbinom<-2n>=(-1)^kdbinom<2n+k-1>[/math] , понятно, что [math][z^<9n>]G^<2n>(z)=displaystylesumlimits_^<lfloor<frac<9n><10>>
floor>(-1)^jinom<2n>inom<11n-10j-1><9n-10j>[/math] , что при [math]n=3[/math] дает [math]dbinom<6><0>dbinom<32><27>-dbinom<6><1>dbinom<22><17>+dbinom<6><2>dbinom<12><7>=55252[/math] .

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

Решение путем интегрирования [ править ]

Рассмотрим многочлен Лорана (т.е. многочлен, в котором допускаются отрицательные степени) [math]H(z)=G^3(z)G^3(1/z)[/math] . Заметим, что его свободный член равен [math]displaystylesumlimits_^<27>[z^i]G^3(z)cdot [z^<-i>]G^3(z^<-1>)=sumlimits_^<27>(D_3^i)^2[/math] . Воспользуемся теоремой Коши [2] из комплексного анализа:

Упростим многочлен [math]H(z)[/math] :

Рассмотрим функцию [math]f(phi)=dfrac<sin(10phi)><sinphi>[/math] на [math]left[-dfrac<pi><2>,dfrac<pi><2>
ight][/math] . Вне отрезка [math]left[dfrac<-pi><10>,dfrac<pi><10>
ight] f(phi) leqslant dfrac<1><sinfrac<pi><10>>approx 3[/math] , значит интеграл по этой части не больше [math]3^6pi approx 2300[/math] , основная часть сосредоточена на [math]left[-dfrac<pi><10>,dfrac<pi><10>
ight][/math] . Оценим интеграл по этому промежутку с помощью метода стационарной фазы. [3] Этот метод позволяет оценить значение интеграла

[math]displaystyleintlimits_<-pi/10>^<pi/10>f^tdphi=displaystyleintlimits_<-pi/10>^<pi/10>e^>dphi[/math] . При [math]t
ightarrow infty[/math] значение интеграла определяется поведением его фазы, т.е. [math]ln[/math] , в окрестности стационарной точки [math]0[/math] (точки, где [math](ln)’=0[/math] , или, что то же самое, [math]f’=0[/math] ). Вблизи [math]0[/math] [math]f(phi) approx 10 left(1 — dfrac<33><2>phi^2
ight)[/math] , а [math]ln(phi) approx ln 10 — dfrac<33><2>phi^2[/math] . При больших [math]t [/math] получим [math]<displaystyleintlimits_<-pi/10>^<pi/10>exp(t(ln 10 — frac<33><2>phi^2))dphi=10^t intlimits_<-pi/10>^<pi/10>exp(-frac<33><2>phi^2)dphi=sqrt<dfrac<pi><66t>> cdot mathrmleft(sqrt<dfrac<33t><2>phi>
ight)igg
vert_<-pi/10>^<pi/10>>[/math] , где [math]mathrm(z)[/math] — функция ошибок [4] . Заметим, что при [math]z gt 2 [/math] [math]mathrm(z) approx 1[/math] , поэтому интеграл примерно равен [math]10^t sqrt<dfrac<2pi><33t>>[/math] .

Полагая [math]t=6[/math] и вспоминая выражение для [math]p_0[/math] , получаем приближенное равенство:

[math]p_0 approx dfrac<10^6><3sqrt<11pi>> approx 56700[/math]

Этот результат с хорошей точностью (отклонение составляет не более [math]3\%[/math] ) приближает искомое значение.

Способ с конечной суммой [ править ]

Рассмотрим функцию [math]g(phi)=H(e^)=left(dfrac<sin<5phi>><sin<frac<pi><2>>>
ight)^6[/math] . Как доказано выше, [math]L_6=dfrac<1><2pi>displaystyleintlimits_0^<2pi>g(phi)dphi[/math] . Для интеграла можно выписать приближенную формулу и получить [math]L_6 approx displaystyledfrac<1>sumlimits_^gBig(dfrac<2pi k>Big)[/math] . Интересно, что при достаточно большом [math]N[/math] это равенство становится точным.

По определению, [math]g(phi)=sumlimits_^<27>a_je^[/math] , где [math]a_j[/math] — коэффициенты многочлена [math]H(z)[/math] . Обозначим [math]r(phi)=sumlimits_^<27>a_j(e^+e^<-ijphi>), g(phi)=a_0+r(phi)[/math] . Докажем, что [math]sumlimits_^g(phi_k)=0[/math] . Раскроем [math]g(phi_k)[/math] :

Рассмотрим внутреннюю сумму:

[math]<displaystylesumlimits_^left(expleft(dfrac<2ijkpi>
ight)+expleft(-dfrac<2ijkpi>
ight)
ight)=sumlimits_^expleft(dfrac<2ijkpi>
ight)+sumlimits_^expleft(-dfrac<2ijkpi>
ight)>[/math] . Получили две геометрические прогрессии со знаменателями, не равными [math]1[/math] : [math]Ngt j implies expleft(dfrac<2ijpi>
ight)
eq 1, expleft(-dfrac<2ijpi>
ight)
eq 1[/math] . Значит искомая сумма равна [math]dfrac<1-expleft(2ijpi
ight)><1-expleft(dfrac<2ijpi>
ight)>+dfrac<1-expleft(-2ijpi
ight)><1-expleft(-dfrac<2ijpi>
ight)>=0[/math] , так как [math]e^<2pi i>=1[/math] .

Таким образом, [math]dfrac<1>sumlimits_^gleft(phi_k
ight)=dfrac<1>sumlimits_^left(a_0+gleft(phi_k
ight)
ight)=a_0[/math] ,

Задача о счастливых билетах — условное название комбинаторной задачи подсчета количества последовательностей цифр длины 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>)[/math] . Отсюда с помощью этого многочлена Лорана и примененной к нему теоремы Коши о вычетах выводится, что число счастливых билетов равно:

[math]p_0 = frac<1> <pi>intlimits_0^ <pi>left ( frac<sin 10 x ><sin >
ight ) ^ <6>dx.[/math]

Аналогично выводится общая формула для нахождения количества [math]2n[/math] -значных счастливых билетов в [math]m[/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
e 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^_[/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]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]klt0[/math] и [math]kgt(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)[/math] :

[math]N_n(k + 1) – N_n(k) = N_(k + 1) – N_(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]

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