Математикадан аудандық олимпиада, 2018-2019 оқу жылы, 9 сынып

Бір елде $N$ қала бар. Әрбір екі қала тіке қатынас жолмен — ұшақпен, немесе кемемен жалғасқан. Көліктің қандай да бір түрін ғана пайдаланып, осы елдің кез келген қаласынан кез келген қаласына (мүмкін, ауысып отыру арқылы) жетуге болатынын дәлелдеңдер.

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

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