Счастливые билеты

Подумаем, как подступиться к задаче. Как зацепиться за число 100 000? Это , что в то же время является количеством способов выбрать 5 цифр билета какими угодно.

Давайте так и сделаем: первые 5 цифр выберем произвольным образом. Последняя шестая цифра восстанавливается не более чем единственным образом: она должна быть равна разности между суммой первых трёх цифр и суммой 4-й и 5-й цифр. Если эта разность — цифра от 0 до 9, то такой билет существует. Если же разность больше 9 или меньше 0, то такой комбинации первых пяти цифр не соответствует никакой счастливый билет (например, комбинации мы не сможем подобрать счастливый билет, так как последняя цифра не может быть равна 18). Таким образом, счастливых билетов не больше 100 000.

Счастливый билет с суммой цифр состоит из двух трёхзначных номеров с суммой цифр каждый. Первый номер выбираем способами (по определению числа ), второй номер — тоже способами. Итого способов .

Как и во втором примере при вычислении , воспользуемся методом шаров и перегородок. У нас есть 10 шаров и мы хотим поставить две перегородки между ними. Способов . Однако некоторые из них нам не подходят, а именно те, где есть слагаемое 10. Поэтому их надо отнять. Таких способов всего 3: , и . Итого способов .

Воспользуемся первой задачей. В счастливом билете сумма цифр трёхзначного номера, образованного первыми цифрами, может быть от 0 до 27. Значит, сложив -шки для всех таких сумм, получим количество счастливых билетов.

Построим соответствие между номерами с суммой цифр и суммой цифр . Сопоставим номеру номер . Очевидно, что это взаимно-однозначное соответствие, или биекция. Значит, тех и других номеров поровну.

Воспользуемся двумя предыдущими задачами. Заменим в сумме из третьей задачи слагаемые, начиная с , на равные им слагаемые вида , и получим в точности требуемое количество.

При мы на самом деле уже нашли их количество во второй задаче, оно равно 3. При переберём все возможные варианты чисел в плохой тройке. Наибольшее число в плохой тройке может быть равно 10 или 11. При 10 тройка может состоять только из чисел 10, 1, 0, а при 11 — только тройка 11, 0, 0. В первом случае получаем 6 троек, во втором — 3 тройки. Всего в сумме 9 плохих троек.

Отметим, что при данных ограничениях в плохой тройке будет ровно одно число, большее 9. Рассмотрим наибольшее число в плохой тройке. Отнимем от него 10, получим некоторую тройку (уже точно не плохую) с суммой на 10 меньше, то есть из . Наоборот, к любой тройке из можно прибавить 10 к одному из трёх чисел и получить плохую тройку с суммой . Получается, что каждой плохой тройке с суммой цифр соответствует ровно одна тройка из , а вот каждой тройке из соответствует три плохие тройки с суммой цифр . Значит, последних втрое больше, чем .

Сначала посчитаем все тройки, в том числе плохие. Для каждого мы решаем сопутствующую задачу о разбиении шариков двумя перегородками, то есть получаем способов. Но при этом надо учесть плохие тройки. Для и мы уже посчитали раньше, что плохих троек 3 и 9 соответственно. Для вычисления плохих троек в случае и воспользуемся предыдущей задачей: при плохих троек , а при плохих троек . Таким образом, вычитая лишнее, получаем Вычисляем:

Не будем вычислять билеты с суммой цифр 27, а построим биекцию между теми и другими билетами.

Сопоставим счастливому билету билет . Так как , сумма цифр второго билета равна 27. Очевидно, что это соотвествие является биекцией, значит, тех и других билетов поровну.

Воспользуемся предыдущей задачей и оценим не количество счастливых билетов, а количество шестизначных номеров с суммой цифр 27. Решим задачу с шарами и перегородками: пусть у нас есть 27 шаров, которые мы хотим поделить на 6 кучек (возможно, пустых) с учётом порядка. Количество способов равно . Конечно, оценка не точная: мы учтём также способы, в которых некоторые слагаемые больше 9. Поэтому можно сделать вывод, что способов точно меньше, чем .