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