Домино

Кость домино представляет собой прямоугольник размером 2x1. На костях нет никаких обозначений, все они неотличимы друг от друга.

У Вас есть коробка размера 2xn, в которую помещаются n костей. Вы можете упаковывать кости плашмя, не помещая одну на другую. К примеру, если у Вас коробка 2x3 и 3 кости, то Вы можете упаковать их тремя различными способами:

Сколькими способами можно упаковать n костей в коробку 2xn?

По данным разведки, такую задачу дают на собеседовании в московском офисе Гугла.

Решение
Мы хотим найти функцию F(n). Определим несколько первых значений.

Очевидно, что F(1)=1 (одну кость можно положить только одном способом) и F(2)=2 (в коробку 2x2 мы можем положить 2 кости двумя способами: обе вертикально или обе горизонтально).

Рассмотрим теперь коробку 2xn при произвольном n>2. Все возможные раскладки можно разбить на два непересекающихся класса. Либо две крайние справа кости лежат горизонтально, либо крайняя справа кость лежит вертикально:

В первом случае слева остаётся место для n-2 костей, которые можно разложить F(n-2) способами. Во втором случае слева остаётся место для n-1 кости, которые можно разложить F(n-1) способами. При этом никаких других раскладок быть не может.

Таким образом,
F(n) = F(n-1) + F(n-2)
F(2) = 2
F(1) = 1

Другими словами, F(n) есть последовательность чисел Фибоначчи.