Сколькими способами можно разбить прямоугольник 9 на 2 на прямоугольники 1 на 2 ?
Чтобы найти количество способов разбить прямоугольник размером 9 на 2 на прямоугольники размером 1 на 2, можно воспользоваться методом динамического программирования.
Обозначим \(a_n\) как количество способов разбить прямоугольник размером \(n\) на 2. Мы можем заметить следующее:
Если мы помещаем один прямоугольник 1 на 2 вертикально, то остаётся прямоугольник размером \((n-1)\) на 2. Таким образом, для этой конфигурации количество способов будет \(a_{n-1}\).
Если мы помещаем два прямоугольника 1 на 2 горизонтально, то остаётся прямоугольник размером \((n-2)\) на 2. Для этой конфигурации количество способов будет \(a_{n-2}\).
Таким образом, у нас есть рекуррентное соотношение:
\[ a_n = a_{n-1} + a_{n-2} \]
Теперь нужно установить базовые случаи:
- Для прямоугольника 1 на 2: \(a_1 = 1\) (один способ — поставить один прямоугольник).
- Для прямоугольника 2 на 2: \(a_2 = 2\) (можно поставить два вертикально или два горизонтально).
Теперь можем вычислить количества для \(n\) от 3 до 9:
- \(a_3 = a_2 + a_1 = 2 + 1 = 3\)
- \(a_4 = a_3 + a_2 = 3 + 2 = 5\)
- \(a_5 = a_4 + a_3 = 5 + 3 = 8\)
- \(a_6 = a_5 + a_4 = 8 + 5 = 13\)
- \(a_7 = a_6 + a_5 = 13 + 8 = 21\)
- \(a_8 = a_7 + a_6 = 21 + 13 = 34\)
- \(a_9 = a_8 + a_7 = 34 + 21 = 55\)
Итак, количество способов разбить прямоугольник 9 на 2 на прямоугольники 1 на 2 равно 55.
