Задача про пять площадей на странице 17, ГДЗ по алгебре за 7 класс к учебнику Высоцкого часть 2
Давным-давно в одном богатом городе правил мудрый царь. Было в этом городе пять базарных площадей, но улицы были узкие, и телеги с товаром то и дело цеплялись друг за друга при встрече. При этом часто рассыпалось зерно, разбивались горшки, и купцы несли убытки. Тогда царь повелел соединить каждые две площади торговыми маршрутами так, чтобы никакие два маршрута не пересекались. Но ни один мудрец не смог начертить нужный план. Почему? Неужели мудрецы были недостаточно мудрыми? Попробуйте сами.
Обозначим площади \(A\), \(B\), \(C\), \(D\), \(E\). Площади — вершины графа, маршруты — его рёбра. Пар площадей 10, поэтому маршрутов тоже 10: \(AB\), \(BC\), \(CD\), \(DE\), \(EA\), \(AC\), \(AD\), \(BD\), \(BE\), \(CE\).
Предположим противное: все 10 маршрутов удалось проложить так, что никакие два из них не пересекаются.
Маршруты \(AB\), \(BC\), \(CD\), \(DE\) и \(EA\) образуют цикл \(ABCDEA\). Маршруты не пересекаются, поэтому этот цикл — замкнутая линия без самопересечений. Замкнутая линия без самопересечений делит плоскость на две части — внутреннюю и внешнюю, и линия, соединяющая точки разных частей, её пересекает. Остальные пять маршрутов — \(AC\), \(AD\), \(BD\), \(BE\) и \(CE\) — замкнутую линию не пересекают, поэтому каждый из них, кроме концов, лежит целиком во внутренней части или целиком во внешней. Если бы в каждой части лежало не больше двух из этих маршрутов, всего их было бы не больше четырёх. Значит, в одной из частей лежат не меньше трёх маршрутов.
Среди любых трёх из этих пяти маршрутов есть два без общих концов. Каждая площадь — конец ровно двух из пяти маршрутов: \(A\) — маршрутов \(AC\) и \(AD\), \(B\) — маршрутов \(BD\) и \(BE\), \(C\) — маршрутов \(AC\) и \(CE\), \(D\) — маршрутов \(AD\) и \(BD\), \(E\) — маршрутов \(BE\) и \(CE\). Если бы любые два из трёх маршрутов имели общий конец, то два из них выходили бы из одной площади, например \(AC\) и \(AD\) из площади \(A\). Третий маршрут из \(A\) не выходит, поэтому его общий конец с \(AC\) — площадь \(C\), а с \(AD\) — площадь \(D\), то есть это маршрут \(CD\). Но маршрут \(CD\) входит в цикл \(ABCDEA\), а не в число этих пяти. У любой другой площади так же: вторые концы двух её маршрутов — соседние площади цикла (\(D\) и \(E\) у площади \(B\), \(A\) и \(E\) у площади \(C\), \(A\) и \(B\) у площади \(D\), \(B\) и \(C\) у площади \(E\)).
Концы двух маршрутов без общих концов на замкнутой линии чередуются: между концами одного маршрута на каждой из двух дуг замкнутой линии лежит по одному концу другого. Например, концы \(A\) и \(C\) маршрута \(AC\) делят замкнутую линию на дуги \(ABC\) и \(CDEA\), и конец \(B\) маршрута \(BD\) лежит на первой дуге, а конец \(D\) — на второй. Маршрут \(AC\) делит свою часть плоскости на две: одна прилегает к дуге \(ABC\), другая — к дуге \(CDEA\). Поэтому маршрут \(BD\), проложенный в той же части плоскости, пересекает \(AC\). Так же устроены остальные пары маршрутов без общих концов: \(BD\) и \(CE\), \(CE\) и \(AD\), \(AD\) и \(BE\), \(BE\) и \(AC\).
Значит, два из маршрутов, лежащих в одной части плоскости, пересекаются. Это противоречит предположению. Значит, предположение неверно, и соединить каждые две площади так, чтобы никакие два маршрута не пересекались, нельзя. Мудрецы тут ни при чём: такого плана не существует.
Ответ: начертить такой план нельзя — два маршрута обязательно пересекутся.
Давным-давно в одном богатом городе правил мудрый царь. Было в этом городе пять базарных площадей, но улицы были узкие, и телеги с товаром то и дело цеплялись друг за друга при встрече. При этом часто рассыпалось зерно, разбивались горшки, и купцы несли убытки. Тогда царь повелел соединить каждые две площади торговыми маршрутами так, чтобы никакие два маршрута не пересекались. Но ни один мудрец не смог начертить нужный план. Почему? Неужели мудрецы были недостаточно мудрыми? Попробуйте сами.
Обозначим площади \(A\), \(B\), \(C\), \(D\), \(E\). Площади — вершины графа, маршруты — его рёбра: каждые две вершины соединены ребром. Пар площадей 10, поэтому маршрутов тоже 10: \(AB\), \(BC\), \(CD\), \(DE\), \(EA\), \(AC\), \(AD\), \(BD\), \(BE\), \(CE\). Царь требует, чтобы этот граф был плоским. Докажем, что это невозможно.
Предположим противное: все 10 маршрутов удалось проложить так, что никакие два из них не пересекаются.
Маршруты \(AB\), \(BC\), \(CD\), \(DE\) и \(EA\) образуют цикл \(ABCDEA\). Маршруты не пересекаются, поэтому этот цикл — замкнутая линия без самопересечений. Замкнутая линия без самопересечений делит плоскость на две части — внутреннюю и внешнюю, и линия, соединяющая точки разных частей, её пересекает. Остальные пять маршрутов — \(AC\), \(AD\), \(BD\), \(BE\) и \(CE\) — замкнутую линию не пересекают, поэтому каждый из них, кроме концов, лежит целиком во внутренней части или целиком во внешней. Если бы в каждой части лежало не больше двух из этих маршрутов, всего их было бы не больше четырёх. Значит, в одной из частей лежат не меньше трёх маршрутов.
Среди любых трёх из этих пяти маршрутов есть два без общих концов. Каждая площадь — конец ровно двух из пяти маршрутов: \(A\) — маршрутов \(AC\) и \(AD\), \(B\) — маршрутов \(BD\) и \(BE\), \(C\) — маршрутов \(AC\) и \(CE\), \(D\) — маршрутов \(AD\) и \(BD\), \(E\) — маршрутов \(BE\) и \(CE\). Если бы любые два из трёх маршрутов имели общий конец, то два из них выходили бы из одной площади, например \(AC\) и \(AD\) из площади \(A\). Третий маршрут из \(A\) не выходит, поэтому его общий конец с \(AC\) — площадь \(C\), а с \(AD\) — площадь \(D\), то есть это маршрут \(CD\). Но маршрут \(CD\) входит в цикл \(ABCDEA\), а не в число этих пяти. У любой другой площади так же: вторые концы двух её маршрутов — соседние площади цикла (\(D\) и \(E\) у площади \(B\), \(A\) и \(E\) у площади \(C\), \(A\) и \(B\) у площади \(D\), \(B\) и \(C\) у площади \(E\)).
Концы двух маршрутов без общих концов на замкнутой линии чередуются: между концами одного маршрута на каждой из двух дуг замкнутой линии лежит по одному концу другого. Например, концы \(A\) и \(C\) маршрута \(AC\) делят замкнутую линию на дуги \(ABC\) и \(CDEA\), и конец \(B\) маршрута \(BD\) лежит на первой дуге, а конец \(D\) — на второй. Маршрут \(AC\) делит свою часть плоскости на две: одна прилегает к дуге \(ABC\), другая — к дуге \(CDEA\). Поэтому маршрут \(BD\), проложенный в той же части плоскости, пересекает \(AC\). Так же устроены остальные пары маршрутов без общих концов: \(BD\) и \(CE\), \(CE\) и \(AD\), \(AD\) и \(BE\), \(BE\) и \(AC\).
Значит, два из маршрутов, лежащих в одной части плоскости, пересекаются. Это противоречит предположению. Значит, предположение неверно, и соединить каждые две площади так, чтобы никакие два маршрута не пересекались, нельзя. Мудрецы тут ни при чём: такого плана не существует.
Ответ: начертить такой план нельзя — два маршрута обязательно пересекутся.
