Question

Можно ли клетки доски 5*5 покрасить в 4 цвета так, чтобы клетки, стоящие на пересечении любых двух строк и любых двух столбцов, были покрашены не менее чем в три цвета?

Answer 1

Предположим, что существует раскраска таблицы 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, покрашен в два цвета. Противоречие.
Ответ: нельзя