Назад
Задача

а) В таблице 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 на рис. справа).

  Точкиbиcпринадлежат одной из вышеупомянутых областей. Остальные шесть клеток в этой области уже заполнены плюсами. Значит, в клеткахbиcстоят одинаковые знаки. Если это минусы, поменяем все знаки в соответствующем столбце. Знаки в клеткахaиdможно (не задевая "хорошую" зону) поменять действиями вдоль диагоналей, помеченных знаками ♣ и ♠ на рис. в центре.   Аналогично продолжаем заполнение на следующие четыре клетки и т.д., пока не заполним первые четыре строки. Покажем, как добавить следующую строку. Изменив, если нужно, знаки в строке, поставим плюс в клеткуl(рис. справа). Затем поставим плюс в клеткуk(с помощью соответствующей диагонали). Докажем, что теперь во всех клетках пятой строки, кроме, может быть, самой правой, стоят плюсы. Действительно, в семи клетках закрашенной на рис. справа фигуры уже стоят плюсы. Значит, и в клеткеmстоит плюс. Сдвинув закрашенную фигуру на одну клетку вправо, видим, что и в клеткеnстоит плюс. И так далее.   Знак в крайней справа клетке при необходимости можно изменить "с помощью" диагонали (как в клеткеk).   Аналогично заполняются плюсами все последующие строки (по очереди).
Ответ

Ответ задачи отсутствует

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

Комментариев нет