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