|
|
 |
Условие
Можно ли клетки доски 5×5 покрасить в 4 цвета так, чтобы клетки, стоящие на пересечении любых двух строк и любых двух столбцов, были покрашены не менее чем в три цвета?
Решение
Предположим, что существует раскраска таблицы 5×5, удовлетворяющая условию.
В каждом столбце найдётся цвет, в который покрашены по крайней мере две клетки этого столбца. Назовём такой цвет преобладающим для данного столбца (возможно, у какого-то столбца будет два преобладающих цвета).
Аналогично какой-то цвет (назовём его 1) будет преобладающим для двух столбцов. Поскольку от перестановки строк и столбцов ничего не зависит, будем считать, что это столбцы a и b. Также можно считать, что в первом столбце цветом 1 покрашены клетки a4 и a5. Тогда клетки b4 и b5 должны быть покрашены какими-то двумя различными цветами, отличными от цвета 1. Пусть они покрашены цветами 2 и 3, а поскольку цвет 1 – преобладающий для столбца b, можно считать, что клетки b2 и b3 покрашены цветом 1.
Рассмотрим клетку a3. Выбрав 3-ю и 5-ю строки и столбцы a и b, мы получим, что клетка a3 не может быть покрашенной цветами 1 и 2. Аналогично она не может быть покрашенной цветами 1 и 2 и, следовательно, покрашена цветом 4. Из аналогичных рассуждений получаем, что и клетка a2 покрашена цветом 4.
Значит, квадрат, состоящий из клеток a3, a2, b3 и b2, покрашен в два цвета. Противоречие.
Ответ
Нельзя.
