Вероятностный метод (усреднение)
Ошибка.
Попробуйте повторить позже
Докажите, что существует такой полный ориентированный граф с 
вершинами, что в нём не менее 
гамильтоновых (то есть
проходящих по всем вершинам ровно по одному разу) путей.
Рассмотрим случайный турнир 
на множестве вершин 
где ориентация каждой дуги определяется независимым
подбрасыванием монеты. 
— множество всех перестановок вершин графа.
- 1.
-
Для каждой перестановки
определим индикаторную случайную величину:
Математическое ожидание
равно вероятности того, что все 
дуг пути направлены корректно:
![E [ξσ]=2n1−1.](/api/latex-service/v1/GetSession/252902/index-48d42b3aa622fbc96dc14681adf27937.svg)
- 2.
-
Обозначим через
общее количество гамильтоновых путей в турнире 
Тогда математическое ожидание:
![∑ --1- -n!-
E [ξ]=σ∈SnE [ξσ]=n!⋅2n−1 = 2n−1.](/api/latex-service/v1/GetSession/252902/index-fb237575e7c09465ee3ae68e26077556.svg)
- 3.
-
Поскольку среднее значение
равно 
существует хотя бы один турнир 
для которого:
![-n!-
ξ(T0)≥ E[ξ]= 2n−1.](/api/latex-service/v1/GetSession/252902/index-e7b2a9502e2b6344f4941e933cda091f.svg)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
