Задача
а) В таблице m×n расставлены знаки "+" и "–". За один ход разрешается поменять знаки на противоположные в любой строке или столбце. Докажите, что если таблица такими действиями не приводится к таблице из одних плюсов, то в ней есть квадрат 2×2, который тоже не приводится.б) В таблице m×n расставлены знаки "+" и "–". За один ход разрешается поменять знаки на противоположные в любой строке или столбце или на любой диагонали (угловые клетки тоже считаются диагоналями). Докажите, что если таблица такими действиями не приводится к таблице из одних плюсов, то в ней есть квадрат 4×4, который тоже не приводится.
Решение
а) Заметим, что допустимые ходы не меняют чётность количества плюсов в квадрате 2×2. Поэтому, если все квадраты 2×2 "приводятся", то изначально (а значит, и после любого числа ходов) в каждом из этих квадратов чётное число плюсов. Докажем,что тогда таблицу можно “привести”.
Меняя, если нужно, знаки в столбцах, заполним плюсами верхнюю строку. Затем действуя со строчками, заполним плюсами левый столбец (при этом верхняя строка не "испортится"). Докажем,что теперь во всей таблице стоят плюсы. Рассмотрим левый верхний квадрат 2×2 (см. рис.). В нём уже стоят три плюса. Значит и в клетке a стоит плюс. Теперь, рассмотрев соседний квадрат 2×2, видим, что и в клетке b стоит плюс. Продолжая, докажем это для всех клеток второй строки. Теперь повторяем рассуждение для третьей, затем четвёртой, ... и последней строк.

Сначала заполним плюсами левый верхний квадрат 4×4 (рис. в центре) – по предположению это можно сделать. Покажем, как продолжить это заполнение на четыре клетки справа от квадрата (a, b, c, d на рис. справа).

Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь