Разделы 
Дополнительно
Задача по математике - 10071
2022-12-06 
В некоторой стране между любыми двумя городами имеется непосредственное железнодорожное сообщение, но только в одном направлении. Доказать, что существует такой город, в который из любого другого города можно попасть, проезжая не более чем через один промежуточный город.
Решение:
Назовем «соседями города $N$» те города, из которых можно попасть в $N$ непосредственно, а «близкими к $N$» - те города, из которых можно попасть в $N$, проезжая не более чем через один промежуточный город. Пользуясь методом математической индукции, докажем, что утверждение задачи справедливо (т. е. что найдется город $N$, к которому остальные близки), каково бы ни было число городов в стране. Для стран, в которых всего два города, утверждение очевидно. Допустим, что утверждение задачи доказано для стран, в которых $n$ городов, и докажем его для страны, в которой $n + 1$ городов. Нанесем на схему дороги, соединяющие какие-нибудь $n$ городов. Эта сеть дорог удовлетворяет условию задачи и, по предположению индукции, существует такой город A, что остальные $n - 1$ городов близки к A, т. е. каждый из них является соседом A или соседом одного из соседей A. Если ($n + 1$)-й : город В тоже близок к A, то все города страны близки к A. Если это не так, то, как видно из условия задачи, город A и все его соседи являются соседями В.
Каждый из остальных городов является соседом одного из соседей А и, значит, близок к В. В этом случае все города страны близки к В. Все доказано.
В некоторой стране между любыми двумя городами имеется непосредственное железнодорожное сообщение, но только в одном направлении. Доказать, что существует такой город, в который из любого другого города можно попасть, проезжая не более чем через один промежуточный город.
Решение:
Назовем «соседями города $N$» те города, из которых можно попасть в $N$ непосредственно, а «близкими к $N$» - те города, из которых можно попасть в $N$, проезжая не более чем через один промежуточный город. Пользуясь методом математической индукции, докажем, что утверждение задачи справедливо (т. е. что найдется город $N$, к которому остальные близки), каково бы ни было число городов в стране. Для стран, в которых всего два города, утверждение очевидно. Допустим, что утверждение задачи доказано для стран, в которых $n$ городов, и докажем его для страны, в которой $n + 1$ городов. Нанесем на схему дороги, соединяющие какие-нибудь $n$ городов. Эта сеть дорог удовлетворяет условию задачи и, по предположению индукции, существует такой город A, что остальные $n - 1$ городов близки к A, т. е. каждый из них является соседом A или соседом одного из соседей A. Если ($n + 1$)-й : город В тоже близок к A, то все города страны близки к A. Если это не так, то, как видно из условия задачи, город A и все его соседи являются соседями В.
Каждый из остальных городов является соседом одного из соседей А и, значит, близок к В. В этом случае все города страны близки к В. Все доказано.
