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

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

Условие

Каждая клетка клетчатой плоскости раскрашена в один из n² цветов так, что в каждом квадрате из клеток встречаются все цвета. Известно, что в какой-то строке встречаются все цвета. Докажите, что существует столбец, раскрашенный ровно в n цветов.


Решение

  Назовём одну из строк, в которой встречаются все цвета, выделенной. Назовём множество клеток, отстоящих друг от друга по горизонтали и вертикали на кратное n число клеток, полным.

  Лемма. В полном множестве либо каждая строка, либо каждый столбец одноцветны.
  Доказательство. Предположим, что в какой-то строке нашего множества нашлись две клетки разного цвета; тогда найдутся и две клетки разного цвета на расстоянии n. Пусть это клетки a и b, а клетки полного множества над ними – x и y (см. рис.).

  Из сравнения цветов в квадратах, составленных из клеток множеств  aS1D  и  xS2D,  видно, что наборы цветов в множествах  aS1  и  xS2  одинаковы; аналогично одинаковы наборы цветов в  S2y  и  S1b.  Так как в множестве S1 нет клеток цвета b, то и в множестве  xS2  нет такого цвета; однако в  S2y  он есть, поэтому цвета y и b совпадают. Аналогично совпадают цвета x и a.
  Повторяя эти рассуждения, получаем, что столбец нашего множества, содержащий a, окрашен одинаково, и то же со столбцом b.
  Если найдутся две клетки на расстоянии n в каком-то столбце, покрашенные по-разному, то аналогично докажем, что строки множества, их содержащие, будут одноцветными. Но они пересекаются со столбцом цвета b, поэтому их цвета совпадают. Противоречие.

  Назовём полное множество вертикальным, если любой его столбец одноцветен, и горизонтальным в противном случае. Докажем, что все горизонтальные полные множества пересекаются с выделенной строкой.
  Пусть это не так. Рассмотрим строку нашего множества, ближайшую к выделенной; пусть она имеет цвет a. Тогда каждую клетку выделенной строки можно заключить в квадрат n×n вместе с какой-то клеткой цвета a из нашего горизонтального множества; поэтому в выделенной строке нет цвета a. Противоречие.
  Пусть каждый столбец пересекается с горизонтальным полным множеством. Тогда выделенная строка пересекается с n горизонтальными множествами, строки которых одноцветны; поэтому в выделенной строке только n цветов. Противоречие.
  Следовательно, есть столбец, для которого все полные множества, его содержащие, вертикальны. Его раскраска периодична с периодом n, то есть в этом столбце ровно n цветов.

Замечания

1. Можно доказать даже, что в каждом столбце содержится ровно n цветов.

2. Утверждение задачи (но не предыдущего замечания!) остаётся верным, если в какой-то строке содержится хотя бы  n² – n + 1  цвет.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2002
Этап
Вариант 4
Класс
Класс 11
задача
Номер 02.4.11.4

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

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