Номер 3.117, страница 160 - гдз по математике 5 класс учебник Никольский, Потапов

3.117. Почтальон разнёс почту во все дома деревни, после чего зашёл с посылкой к Феде. На рисунке 149 показаны все тропинки, по которым проходил почтальон, причём, как оказалось, ни по одной из них он не проходил дважды. В каком доме живёт Федя? Каков мог быть маршрут почтальона?

Рис. 149

Для решения этой задачи представим схему деревни в виде графа, где дома и почта — это вершины, а тропинки между ними — рёбра. Условие задачи, что почтальон прошёл по каждой тропинке ровно один раз, означает, что его путь представляет собой эйлеров путь.

Эйлеров путь — это путь в графе, проходящий через каждое ребро ровно один раз. Согласно теореме Эйлера, такой путь существует тогда и только тогда, когда в графе имеется не более двух вершин с нечётной степенью (количеством рёбер/тропинок, выходящих из вершины).

1. Если в графе нет вершин с нечётной степенью, то эйлеров путь является циклом (начинается и заканчивается в одной и той же вершине).
2. Если в графе ровно две вершины с нечётной степенью, то эйлеров путь существует и начинается в одной из этих вершин, а заканчивается в другой.

Если в графе более двух вершин с нечётной степенью, эйлеров путь невозможен.

Проанализируем наш граф. Найдём степени каждой вершины:

• Почта: 5 тропинок (к домам 1, 3, 4, 6, 7). Степень $deg(П) = 5$ (нечётная).
• Дом 1: 3 тропинки (к Почте, домам 2, 7). Степень $deg(1) = 3$ (нечётная).
• Дом 2: 2 тропинки (к домам 1, 3). Степень $deg(2) = 2$ (чётная).
• Дом 3: 3 тропинки (к Почте, домам 2, 4). Степень $deg(3) = 3$ (нечётная).
• Дом 4: 3 тропинки (к Почте, домам 3, 5). Степень $deg(4) = 3$ (нечётная).
• Дом 5: 3 тропинки (к домам 4, 6, 7). Степень $deg(5) = 3$ (нечётная).
• Дом 6: 3 тропинки (к Почте, домам 5, 7). Степень $deg(6) = 3$ (нечётная).
• Дом 7: 4 тропинки (к Почте, домам 1, 5, 6). Степень $deg(7) = 4$ (чётная).

В данном графе шесть вершин имеют нечётную степень: Почта, дом 1, дом 3, дом 4, дом 5 и дом 6. Вершины с чётной степенью — дом 2 и дом 7.

По условию, почтальон начинает свой путь от Почты (стартовая вершина) и заканчивает его у дома Феди (конечная вершина). Для того чтобы такой путь существовал, Почта и дом Феди должны быть единственными двумя вершинами с нечётной степенью в графе. Все остальные (промежуточные) вершины должны иметь чётную степень.

Однако в нашей задаче целых шесть вершин имеют нечётную степень. Это противоречит теореме Эйлера. Следовательно, в графе, изображённом на рисунке, невозможно проложить маршрут, который бы начинался в одной точке, заканчивался в другой и проходил бы по каждой тропинке ровно один раз.

Это означает, что условия задачи противоречивы. Вероятнее всего, в условии или на рисунке допущена ошибка. При данных условиях определить дом Феди невозможно.

Ответ: На основании предоставленной схемы невозможно определить, в каком доме живёт Федя, так как описанный в задаче маршрут математически невозможен.

Поскольку, как было показано выше, в данном графе более двух вершин нечётной степени, эйлеров путь, который бы удовлетворял условиям задачи (пройти по каждой тропинке ровно один раз), не существует.

Таким образом, почтальон не мог проложить такой маршрут, который описан в задаче. Любая попытка построить такой маршрут приведёт либо к тому, что некоторые тропинки останутся не пройденными, либо к тому, что по каким-то тропинкам придётся пройти более одного раза.

Ответ: Маршрута, удовлетворяющего всем условиям задачи, не существует.