ВсОШ 2024, 11 класс, задача 7
В стране городов и пока нет дорог. Правительство наугад определяет стоимость строительства дороги (с двусторонним движением) между каждыми двумя городами, используя по разу все суммы от до талеров (все варианты равновероятны). Мэр каждого города выбирает самую дешёвую из возможных дорог, идущих из этого города, и она строится (это может быть взаимным желанием мэров обоих соединяемых городов или только одного из двух). После строительства этих дорог города оказываются разбиты на компонент связности (между городами одной компоненты связности можно добраться по построенным дорогам, возможно, с пересадками, а между городами разных компонент - нельзя). Найдите математическое ожидание случайной величины . (Ф. Петров)
Ответ. .
Решение. Дорогу, которую хотят строить сразу два мэра, назовём надёжной. Рассмотрим в каждой компоненте самую дешёвую дорогу . Тогда она является надёжной. Предположим, что в этой компоненте есть ещё одна надёжная дорога (ясно, что города , отличны от , ) и рассмотрим путь по дорогам от одного из городов , до одного из городов , - не умаляя общности, он имеет вид (города отличны от , , , , возможно, ). Тогда дорогу хочет строить мэр города (мэр города хочет строить ), дорогу - мэр города (мэр города хочет строить ) и так далее, мэр города хочет строить дорогу , а не - противоречие.
Итак, в каждой компоненте есть ровно одна надёжная дорога. Для каждой из пар городов , рассмотрим случайную величину , которая равна , если - надёжная дорога, и в противном случае. Из доказанного следует, что есть сумма по всем парам . Для данных , событие означает, что дорога - самая дешёвая из дорог, выходящих из или , так что вероятность такого события равна (из симметричности распределения цен эти дороги равноправны, так что каждая из них является самой дешёвой с вероятностью ). Значит, математическое ожидание равно , а математическое ожидание случайной величины равно сумме этих математических ожиданий по всем парам, то есть .