Распечатать запись Распечатать запись

Число “счастливых’’ билетов

Сначала немного истории. Автобусные билеты имели (да и сейчас это, кажется, так же) номера, состоящие из шести цифр. Разумеется, номер билета мог начинаться на 0. “Счастливыми’’ назывались билеты, у которых сумма первых трех цифр равна сумме последних трех цифр. Была распространена уверенность (во всяком случае, среди детского населения страны), что если тебе достался “счастливый’’ билет, ты можешь загадать желание и съесть билет, тогда твое желание исполнится. Отсюда название. Конечно же, “счастливые’’ билеты доставались ребятишкам не так уж часто. Честно говоря, ни разу не видела, чтобы кто-нибудь такой билет действительно съел, да и сама не ела. Хотя слухи о съевших “счастливый’’ билет и взамен получивших исполнение желания, ходили, и многие были убеждены в том, что они основаны на реальных событиях ;) Соответственно, поскольку билетов таких было не так уж много, возникла и следующая задача о числе “счастливых’’ билетов. Итак,

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

В наше время эта задача была достаточно известной. Мне, помнится, она была предложена на уроке алгебры в 9 классе, когда изучали комбинаторику. Кроме того, на тему “счастливых’’ билетов были статьи в журнале “Квант’’ (например, их можно найти здесь). Но удивительно то, что сейчас почему-то пишут о других методах подсчета числа “счастливых’’ билетов, совсем не о комбинаторных, как это было раньше. В основном предлгается программа, написанная на одном или другом языке программирования, которая позволяет решить эту задачу. Забавно, что в написании такой программы ничего сложного нет, это всего лишь цикл, т.е. вещь достаточно стандартная и скучная. А вот попытаться решить задачу с помощью комбинаторики гораздо интереснее и полезнее. Надеюсь, вы это сделаете, прежде чем начать читать дальше :) .

Решение. Само решение требует достаточно большого числа вычислений, однако они не очень сложные. Важно понять, как их сократить.

Найдем a_k — число билетов, у которых сумма первых трех цифр равна сумме трех последних цифр и равна k. Ясно, что k может принимать значения от 0 (три 0) до 27 (три “девятки’’).

Сначала докажем, что a_k=a_{27-k}. В самом деле, каждой последовательности из трех десятичных цифр с суммой цифр k от 0 до 13 можно поставить в соответствие последовательность из трех десятичных цифр с суммой цифр 27-k следующим образом: каждую цифру c в исходной последовательности заменим на цифру 9-c. Тем самым, каждой последовательности из трех десятичных цифр с суммой цифр k от 0 до 27 будет соответствовать одна и только одна последовательность из трех десятичных цифр с суммой цифр 27-k, принимающей значения от 14 до 27. Значит, таких последовательностей с суммой цифр k, где 0\le k\le 13 столько же, сколько последовательностей с суммой цифр 27-k (a_k=a_{27-k}).

Далее нам понадобится число способов представления целого неотрицательного числа n в виде суммы трех целых неотрицательных слагаемых. Это можно сделать C_{n+2}^2 способами. Действительно, число способов равно числу сочетаний с повторениями из n по 3 (или иначе, разбиваем n единиц на три группы — три слагаемых, в качестве разделителей используем нули, всего n+2 элемента, из которых нужно выбрать 2 нуля, см. сочетания с повторениями).

Число способов a_k получить сумму k от 0 до 9 можно вычислить по полученной формуле:

k=0: a_0=1 (впрочем, это и так очевидно, 0=0+0+0, иначе никак),

k=1: a_1=C_3^2=3,

k=2: a_2=C_4^2=6,

k=3: a_3=C_5^2=10,

k=4: a_4=C_6^2=15,

k=5: a_5=C_7^2=21,

k=6: a_6=C_8^2=28,

k=7: a_7=C_9^2=36,

k=8: a_8=C_{10}^2=45,

k=9: a_9=C_{11}^2=55.

Теперь перейдем к a_{10}. Здесь все немного сложнее, потому что цифры 10 не существует, и нам нужно из всех способов разбиения числа 10 не три целых неотрицательных слагаемых вычесть те способы, в которых одно из слагаемых равно 10. Подсчитать эти способы можно довольно легко. Мы первое слагаемое в разложении числа 10 на сумму трех слагаемых положим равным 10, а дальше подсчитаем количество способов представить оставшееся число (0) в виде суммы трех целых неотрицательных слагаемых (этих способов C_{2}^2=1). Получаем (с учетом того, что слагаемое 10 может стоять на трех разных местах)

k=10: a_{10}=C_{12}^2-3C_{2}^2=66-3=63.

Для k=11,12,13 поступаем точно так же. Сначала находим число способов представить 11 в виде суммы трех целых неотрицательных слагаемых — оно равно C_{13}^2, а затем вычитаем те способы, в которых одно из слагаемых больше либо равно десяти — их всего 3C_{3}^2. Итак,

k=11: a_{11}=C_{13}^2-3C_{3}^2=78-9=69,

k=12: a_{12}=C_{14}^2-3C_{4}^2=91-18=73,

k=13: a_{13}=C_{15}^2-3C_{5}^2=105-30=75.

Число билетов, у которых сумма первых трех цифр равна сумме последних трех цифр и равна k, находится как a_k^2 (независимо от способа выбора первых трех цифр с суммой k мы можем выбрать три последние цифры, сумма которых также равна k).

Осталось найти общую сумму:

2\cdot(1^2+3^2+6^2+10^2+15^2+21^2+28^2+36^2+45^2+55^2+63^2+69^2+73^2+75^2)=

=55252.

Итак, всего есть 55252 “счастливых’’ билета.

Комментариев: 2

  1. 1 Сергей:

    Но тут есть ещё один прикол – были серии, в которых крайне редко эти билеты встречались, например, если начало с 868 … тута уже 001 и 002 далеко не катит… это уже распределение !!! другие законы математики !! Если можно, просчитайте, плиз!!!!!

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Так тут отдельно нужно считать для каждой серии :-)

    [Ответить]

Оставьте свой отзыв

Добавить изображение