Вопрос школьника
Попробуй раскрасить все нарисованные колпаки тремя карандашами разного цвета так, чтобы среди них не было двух одинаковых и цвета полос на одно колпачке не повторялись.
Ответ от учителя
Для решения этой задачи нам нужно использовать теорию графов и комбинаторику.
Представим каждый колпак в виде вершины графа, а каждую полоску на колпаке в виде ребра, соединяющего две вершины. Тогда наша задача сводится к тому, чтобы раскрасить вершины графа в три цвета так, чтобы никакие две смежные вершины не были одного цвета.
Для начала заметим, что в графе не может быть вершин степени больше двух, так как в противном случае на одном колпаке будет повторяться цвет полоски. Также заметим, что граф не может быть связным, так как в противном случае мы не сможем раскрасить вершины графа в три цвета.
Рассмотрим теперь несвязный граф, состоящий из нескольких компонент связности. Каждую компоненту связности можно раскрасить в три цвета, используя следующий алгоритм:
1. Выбираем произвольную вершину в компоненте связности и раскрашиваем ее в первый цвет.
2. Раскрашиваем всех смежных с ней вершин во второй цвет.
3. Раскрашиваем всех смежных с ними вершин в третий цвет.
4. Повторяем шаги 2 и 3 для всех еще не раскрашенных вершин в компоненте связности.
Таким образом, мы получаем раскраску каждой компоненты связности в три цвета. Остается только выбрать произвольную вершину в каждой компоненте связности и раскрасить ее в любой из трех цветов, не совпадающий с цветом, которым она уже раскрашена. Это можно сделать, так как каждая компонента связности не содержит вершин степени больше двух.
Таким образом, мы получаем раскраску всех вершин графа в три цвета, удовлетворяющую условиям задачи.
