Разделы 
Дополнительно
Задача по математике - 3603
2019-06-12 
В некотором городе для любых трех перекрестков $A, B$ и $C$ есть путь, ведущий из $A$ в $B$ и не проходящий через $C$. Докажите, что с любого перекрестка на любой другой ведут по крайней мере два непересекающихся пути (перекресток - место, где сходятся по крайней мере две улицы; в городе не меньше двух перекрестков).
Решение:
Назовем длиной пути число отрезков, из которых он состоит. Пусть $n$ - длина кратчайшего пути из $A$ в $B$. Докажем утверждение задачи индукцией по $n$.
При $n - 1$ кроме кратчайшего пути $AB$ существует путь, идущий из $A$ в перекресток $C \neq A$, удаленный от $B$ на 1, и не проходящий через $В$.
Пусть $n > 1$, $D$ - ближайший к $A$ перекресток на кратчайшем пути из $A$ в $B$. По предположению индукции, существует два непересекающихся пути $p$ и $q$ из $D$ и $В$. Будем идти из $A$ по пути $l$, не проходящем через $D$. Если этот путь не пересекается с путями $p$ и $q$, то все доказано. Если же он впервые пересекает, скажем, путь $p$, то дальше следует идти по $p$ прямо в $B$. Полученный путь не пересекается с $q$.
В некотором городе для любых трех перекрестков $A, B$ и $C$ есть путь, ведущий из $A$ в $B$ и не проходящий через $C$. Докажите, что с любого перекрестка на любой другой ведут по крайней мере два непересекающихся пути (перекресток - место, где сходятся по крайней мере две улицы; в городе не меньше двух перекрестков).
Решение:
Назовем длиной пути число отрезков, из которых он состоит. Пусть $n$ - длина кратчайшего пути из $A$ в $B$. Докажем утверждение задачи индукцией по $n$.
При $n - 1$ кроме кратчайшего пути $AB$ существует путь, идущий из $A$ в перекресток $C \neq A$, удаленный от $B$ на 1, и не проходящий через $В$.
Пусть $n > 1$, $D$ - ближайший к $A$ перекресток на кратчайшем пути из $A$ в $B$. По предположению индукции, существует два непересекающихся пути $p$ и $q$ из $D$ и $В$. Будем идти из $A$ по пути $l$, не проходящем через $D$. Если этот путь не пересекается с путями $p$ и $q$, то все доказано. Если же он впервые пересекает, скажем, путь $p$, то дальше следует идти по $p$ прямо в $B$. Полученный путь не пересекается с $q$.
