Районная олимпиада, 2018-2019 учебный год, 9 класс

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

Комментарий/решение

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