Пять участков отделены друг от друга заборами. можно ли побывать на каждом участке, но при этом этом перелезть через каждый забор ровно один раз?
Классическая задача по графам. Рассмотрим участки как вершины, а заборы между соседними участками — как ребра. Тогда у нас есть граф P5: вершины A, B, C, D, E по цепочке соединены ребрами AB, BC, CD, DE.
Цель: начать на каком–то участке, пройти так, чтобы побывать на каждом участке и прошить каждый забор ровно один раз. Это эквивалентно существованию эйлерова пути, который проходит по всем рёбрам ровно один раз.
Проверим условие Эйлера для графа:
- Граф связный.
- В графе должно быть либо 0, либо 2 вершины с нечетной степенью.
- В P5 конечные вершины A и E имеют степень 1 (нечетная), внутренние вершины B, C, D имеют степень 2 (четная). Всего две нечетные вершины — значит эйлеров путь существует.
Построим такой путь:
- Начинаем с левого участка A.
- Перепрыгиваем через забор AB к B, затем через BC к C, затем через CD к D, и наконец через DE к E.
- Переходы: A → B → C → D → E. Каждое движение пересекает свой забор ровно один раз, и мы побывали на каждом участке (A, B, C, D, E).
Ответ: да, можно. Простой способ — начать с одного конца ряда участков и идти к другому концу, последовательно пересекая каждый забор ровно один раз. Это обобщается так: если участки лежат в виде цепи (Pn), то существует такой путь от одной к другой крайних вершинам, пересекающий все рёбра ровно по одному.