В квадрате 10х10 каждая клетка покрашена в красный или зелёный цвет. Сколько существует раскрасок для которых в любом квадрате 2х2 по две красных и две зелёных клетки

Задача: в квадрате 10×10 каждый 2×2 блок содержит ровно две красные и две зелёные клетки. Считать красный = 1, зелёный = 0. 1) Рассмотрим две соседние строки A (расположенная на каком–то уровне) и B (следующая строка). Обозначим в столбце j сумму S_j = A_j + B_j (два бита на одной позиции). Условие на каждый 2×2 блок (с столбцами j и j+1) эквивалентно тому, что S_j + S_{j+1} = 2 для каждого j = 1..9. Решим рекурренту S_j + S_{j+1} = 2: - Если S_1 = 1, то S_2 = 1, S_3 = 1 и так далее. Значит S_j = 1 для всех j. - Если S_1 = 0, то S_2 = 2, S_3 = 0, S_4 = 2, …, то S_j чередуются: 0,2,0,2, … Именно такие два типа сценариев возможны для пары строк A и B: - Тип I: S_j = 1 для всех j. Это значит B = NOT A (в каждой колонке цифра в строке B противоположна цифре в строке A). - Тип II: S_j чередуется 0 и 2. Это значит A_j = B_j для всех j, и самa общая строка A (и B) должна идти по чередованию: 0101010101 или 1010101010 (то есть обе строки одновременно равны одной из двух чередующихся строк). Следовательно, между двумя соседними строками разрешены два варианта перехода: - Перейти кNOT A (обязательно). - Если текущая строка A чередующаяся, можно перейти к той же самой строке A (копия). Заметим, что копия разрешена только если текущая строка A чередующаяся; если A не чередующаяся, копия невозможна. 2) Подсчёт количества раскрасок - Всего существует две чередующиеся строки длины 10: 0101010101 и 1010101010. Остальные 2^10 − 2 = 1022 строки не чередующиеся. - Пусть A1 — первая строка. - Если A1 чередующаяся: на каждом следующем шаге (для каждой из 9 переходов к A2…A10) есть 2 варианта выбора (копия или переход через NOT). Всего 2^9 вариантов переходов. При двух возможных A1 получаем 2 · 2^9 = 2^10 = 1024 раскраски. - Если A1 не чередующаяся: на каждом шаге можно сделать только переход через NOT; то есть ровно 1 раскраска для данного A1. Всего таких A1: 2^10 − 2 = 1022. Значит всего 1022 раскраски. Итого общее число раскрасок: 2046. Ответ: 2046. Замечание: общую формулу можно записать так: N(H, W) = количество раскрасок H×W с условием, что в любом 2×2 блоке две красные и две зелёные, равно 2^H + 2^W − 2. Здесь H = W = 10, поэтому N = 2^10 + 2^10 − 2 = 2046.