Question

У Мистера Фокса есть в распоряжении фломастеры n цветов, которыми он собирается покрасить рёбра куба (каждое ребро — в один из n цветов). Найдите наибольшее значение n, для которого существует такая раскраска рёбер куба, что для любых двух цветов (из n) найдутся два ребра, покрашенные в эти цвета и имеющие общую вершину.

Answer 1

Должно быть не меньше, чем по два ребра каждого цвета. Значит, максимум, 12:2=6 цветов. Представим, что цветов больше 6. Тогда у нас найдется обязательно одно ребро, у которого нет пары по цвету. Потому что всего 12 ребер в кубе. Но у каждого ребра в кубе только 4 ребра, с которыми он имеет соседнюю вершину. Получается 5 разных цветов, а мы только что решили, что их больше 6-ти. Получается несоответствие условию задачи. Поэтому ответ- 6 цветов максимум.