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