Разделы 
Дополнительно
Задача по математике - 1656
2019-01-20 
В какое наибольшее число цветов можно раскрасить все клетки доски размера $10 \times 10$ так, чтобы в каждой строке и в каждом столбце находились клетки не более, чем пяти различных цветов?
Решение:
Пример раскраски в 41 цвет показан на рис. (неотмеченные клетки окрашены в 41-й цвет). Докажем, что 41 - максимальное число цветов.
Если в каждой строке встречается не более 4 цветов, то всего цветов не более 40. Пусть в строке $A$ встретилось 5 цветов. Если в любой оставшейся строке имеется не более 4 цветов, не встречающихся в $A$, то всего цветов не более, чем $5 + 4 \cdot 9 = 41$. Иначе найдется строка $B$, в которой встречается 5 цветов, отличных от цветов строки $A$. Назовем 10 цветов строк $A$ и $B$ «старыми», а все остальные цвета - новыми. Теперь в каждом столбце встречается хотя бы 2 старых цвета (в строках $A$ и $B$), поэтому новых там не более 3. Следовательно, всего в таблице 10 старых и не более 30 новых цветов, итого не более 40.
Ответ. 41.
В какое наибольшее число цветов можно раскрасить все клетки доски размера $10 \times 10$ так, чтобы в каждой строке и в каждом столбце находились клетки не более, чем пяти различных цветов?
Решение:
Пример раскраски в 41 цвет показан на рис. (неотмеченные клетки окрашены в 41-й цвет). Докажем, что 41 - максимальное число цветов.
Если в каждой строке встречается не более 4 цветов, то всего цветов не более 40. Пусть в строке $A$ встретилось 5 цветов. Если в любой оставшейся строке имеется не более 4 цветов, не встречающихся в $A$, то всего цветов не более, чем $5 + 4 \cdot 9 = 41$. Иначе найдется строка $B$, в которой встречается 5 цветов, отличных от цветов строки $A$. Назовем 10 цветов строк $A$ и $B$ «старыми», а все остальные цвета - новыми. Теперь в каждом столбце встречается хотя бы 2 старых цвета (в строках $A$ и $B$), поэтому новых там не более 3. Следовательно, всего в таблице 10 старых и не более 30 новых цветов, итого не более 40.
Ответ. 41.
