РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 11 № 3099 Добавить в вариант

Сколько способов замостить прямоугольник $2 \times 12$ неперекрывающимися доминошками $1 \times 2?$

Решение.

Пусть $d_n$   — количество способов замостить прямоугольник $2 \times n$ неперекрывающимися доминошками $1 \times 2.$ Если первая доминошка лежит вертикально; то количество способов равно $d_n минус 1 ;$ а если первая доминошка лежит горизонтально то количество способов равно $d_n минус 2.$ Тогда $d_n=d_n минус 1 плюс d_n минус 2,$ откуда $d_1=1$ и $d_2=2.$

Ответ: 233.

Олимпиада Университета Иннополис Innopolis Open, 11 класс, 1 тур (отборочный), 2016 год

Классификатор: Разное. Логические задачи

Спрятать решение · Помощь