Сколькими способами можно уложить N доминошек размером 2x1 ** доску размером 2xN клеток?

0 голосов
78 просмотров

Сколькими способами можно уложить N доминошек размером 2x1 на доску размером 2xN клеток?


Математика (20 баллов) | 78 просмотров
Дан 1 ответ
0 голосов
Правильный ответ

Пусть ответ на эту задачу #(N). Очевидно, #(1) = 1. Будет удобно считать, что #(0) = 1.

Найдём #(N) при N >= 2. Каждый способ замостить доску 2xN получается из предыдущих: либо самая правая стоит вертикально, тогда слева нужно замостить доминошками часть доски размером 2x(N - 1) (это можно сделать #(N - 1) способами), либо справа стоят две доминошки горизонтально, при этом оставшаяся часть имеет размер 2x(N - 2), и её можно покрыть #(N - 2) способами.

Значит, #(N) = #(N - 1) + #(N - 2), при этом #(0) = #(1) = 1. Получились числа Фибоначчи Fib(N). Для них, например, существует формула Бине:
Fib(N) = (ф^N - (-1/ф)^N)/sqrt(5), где ф - золотое сечение.

Ответ. #(N) = Fib(N).

(148k баллов)