Олимпиадная задача по комбинаторной геометрии: раскраска доски 10×10 цветами

  Пример раскраски в 41 цвет показан на рисунке (неотмеченные клетки окрашены в 41-й цвет).

 Оценка. Если в каждой строке встречается не более четырёх цветов, то всего цветов не более 40. Пусть в строкеAвстретилось пять цветов. Если в каждой оставшейся строке имеется не более четырёх цветов, не встречающихся вA, то всего цветов не более, чем  5 + 4·9 = 41.   Пусть найдётся строка B , в которой встречается пять цветов, отличных от цветов строкиA. Назовём 10 цветов строкAиBстарыми, а все остальные цвета – новыми.   Теперь в каждом столбце встречается хотя бы два старых цвета (в строкахAиB), поэтому новых там не более трёх. Следовательно, всего в таблице 10 старых и не более 30 новых цветов, итого не более 40.

В 41 цвет.