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

709. Придумайте свои фигуры, которые можно нарисовать, не отрывая карандаша от бумаги и не проводя по линии дважды.

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

Ключевым понятием здесь является «степень» вершины — это количество линий, которые в ней сходятся. Вершина называется нечетной, если ее степень нечетна (1, 3, 5, ...), и четной, если ее степень четна (2, 4, 6, ...). Степень вершины $v$ можно обозначить как $deg(v)$.

Правило, которое определяет, можно ли нарисовать фигуру одним росчерком, гласит:
1. Если у фигуры нет нечетных вершин (т.е. все вершины четные), ее можно нарисовать одним росчерком. Начать движение можно из любой точки, и оно закончится в той же самой точке.
2. Если у фигуры ровно две нечетные вершины, ее также можно нарисовать одним росчерком. Но начинать нужно в одной из нечетных вершин, а заканчивать — в другой.
3. Если у фигуры больше двух нечетных вершин (например, четыре), то нарисовать ее по заданным правилам невозможно.

Основываясь на этом, придумаем несколько фигур.

Домик
Простая фигура, состоящая из квадрата («стены») и треугольника наверху («крыша»), у которых одна сторона общая.
У этой фигуры 5 вершин:
- Две нижние вершины квадрата: в каждой сходится по 2 линии, $deg(v) = 2$. Это четные вершины.
- Верхняя вершина крыши: в ней тоже сходятся 2 линии, $deg(v) = 2$. Это четная вершина.
- Две верхние вершины квадрата, которые также являются основанием крыши: в каждой из них сходится по 3 линии (сторона квадрата, общая сторона с крышей, сторона крыши). $deg(v) = 3$. Это нечетные вершины.
Фигура имеет ровно две нечетные вершины.
Ответ: Фигуру «Домик» можно нарисовать, так как у нее две нечетные вершины.

Пятиконечная звезда
Классическая пятиконечная звезда (пентаграмма), нарисованная пятью отрезками.
У этой фигуры 10 вершин:
- 5 внешних вершин («лучи» звезды): в каждой из них сходятся по 2 линии. Все они четные, $deg(v) = 2$.
- 5 внутренних вершин (точки пересечения линий): в каждой из них сходится по 4 линии. Все они тоже четные, $deg(v) = 4$.
В этой фигуре все вершины четные.
Ответ: Фигуру «Пятиконечная звезда» можно нарисовать, так как у нее нет нечетных вершин.

Конверт
Фигура, похожая на почтовый конверт. Состоит из квадрата и «крышки» в виде треугольника, построенного на верхней стороне квадрата. Важно: диагонали внутри квадрата не проводим.
Это та же самая фигура, что и «Домик», только повернутая. У нее также 5 вершин.
- Две вершины на основании квадрата: $deg(v) = 2$ (четные).
- «Носик» конверта (вершина треугольника): $deg(v) = 2$ (четная).
- Две вершины, где «крышка» соединяется с квадратом: $deg(v) = 3$ (нечетные).
Фигура имеет ровно две нечетные вершины. (Примечание: если бы в этом конверте были проведены диагонали, то все 4 угла квадрата стали бы нечетными, и его нельзя было бы нарисовать).
Ответ: Фигуру «Конверт» (без диагоналей) можно нарисовать, так как у нее две нечетные вершины.

Снежинка
Более сложная фигура: правильный шестиугольник, на каждой стороне которого снаружи достроен треугольник.
У этой фигуры 12 вершин:
- 6 вершин исходного шестиугольника: в каждой из них сходятся 4 линии (две стороны шестиугольника и две стороны пристроенных треугольников). Все они четные, $deg(v) = 4$.
- 6 внешних вершин (вершины треугольников): в каждой из них сходятся 2 линии. Все они тоже четные, $deg(v) = 2$.
В этой фигуре все вершины четные.
Ответ: Фигуру «Снежинка» можно нарисовать, так как у нее нет нечетных вершин.

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

В каком доме живёт Федя?

Каков мог быть маршрут почтальона?

Рис. 144

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

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

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

Проанализируем нашу схему. Подсчитаем количество тропинок (степень вершины) для каждого объекта:

• Почта: 4 тропинки (к домам 1, 3, 4, 6) — чётная вершина.
• Дом 1: 3 тропинки (к Почте, 2, 7) — нечётная вершина.
• Дом 2: 2 тропинки (к домам 1, 3) — чётная вершина.
• Дом 3: 3 тропинки (к Почте, 2, 4) — нечётная вершина.
• Дом 4: 3 тропинки (к Почте, 3, 5) — нечётная вершина.
• Дом 5: 3 тропинки (к домам 4, 6, 7) — нечётная вершина.
• Дом 6: 3 тропинки (к Почте, 5, 7) — нечётная вершина.
• Дом 7: 3 тропинки (к домам 1, 5, 6) — нечётная вершина.

В нашей схеме 6 нечётных вершин (дома 1, 3, 4, 5, 6, 7) и 2 чётные (Почта, дом 2). Поскольку в графе больше двух нечётных вершин, пройти по всем тропинкам ровно один раз в рамках одного непрерывного маршрута невозможно. Это означает, что в условии задачи содержится противоречие.

Тем не менее, такие задачи часто встречаются в учебниках и предполагают логическое рассуждение на основе имеющихся правил, даже если они приводят к парадоксу.

В каком доме живёт Федя?

Если бы такой маршрут был возможен, то дом Феди, как конечная точка пути, должен был бы быть нечётной вершиной. Нечётными вершинами являются дома 1, 3, 4, 5, 6, 7. Таким образом, Федя должен жить в одном из этих домов. Однако логичной начальной точкой для почтальона является Почта, которая является чётной вершиной. Это нарушает правило, согласно которому начало и конец пути должны быть нечётными вершинами (если они не совпадают).

Учитывая, что задача дана в учебнике, возможно, она содержит ошибку или является задачей-шуткой, чтобы продемонстрировать невозможность такой ситуации. Если всё же необходимо дать ответ, то он будет основан на единственном твёрдом правиле: конечная точка пути должна быть нечётной вершиной.

Ответ: Федя должен жить в доме с нечётным числом тропинок. Таких домов шесть: 1, 3, 4, 5, 6, 7. Поскольку условие задачи не позволяет однозначно выбрать один из них и в целом является математически противоречивым, указать один конкретный дом невозможно.

Каков мог быть маршрут почтальона?

Так как непрерывный маршрут, удовлетворяющий условиям, невозможен, составить его нельзя. Математически доказано, что для обхода всех рёбер этого графа потребуется как минимум $6 / 2 = 3$ отдельных непрерывных маршрута. Например, один маршрут мог бы соединять дома 1 и 3, второй — 4 и 5, а третий — 6 и 7. Но для перемещения между этими маршрутами почтальону пришлось бы либо летать, либо проходить по некоторым тропинкам дважды, что противоречит условию.

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

711. Экскурсоводу нужно выбрать маршрут по залам музея так, чтобы обойти все залы, не проходя ни через одну дверь дважды. Где нужно начать и где закончить осмотр? Найдите один из возможных маршрутов (рис. 145).

Рис. 145

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

Сначала определим количество дверей в каждом зале, что в теории графов называется степенью вершины:

• Зал 1: 2 двери (четная степень)
• Зал 2: 3 двери (нечетная степень)
• Зал 3: 3 двери (нечетная степень)
• Зал 4: 2 двери (четная степень)
• Зал 5: 3 двери (нечетная степень)
• Зал 6: 4 двери (четная степень)
• Зал 7: 4 двери (четная степень)
• Зал 8: 3 двери (нечетная степень)
• Зал 9: 2 двери (четная степень)
• Зал 10: 3 двери (нечетная степень)
• Зал 11: 3 двери (нечетная степень)
• Зал 12: 2 двери (четная степень)

Мы видим, что есть шесть залов с нечетным количеством дверей: 2, 3, 5, 8, 10 и 11.

Где нужно начать и где закончить осмотр?

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

Однако в задаче требуется обойти все *залы*, а не все *двери*. Формулировка вопроса "Где нужно начать и где закончить?" указывает на то, что начальная и конечная точки обладают особыми свойствами. В задачах такого типа этими особыми точками как раз и являются вершины с нечетной степенью. Поэтому следует выбрать для начала и конца маршрута два из шести залов с нечетным числом дверей.

Ответ: Начать осмотр нужно в одном из залов с нечетным количеством дверей (например, в зале 2, 3, 5, 8, 10 или 11) и закончить осмотр в другом зале с нечетным количеством дверей.

Найдите один из возможных маршрутов

Выберем в качестве начальной точки зал №2, а в качестве конечной — зал №11 (оба имеют по 3 двери). Можно построить следующий маршрут, который удовлетворяет всем условиям задачи:

2 → 1 → 5 → 9 → 10 → 6 → 7 → 3 → 4 → 8 → 12 → 11

Этот маршрут проходит через все 12 залов и не использует ни одну дверь дважды. Он начинается в зале с нечетным числом дверей и заканчивается в другом зале с нечетным числом дверей.

Ответ: Один из возможных маршрутов: 2 → 1 → 5 → 9 → 10 → 6 → 7 → 3 → 4 → 8 → 12 → 11.

712. Задача Л. Эйлера. Можно ли поочерёдно обойти все семь мостов г. Кёнигсберга (ныне Калининград), соединяющих районы этого города с островами на реке Прегель (рис. 146), проходя по каждому мосту только один раз?

р. Прегель

Рис. 146

Эта классическая задача, известная как «Задача о семи мостах Кёнигсберга», была решена великим математиком Леонардом Эйлером в 1736 году и послужила рождению новой области математики — теории графов. Для её решения необходимо представить карту города в виде математической модели — графа.

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

Обозначим вершины графа, соответствующие участкам суши на рисунке:
А — Северный берег (верхний);
Б — Южный берег (нижний);
В — Западный остров (левый);
Г — Восточный остров (правый).

Теперь посчитаем количество мостов (рёбер), соединяющих эти участки суши:
- Между Северным берегом (А) и Западным островом (В) — 2 моста.
- Между Южным берегом (Б) и Западным островом (В) — 2 моста.
- Между Западным островом (В) и Восточным островом (Г) — 1 мост.
- Между Северным берегом (А) и Восточным островом (Г) — 1 мост.
- Между Южным берегом (Б) и Восточным островом (Г) — 1 мост.

Вопрос задачи сводится к следующему: можно ли обойти все рёбра этого графа, пройдя по каждому из них ровно один раз? Такой путь называется Эйлеровым путём.

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

Посчитаем степень каждой вершины в нашей задаче:
- Степень вершины А (Северный берег) = $2$ (к острову В) $+ 1$ (к острову Г) $= 3$ (нечётная).
- Степень вершины Б (Южный берег) = $2$ (к острову В) $+ 1$ (к острову Г) $= 3$ (нечётная).
- Степень вершины В (Западный остров) = $2$ (к берегу А) $+ 2$ (к берегу Б) $+ 1$ (к острову Г) $= 5$ (нечётная).
- Степень вершины Г (Восточный остров) = $1$ (к берегу А) $+ 1$ (к берегу Б) $+ 1$ (к острову В) $= 3$ (нечётная).

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

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