|
|
 |
Условие
(Счастливые билеты; предлагалась на Всесоюзной олимпиаде
по программированию 1989 года.) Последовательность из
2n цифр (каждая цифра от 0 до 9) называется
счастливым билетом, если сумма первых n цифр равна сумме
последних n цифр. Найти число счастливых
последовательностей данной длины.
Решение
(Сообщено одним из участников олимпиады; к сожалению, не могу указать фамилию, так как работы проверялись зашифрованными.) Рассмотрим более общую задачу: найти число последовательностей, где разница между суммой первых n цифр и суммой последних n цифр равна k ( k = - 9n,..., 9n). Пусть T(n, k) — число таких последовательностей. Разобьём множество таких последовательностей на классы в зависимости от разницы между первой и последней цифрами. Если эта разница равна t, то разница между суммами групп из оставшихся n - 1 цифр равна k - t. Учитывая, что пар цифр с разностью t бывает 10 - | t|, получаем формулу
