Закл 2024

Дорогу, которую хотят строить сразу два мэра, назовём надёжной. Рассмотрим в каждой компоненте самую дешёвую дорогу Тогда она является надёжной. Предположим, что в этой компоненте есть ещё одна надёжная дорога (ясно, что города отличны от ) и рассмотрим путь по дорогам от одного из городов до одного из городов — не умаляя общности, он имеет вид (города отличны от возможно, ). Тогда дорогу хочет строить мэр города (мэр города хочет строить ), дорогу — мэр города (мэр города хочет строить ) и так далее, мэр города хочет строить дорогу а не — противоречие.

Итак, в каждой компоненте есть ровно одна надёжная дорога. Для каждой из пар городов рассмотрим случайную величину которая равна если — надёжная дорога, и 0 в противном случае. Из доказанного следует, что есть сумма по всем парам Для данных событие означает, что дорога — самая дешёвая из дорог, выходящих из или так что вероятность такого события равна (из симметричности распределения цен эти дороги равноправны, так что каждая из них является самой дешёвой с вероятностью ). Значит, математическое ожидание равно а математическое ожидание случайной величины равно сумме этих математических ожиданий по всем парам, то есть