Напечатать все последовательности длины k из чисел 1..n.

   Решение

а) Докажите, что производящая функция последовательности чисел Фибоначчи   F(x) = F₀ + F₁x + F₂x² + ... + F_nxⁿ + ...

может быть записана в виде     где   = ,  = .

б) Пользуясь результатом задачи 61490, получите формулу Бине (см. задачу 60578.

   Решение

В предложенном в предыдущей задаче алгоритме используется сравнение двух массивов (x <> last). Устранить его, добавив булевскую переменную l и включив в инвариант соотношение последовательность x - последняя.

   Решение

Напечатать все последовательности положительных целых чисел длины k, у которых i-ый член не превосходит i.

   Решение

Тема:    [ Принцип Дирихле (прочее) ]

Сложность: 3+ Классы: 7,8,9

Прислать комментарий

Условие

В банде 101 террорист. Все вместе они в вылазках ни разу не участвовали, а каждые двое встречались в вылазках ровно по разу.
Докажите, что один из террористов участвовал не менее чем в 11 различных вылазках.

Решение

Пусть есть террорист A, участвовавший не более чем в 10 вылазках. Остальных террористов ровно 100, поэтому хотя бы в одной из этих вылазок (обозначим её Z) участвовало не меньше 10 террористов (не считая A). Рассмотрим террориста B, не участвовавшего в Z. Он участвовал в вылазках со всеми 11 террористами вылазки Z, причём все эти вылазки различны.

Замечания

3 балла

Источники и прецеденты использования