Отзывы пользователей

гдз

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

Подсказка

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

Назовем расстоянием между некоторыми двумя вершинами куба наименьшее количество ребер, которые нужно пройти от одной из этих вершин до другой. Легко видеть, что расстояние между любыми двумя вершинами куба не больше 3. Допустим, что условие задачи не выполнено, т.е. цифры на концах любого ребра отличаются не более, чем на 2. Рассмотрим вершину с цифрой 1. Поскольку расстояние от нее до любой вершины не более 3, число, стоящее в любой другой вершине, не более, чем 1+3*2=7. Однако в одной из вершин должна стоять цифра 8. Мы получаем противоречие, доказывающее утверждение задачи.

 
Поделиться: