Помните ли первый раз, когда вам рассказали про счастливые билеты?
Наверное, во многих городах уже редко встречается общественный транспорт, в котором выдают билеты с шестизначными номерами. Действуют электронные билеты или вообще не выдают ничего. Но в детстве это было своеобразным приключением, когда первый раз, кто-то из взрослых говорил: "Смотри, тебе попался счастливый билет!". Почему это так радовало взрослых людей?
Для меня это стало тайной, которую хотелось разгадать. Каждый раз, когда мне продавали билет, я внимательно считала сумму первых и последних трех цифр и пыталась понять, какой же билет будет счастливым? Может следующий, или предыдущий? Тогда это была довольно сложная задача.
И вот недавно эта тайна снова вернулась ко мне, но уже в другом свете. Возник вопрос, а сколько счастливых билетов есть вообще и как часто они попадаются. Задача не тривиальная, скажу я вам.
Сформулируем её следующим образом.
Как всегда существует топорный способ решит задачу: выписать все такие числа. Для этого потребуется проверить миллион вариантов, если делать это вручную, задачка станет утомительной. Посмотрим, какие есть более простые варианты.
Для начала осознаем, что сумма трех цифр находится в промежутке от 0 до 27. Соответственно мы можем все трехзначные числа разделить на 28 групп, в каждой из которой сумма цифр равна одному из чисел от 0 до 27.
С этим фактом мы можем значительно упростить перебор. Например, чтобы получить в сумме число 3, нужно взять следующие тройки: 012, 111, 003. Для каждой тройки посчитаем, сколько получится чисел, если переставлять местами цифры: 012 - 6 вариантов, 111 - 1 вариант, 003 - 3 варианта. Значит всего троек, которые дают в сумме число 3 - 10 вариантов. Таким образом, счастливых билетов, у которых сумма первых и последних трех цифр равна 3, будет 100 штук.
Подобные выкладки можно сделать для каждого числа из диапазона от 0 до 27. Подобное решение всё еще довольно сложное и длительное, но уже вполне реализуемое.
Посмотрим более простой способ.
Здесь нам придется воспользоваться индукцией. Рассмотрим самый простой случай: двухзначные числа (00, 01, 02, ..., 97, 98, 99), среди них есть 10 счастливых (00, 11, 22, ..., 88, 99). То есть, мы можем легко сказать, сколько чисел имеют сумму первых и последних цифр равной заданному числу.
Сделаем следующий шаг и рассмотрим четырехзначных числа. Соответственно, если нам нужно получить заданную сумму цифр k, то мы рассматриваем все варианты для первой цифры числа l < k. Тогда вторая цифра числа должна быть равна (k - l), и здесь мы можем точно сказать, сколько таких чисел есть, потому что для двухзначных чисел мы уже ответили на этот вопрос.
В общем виде формула выглядит следующим образом:
Используя эту формулу можно получить ответ довольно быстро. Хотя это уже не так важно.
Испугались?
55 252, если вам все еще интересно. В среднем один из 18 билетом принесет вам счастье!