У Мистера Фокса есть в распоряжении фломастеры n цветов, которыми он собирается покрасить...

Question

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

Answer 1

Каждое ребро куба принадлежит двум граням, поэтому для того, чтобы каждая из 6 граней имела черное ребро, требуется не менее 3 черных ребер.

Пример, когда 3 черных ребер достаточно – в кубе ABCDABCD красим в черный цвет ребра AB, DD, BC. Нетрудно проверить, что такая раскраска нам подойдет.