Задача 104050

Тема:    [ Геометрия на клетчатой бумаге ]

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

Условие

а) Сколькими способами можно разбить прямоугольник 8×2 на прямоугольники 1×2? б) Придумайте и опишите фигуру, которую можно разрезать на прямоугольники 1×2 ровно 555 способами.

Решение

а) Число способов равно f₉ = 34, где f_n — n-ное число Фибоначчи. Это утверждение следует из сдедующей, легко доказываемой по индукции леммы: прямоугольник n×2 можно разбить на прямоугольники 1×2 ровно f_n способами.

Ответ

а) 34 способами.

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

Кружок
Название	ВМШ 57 школы
класс
Класс	7
год
Место проведения	57 школа
Год	2005/06
занятие
Тема	Классическая комбинаторика
Название	Свобода выбора
Номер	13
задача
Номер	6