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

---

Требуется подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100).

Выходные данные
В выходной файл вывести количество искомых последовательностей.

Пример входного файла
5

Пример выходного файла
13

   Решение

Темы:    [ Ориентированные графы ] [ Многоугольники (прочее) ]

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

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

Условие

На сторонах некоторого многоугольника расставлены стрелки.
Докажите, что число вершин, в которые входят две стрелки, равно числу вершин, из которых выходят две стрелки.

Подсказка

Число выходящих стрелок равно числу вершин многоугольника.

Решение

Пусть n – число сторон данного многоугольника, а k – число вершин, в которые входит по две стрелки. Всего стрелок – n, из них 2k стрелок входят в данные k вершин, остальные  n – 2k  стрелок входят еще в  n – 2k  вершин (в каждую – по одной). Остаётся  n – k – (n – 2k) = k  вершин, в которые не входит ни одной стрелки, то есть из которых выходит по две стрелки.

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