|
|
 |
Условие
Тетрадный лист раскрасили в 23 цвета по клеткам. Пара цветов называется хорошей, если существует две соседние клетки, закрашенные этими цветами. Каково минимальное число хороших пар?
Решение
Оценка. Нарисуем граф с 23 вершинами (цветами) и соединим рёбрами вершины, соответствующие хорошим парам.
Рассмотрим две произвольные вершины A и B. Возьмём некоторую клетку K, окрашенную в цвет A, и некоторую клетку L, окрашенную в цвет B. Построим "цепочку" клеток, соединяющих K с L. Каждым двум разноцветным соседним клеткам этой "цепочки" соответствует хорошая пара цветов, то есть ребро нашего графа. Тем самым мы построили путь от A к B.
Это значит, что наш граф связен, следовательно, в нём не менее 22 рёбер.
Пример раскраски в 23 цвета с 22 хорошими парами цветов: покрасим 22 несоседние клетки в 22 цвета, а оставшийся лист – в 23-й цвет.
Ответ
22 пары.
Замечания
3 балла
