Доказательство расположения жуках на плоскости
Задача
Есть 101 жук, среди которых некоторые являются друзьями. Известно, что любые 100 жуков могут расположиться на плоскости так, что каждые два из них будут друзьями тогда и только тогда, когда расстояние между ними равно 1. Верно ли, что все жуки тоже могут расположиться таким же образом?
Решение
Решение 1: Пусть два жука дружат тогда и только тогда, когда соответствующие точки на рисунке соединены сплошным отрезком.

Решение 2:Рассмотрим следующий граф: трапеция ABCD с основаниями BC = 33 и AD = 34 высоты
составленная из 67 правильных треугольников со стороной 1, и A и D соединены путем длины 33. Очевидно, его нельзя нарисовать на плоскости, соблюдая условие задачи, а граф, полученный из него удалением любой вершины, можно.
Ответ
Неверно.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь