Решение задачи 190

Условие:

Сколькими способами в таблице n×n (n>1) можно расставить единицы и нули так, чтобы в каждом квадратике 2×2 сумма чисел была четной?

Решение:

Заполним верхнюю строку и левый столбец как попало. Тогда вторая строчка заполняется слева направо однозначно. Действительно, если в квадратике 2×2 три числа уже стоят, то четвертое определяется единственным способом. Аналогично заполняются оставшиеся строки (идем по строкам сверху вниз, строки заполняем слева направо).

Получается, ответ на эту задачу это число способов расставить 1 и 0 в верхней строке и в левом столбце. Нетрудно видеть, что это число равно 2^{2n−1}.

Ответ: 2^{2n−1}.