Задача 97787
|
|
 |
Условие
Несколько фишек двух цветов расположены в ряд (встречаются оба цвета). Известно, что фишки, между которыми 10 или 15 фишек, одинаковы.
Какое наибольшее число фишек может быть?
Решение
Занумеруем фишки слева направо. В соответствующем графе соединим рёбрами вершины, одноцветные по условию. При 25 фишках образуются две компоненты связности: 10-21-5-16 и 11-22-6-17-1-12-23-7-18-2-13-24-8-19-3-14-25-9-20-4-15; их можно раскрасить в разные цвета.
При добавлении 26-й фишки между этими двумя компонентами образуется перемычка 15-26-10. Следовательно, граф связен, и раскрасить его нельзя. Тем более нельзя раскрасить граф с большим числом фишек.
Ответ
25 фишек.
Замечания
баллы: 7
