А мы уже и ответ принесли!
Оказывается, невозможно провести от каждого домика по одной тропинке к погребу, колодцу и навесу так, чтобы ни одна из этих девяти тропинок не пересекалась с другой.
Ход решения 🔍
Обозначим три домика за A, B и C, а погреб, колодец и навес как P, K и N, соответственно (как на второй карточке). Пусть дома A и B соединены с каждым из трёх объектов непересекающимися тропинками. Заметим, что в этом случае тропинки разобьют плоскость на несколько областей, а если быть более точным – на 3!
Например, тропинки AP и AK вместе с тропинками BP и BK образуют замкнутый контур ограниченной области. Аналогично, AK и AN вместе с BK и BN образуют замкнутый контур другой ограниченной области. Третья и неограниченная область — это всё, что остаётся.
Таким образом, дом C обязательно окажется в одной из этих областей, каким бы образом мы ни соединяли тропинки.
ㅤㅤㅤㅤㅤㅤㅤㅤ
Пример ⬇️
Рассмотрим ситуацию, когда он оказался в первой области APKB. Навес N лежит вне этой области, а значит тропинка CN будет обязана пересечь контур области, т.е. одну из уже проложенных тропинок.
Точно так же в случаях если C попала в какую-то другую область — всегда найдётся один из объектов (P, K или N), который не будет лежать внутри этой области, а значит соответствующая тропинка пересечет её контур.
Несмотря на кажущуюся простоту задачи и достаточно быстро напрашивающийся ответ, строгое доказательство не назовешь очевидным, так как его аргументированное обоснование несёт уже вполне топологический характер.
Задачу можно также решить, переведя её на язык графов:
Если каждый из объектов представить в виде точек, то есть вершин графа, а тропинки – рёбер графа, то по сути задача спрашивает, может ли каждая из трёх вершин одной группы быть соединена со всеми тремя вершинами другой группы без пересечений.
Известно, что для любого плоского (то есть лежащего на плоскости) двудольного графа (то есть графа, который можно нарисовать без пересечений) выполняется неравенство
E ≤ 2V−4
где V — число вершин, E — число рёбер графа. У нас V=6, E=9. Тогда для нашего графа должно быть E ≤ 2⋅6−4 = 8, но 9 > 8. Получили противоречие.
Кстати, такой граф, как наш, обозначают как K₃,₃. Обозначение Kₙ означает полный граф на n вершинах: каждая вершина соединена с каждой. Мы только что доказали, что двудольный граф K₃,₃ не может быть плоским. Это один из двух знаменитых минимальных неплоских графов, второй — граф K₅. Именно эти два графа появляются в знаменитой теореме Понтрягина-Куратовского:
🔄Граф можно нарисовать на плоскости без пересечений тогда и только тогда, когда он не содержит «спрятанного» K₅ или K₃,₃🔄
Как вам решение? Было сложно или элементарно?
⚡️ — я справился в два счёта
🗿 — вот бы побегать по этим тропинкам, а не задачи решать...
#задача