ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 110088
УсловиеКаждая клетка клетчатой плоскости раскрашена в один из n² цветов так, что в каждом квадрате из n× клеток встречаются все цвета. Известно, что в какой-то строке встречаются все цвета. Докажите, что существует столбец, раскрашенный ровно в n цветов.РешениеНазовём одну из строк, в которой встречаются все цвета, выделенной. Назовём множество клеток, отстоящих друг от друга по горизонтали и вертикали на кратное n число клеток, полным. Лемма. В полном множестве либо каждая строка, либо каждый столбец одноцветны. Из сравнения цветов в квадратах, составленных из клеток множеств
a ∪ S1 ∪ D и x ∪ S2 ∪ D, видно, что наборы цветов в множествах a ∪ S1 и x ∪ S2 одинаковы; аналогично одинаковы наборы цветов в S2 ∪ y и S1 ∪ b. Так как в множестве S1 нет клеток цвета b, то и в множестве x ∪ S2 нет такого цвета; однако в S2 ∪ y он есть, поэтому цвета y и b совпадают. Аналогично совпадают цвета x и a. Назовём полное множество вертикальным, если любой его столбец одноцветен, и горизонтальным в противном случае. Докажем, что все горизонтальные полные множества пересекаются с выделенной строкой. Замечания1. Можно доказать даже, что в каждом столбце содержится ровно n цветов. 2. Утверждение задачи (но не предыдущего замечания!) остаётся верным, если в какой-то строке содержится хотя бы n² – n + 1 цвет. Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|