ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65399
Темы:    [ Числовые таблицы и их свойства ]
[ Теория алгоритмов (прочее) ]
[ Четность и нечетность ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

а) В таблице 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).
  Аналогично заполняются плюсами все последующие строки (по очереди).

Замечания

Баллы: 3 + 6

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Номер 25
Дата 2003/2004
вариант
Вариант осенний тур, основной вариант, 10-11 класс
задача
Номер 7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .