Задача 35054

Темы:    [ Комбинаторная геометрия (прочее) ] [ Принцип Дирихле (прочее) ]

Сложность: 2+ Классы: 7,8

Условие

В вершинах куба расставлены цифры 1, 2, ..., 8. Докажите, что есть ребро, цифры на концах которого отличаются не менее чем на 3.

Подсказка

От вершины с цифрой 1 до вершины с цифрой 8 можно дойти, двигаясь не более чем по трём ребрам.

Решение

  Назовём расстоянием между двумя вершинами куба наименьшее количество рёбер, которые нужно пройти от одной из этих вершин до другой. Легко видеть, что расстояние между любыми двумя вершинами не больше 3.
  Рассмотрим три (или меньше) ребра, по которым можно пройти из вершины 1 в вершину 8. Поскольку,  8 – 1 > 3·2,  то на концах одного из этих рёбер цифры отличаются не менее чем на 3.

Источники и прецеденты использования

web-сайт

задача