Версия для печати
Убрать все задачи

---

Можно ли расставить по кругу числа 1, 2, ..., 60 в таком порядке, чтобы сумма каждых двух чисел, между которыми находится одно число, делилась на 2, сумма каждых двух чисел, между которыми находятся два числа, делилась на 3, сумма каждых двух чисел, между которыми находятся шесть чисел, делилась на 7?

   Решение

Тема:    [ Числа Фибоначчи ]

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

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

Условие

Рассмотрим множество последовательностей длины n, состоящих из 0 и 1, в которых не бывает двух 1 стоящих рядом. Докажите, что количество таких последовательностей равно F_{n + 2}. Найдите взаимно-однозначное соответствие между такими последовательностями и маршрутами кузнечика из задачи 3.109.

Подсказка

Найдите рекуррентную формулу для числа таких последовательностей. Можно также воспользоваться результатом задачи 3.109. Для этого нужно каждую единицу интерпретировать как прыжок кузнечика через клетку.

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