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