Question

Помогите В стране N городов. Между любыми двумя городами имеется прямое сообщение самолетом или пароходом. Докажите, что, пользуясь лишь каким-то одним видом транспорта, из любого города можно попасть в любой другой (быть может, с пересадками).​

Answer 1

Ответ:Утверждение доказано.

Пошаговое объяснение:Будем доказывать утверждение индукцией по n – числу городов. Пусть n=2. Тогда утверждение очевидно.   Пусть утверждение имеет место для n=k городов. Пусть, для определённости, существует авиасообщение между всеми k городами.   Добавим ещё один город. Если он соединён авиасообщением, хотя бы с одним из k городов, то все k+1 городов соединены авиасообщением. Если же нет авиасообщения ни с одним из k городов, то отсюда следует, что (k+1)-й город соединён параходнымным сообщением с каждым из k предыдущих городов. Следовательно,  все k+1 городов соединены друг с другом параходным сообщением.  Утверждение доказано.

Answer 2

Для доказательства этого утверждения воспользуемся методом математической индукции.

Предположим, что в стране N городов любые два города можно соединить прямым сообщением только одним видом транспорта. Рассмотрим случай N+1 города.

Выберем произвольный город A из этих N+1 городов. По предположению индукции, из города A можно добраться в любой другой город только одним видом транспорта. Теперь рассмотрим оставшиеся N городов. Если все они соединены с городом A только одним видом транспорта, то утверждение доказано для N+1 города.

Предположим, что существует город B из оставшихся N городов, который не соединен с городом A прямым сообщением одним видом транспорта. Рассмотрим путь от города A к городу B с использованием другого города C. По предположению индукции, из города A можно добраться в город C только одним видом транспорта. Аналогично, из города C можно добраться в город B только одним видом транспорта. Таким образом, существует путь от города A к городу B через город C, который использует только один вид транспорта для каждого участка пути.

Таким образом, независимо от того, какой город выбран в качестве отправной точки, пользуясь только одним видом транспорта, можно добраться в любой другой город, возможно с пересадками через другие города.