|
|
 |
Условие
а) В таблице m×n расставлены знаки "+" и "–". За один ход разрешается поменять знаки на противоположные в любой строке или столбце. Докажите, что если таблица такими действиями не приводится к таблице из одних плюсов, то в ней есть квадрат 2×2, который тоже не приводится.
б) В таблице m×n расставлены знаки "+" и "–". За один ход разрешается поменять знаки на противоположные в любой строке или столбце или на любой диагонали (угловые клетки тоже считаются диагоналями). Докажите, что если таблица такими действиями не приводится к таблице из одних плюсов, то в ней есть квадрат 4×4, который тоже не приводится.
Решение
а) Заметим, что допустимые ходы не меняют чётность количества плюсов в квадрате 2×2. Поэтому, если все квадраты 2×2 "приводятся", то изначально (а значит, и после любого числа ходов) в каждом из этих квадратов чётное число плюсов. Докажем,что тогда таблицу можно “привести”.
Меняя, если нужно, знаки в столбцах, заполним плюсами верхнюю строку. Затем действуя со строчками, заполним плюсами левый столбец (при этом верхняя строка не "испортится"). Докажем,что теперь во всей таблице стоят плюсы.
Рассмотрим левый верхний квадрат 2×2 (см. рис.). В нём уже стоят три плюса. Значит и в клетке a стоит плюс. Теперь, рассмотрев соседний квадрат 2×2, видим, что и в клетке b стоит плюс. Продолжая, докажем это для всех клеток второй строки. Теперь повторяем рассуждение для третьей, затем четвёртой, ... и последней строк.
б) Предположим, что все квадраты 4×4 "приводятся". Докажем, что тогда и таблицу можно “привести”. Заметим, что допустимые ходы не меняют чётность количества плюсов в закрашенной на рис. слева области квадрата 4×4 (любая строка, столбец или диагональ пересекает эту область по чётному числу клеток). Поэтому в каждой из таких областей чётное число плюсов.
Сначала заполним плюсами левый верхний квадрат 4×4 (рис. в центре) – по предположению это можно сделать. Покажем, как продолжить это заполнение на четыре клетки справа от квадрата (a, b, c, d на рис. справа).
Аналогично продолжаем заполнение на следующие четыре клетки и т.д., пока не заполним первые четыре строки. Покажем, как добавить следующую строку. Изменив, если нужно, знаки в строке, поставим плюс в клетку l (рис. справа). Затем поставим плюс в клетку k (с помощью соответствующей диагонали). Докажем, что теперь во всех клетках пятой строки, кроме, может быть, самой правой, стоят плюсы. Действительно, в семи клетках закрашенной на рис. справа фигуры уже стоят плюсы. Значит, и в клетке m стоит плюс. Сдвинув закрашенную фигуру на одну клетку вправо, видим, что и в клетке n стоит плюс. И так далее.
Знак в крайней справа клетке при необходимости можно изменить "с помощью" диагонали (как в клетке k).
Аналогично заполняются плюсами все последующие строки (по очереди).
Замечания
Баллы: 3 + 6
