СПбГУ 2025, 9 класс, задача 5
( баллов) В стране городов. Между некоторыми городами построены дороги с односторонним движением, а между городами может быть несколько дорог в разных направлениях. Для любых двух городов и можно добраться (возможно через какие-то другие города) либо из в , либо из в , либо из в и из в . Для какого наименьшего можно утверждать, что всегда можно так построить новых дорог, что в любой город можно будет добраться из любого другого города?
Ответ: при .
Решение. Сначала приведем пример, когда одну дорогу придется построить. Занумеруем города числами от до . Пусть из каждого города есть дорога в город (конечно ). Условие задачи выполнено, но из второго города в первый не добраться. Поэтому нужно построить хотя бы одну дорогу.
Докажем теперь, что всегда можно построить одну дорогу так, что из любого города можно будет попасть в любой другой. Рассмотрим город , из которого можно приехать в наибольшее количество городов страны. Предположим, что существует город , в который не приехать из города . По условию тогда из города можно добраться до города . Но тогда из города можно приехать и во все города, в которые можно было приехать из города , а еще можно добраться и до города . Это противоречит выбору города , как города, из которого можно приехать в наибольшее количество городов. Таким образом, из города можно добраться во все города страны.
Аналогично, существует такой город , в который можно приехать из любого города страны. Тогда если построить дорогу из и , то для любых двух городов и появится способ добраться из в . А именно, нужно сначала приехать из в , затем по новой дороге переместиться из в и наконец из приехать в .