Городская Жаутыковская олимпиада по математике, 7 класс, 2023 год

Сколькими способами в каждой клетке таблицы $4\times 4$ можно расположить цифры 0 и 1 так, чтобы сумма чисел в каждом столбце и сумма чисел в каждой строчке была четной?

Комментарий/решение

Ответ 2^9

Решение: Возьмем левый верхний квадрат 3*3 в этой таблице 4*4. Заметим что если мы будем расставлять числа в него в хаотичном порядке, то далее нижняя строчка автоматический выстроится, т.е. если сумма в первом столбце без нижн клетки была чет, то нижн кл автоматически должна быть 0. Аналогично со строками и остальными столбцами. Причем получившаяся строка и столбец которые не пересекаются с квадратом 3*3 имеют общ клетку - нижний правый уголок. Заметим что квадрат 3*3 такой же по четности как и самая нижняя строка без правого уголка и самый левый столбец без нижн клетки, так как если это не так то в одной из строк/ столбце сумма чисел будет нечетной что невозможно, а значит что мы можем поставить число в нижний правый уголок, причем единственным способом. Тогда ответ это кол во различных квадратом 3*3 в клетках которого расположены числа 1 или 0. В каждую клетку можно поместить 1 или 0 тогда ответ 2*2*...*2 и так 3*3 раз. Значит ответ 2^9