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

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

Условие

В таблице размера n×n клеток: две противоположные угловые клетки – чёрные, а остальные – белые. Какое наименьшее количество белых клеток достаточно перекрасить в чёрный цвет, чтобы после этого с помощью преобразований, состоящих в перекрашивании всех клеток какого-либо столбца или какой-либо строки в противоположный цвет, можно было сделать чёрными все клетки таблицы?


Решение

  Пусть из некоторой раскраски P можно указанными преобразованиями сделать полностью чёрный квадрат. Тогда те же преобразования в обратном порядке переведут полностью чёрный квадрат в раскраску P . При каждом из этих преобразований одинаково раскрашенные строки или противоположно раскрашенные строки (то есть строки, соответствующие клетки которых раскрашены в разные цвета) переходят также в одинаково или противоположно раскрашенные. Следовательно, все строки раскраски P были одинаково или противоположно раскрашены. Наоборот, из каждой раскраски с этим свойством можно указанными преобразованиями сделать сначала все строки одинаковыми, а затем – и полностью чёрными. Каждая такая раскраска удовлетворяет одному из следующих условий.
  1) В каждой строке все клетки одного цвета. Тогда из условия следует, что в первой и последней строках все клетки чёрные, то есть всего чёрных клеток не менее 2n.
  2) В каждой строке есть не менее двух чёрных клеток, то есть всего чёрных клеток не менее 2n.
  3) Существует строка, в которой ровно одна чёрная клетка. Тогда либо первая, либо последняя строка с ней не совпадает и, следовательно, противоположна ей, то есть содержит  n – 1  чёрную клетку. В этом случае общее число чёрных клеток не меньше  (n – 1)·1 + 1·(n – 1) = 2n – 2.
  Таким образом, в любом случае в раскраске P должно быть не менее  2n – 2  чёрных клеток. Значит, число клеток, которые нужно предварительно перекрасить, должно быть не меньше  2n – 4.  На рисунке изображён квадрат n×n, все строки которого раскрашены одинаково или противоположно, а число предварительно перекрашенных в чёрный цвет клеток равно  2n – 4.


Ответ

2n – 4  клетки.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 70
Год 2007
вариант
Класс 11
задача
Номер 5

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

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