Задача про три дома и три колодца на странице 18, ГДЗ по алгебре за 7 класс к учебнику Высоцкого часть 2
В одном селе было три колодца, но один-два то и дело пересыхали. Три соседа решили, что каждый из них может пользоваться любым из трёх колодцев, но каждый должен протоптать от своего дома к каждому колодцу три отдельные тропинки. Хотели даже сделать так, чтобы никакие две тропинки не пересекались. Но не смогли. Почему?
Обозначим дома Д1, Д2, Д3, а колодцы К1, К2, К3. От каждого дома к каждому колодцу ведёт своя тропинка — всего \(3 \cdot 3 = 9\) тропинок. Дома и колодцы — вершины графа, тропинки — его рёбра.
Предположим противное: все 9 тропинок удалось протоптать так, что никакие две из них не пересекаются.
Тропинки Д1К1, К1Д2, Д2К2, К2Д3, Д3К3 и К3Д1 образуют цикл Д1К1Д2К2Д3К3Д1. Тропинки не пересекаются, поэтому этот цикл — замкнутая линия без самопересечений. Замкнутая линия без самопересечений делит плоскость на две части — внутреннюю и внешнюю, и линия, соединяющая точки разных частей, её пересекает. Остальные три тропинки — Д1К2, Д2К3 и Д3К1 — замкнутую линию не пересекают, поэтому каждая из них, кроме концов, лежит целиком во внутренней части или целиком во внешней. Три тропинки приходятся на две части, значит, две из них лежат в одной части.
Концы любых двух из этих трёх тропинок на замкнутой линии чередуются: между концами одной тропинки на каждой из двух дуг замкнутой линии лежит по одному концу другой. Концы Д1 и К2 тропинки Д1К2 делят замкнутую линию на дуги Д1К1Д2К2 и К2Д3К3Д1. Тропинка Д1К2 делит свою часть плоскости на две: одна прилегает к дуге Д1К1Д2К2, другая — к дуге К2Д3К3Д1. Концы Д2 и К3 тропинки Д2К3 лежат на разных дугах, поэтому тропинка Д2К3, проложенная в той же части плоскости, пересекает Д1К2. Так же концы Д3 и К1 тропинки Д3К1 лежат на разных дугах между Д2 и К3, а концы Д1 и К2 тропинки Д1К2 — на разных дугах между Д3 и К1.
Значит, две тропинки, лежащие в одной части плоскости, пересекаются. Это противоречит предположению. Значит, предположение неверно, и протоптать 9 тропинок так, чтобы никакие две из них не пересекались, нельзя.
Ответ: проложить тропинки без пересечений нельзя — две из них обязательно пересекутся.
В одном селе было три колодца, но один-два то и дело пересыхали. Три соседа решили, что каждый из них может пользоваться любым из трёх колодцев, но каждый должен протоптать от своего дома к каждому колодцу три отдельные тропинки. Хотели даже сделать так, чтобы никакие две тропинки не пересекались. Но не смогли. Почему?
Обозначим дома Д1, Д2, Д3, а колодцы К1, К2, К3. От каждого дома к каждому колодцу ведёт своя тропинка — всего \(3 \cdot 3 = 9\) тропинок. Дома и колодцы — вершины графа, тропинки — его рёбра: каждое ребро соединяет дом с колодцем. Докажем, что проложить все 9 тропинок без пересечений нельзя.
Предположим противное: все 9 тропинок удалось протоптать так, что никакие две из них не пересекаются.
Тропинки Д1К1, К1Д2, Д2К2, К2Д3, Д3К3 и К3Д1 образуют цикл Д1К1Д2К2Д3К3Д1. Тропинки не пересекаются, поэтому этот цикл — замкнутая линия без самопересечений. Замкнутая линия без самопересечений делит плоскость на две части — внутреннюю и внешнюю, и линия, соединяющая точки разных частей, её пересекает. Остальные три тропинки — Д1К2, Д2К3 и Д3К1 — замкнутую линию не пересекают, поэтому каждая из них, кроме концов, лежит целиком во внутренней части или целиком во внешней. Три тропинки приходятся на две части, значит, две из них лежат в одной части.
Концы любых двух из этих трёх тропинок на замкнутой линии чередуются: между концами одной тропинки на каждой из двух дуг замкнутой линии лежит по одному концу другой. Концы Д1 и К2 тропинки Д1К2 делят замкнутую линию на дуги Д1К1Д2К2 и К2Д3К3Д1. Тропинка Д1К2 делит свою часть плоскости на две: одна прилегает к дуге Д1К1Д2К2, другая — к дуге К2Д3К3Д1. Концы Д2 и К3 тропинки Д2К3 лежат на разных дугах, поэтому тропинка Д2К3, проложенная в той же части плоскости, пересекает Д1К2. Так же концы Д3 и К1 тропинки Д3К1 лежат на разных дугах между Д2 и К3, а концы Д1 и К2 тропинки Д1К2 — на разных дугах между Д3 и К1.
Значит, две тропинки, лежащие в одной части плоскости, пересекаются. Это противоречит предположению. Значит, предположение неверно, и протоптать 9 тропинок так, чтобы никакие две из них не пересекались, нельзя.
Ответ: проложить тропинки без пересечений нельзя — две из них обязательно пересекутся.
