Сколькими способами можно покрасить хотя бы одну клетку доски 2×4 так, чтобы никакие две покрашенные клетки не имели общей стороны?
1 Ответ
Обозначим f(n) как количество способов покраски доски 2×n с учетом нашего условия. Мы будем определять рекурсивное соотношение для f(n).
Существует несколько возможных случаев в зависимости от того, какие клетки мы можем покрасить на первой колонне:
- Если мы не красим первую колонну (первую клетку в первом ряду и первую клетку во втором ряду), тогда у нас остаётся покрасить оставшуюся доску 2×(n−1). Таким образом, это даёт нам f(n−1) способов.
- Если мы красим только верхнюю клетку первой колонки, то нижнюю клетку покрасить нельзя. Это даёт нам возможность покрасить оставшуюся доску 2×(n−2). Таким образом, это создаёт f(n−2) способов.
- Если мы красим только нижнюю клетку первой колонки, то верхнюю клетку покрасить нельзя. Это также создаёт f(n−2) способов.
Собрав все эти варианты, мы получаем рекуррентное соотношение:
f(n)=f(n−1)+2f(n−2)
Теперь необходимо определить базовые условия для запуска рекурсивного соотношения:
f(0): это случай, когда нет клеток для покраски. Считаем, что есть 1 способ не красить клетки (пустое множество), поэтому f(0)=1.
f(1): для доски 2×1 у нас есть 3 варианта: не красить, красить только верхнюю клетку или красить только нижнюю. Таким образом, f(1)=3.
Теперь, имея начальные условия, можем найти f(2) и f(3):
f(2)=f(1)+2f(0)=3+2⋅1=5
f(3)=f(2)+2f(1)=5+2⋅3=5+6=11
f(4)=f(3)+2f(2)=11+2⋅5=11+10=21
Теперь мы получили f(4)=21, но это количество всех возможных покрасок, включая случай, когда мы не покрасили ни одну клетку.
В условии сказано, что мы ищем количество способов покрасить хотя бы одну клетку. Следовательно, нам нужно вычесть 1 из полученного результата:
f(4)−1=21−1=20
Ответ: 20