Олимпиадная задача: способы разбиения прямоугольника 8×2 на 1×2 – комбинаторная геометрия
Задача
а) Сколькими способами можно разбить прямоугольник 8×2 на прямоугольники 1×2? б) Придумайте и опишите фигуру, которую можно разрезать на прямоугольники 1×2 ровно 555 способами.
Решение
а) Число способов равно f9= 34, где fn n-ное число Фибоначчи. Это утверждение следует из сдедующей, легко доказываемой по индукции леммы: прямоугольник n×2 можно разбить на прямоугольники 1×2 ровно fnспособами.
Ответ
а) 34 способами.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет