Вероятностный метод (усреднение)
Ошибка.
Попробуйте повторить позже
Рассмотрим двудольный граф 
с 
вершинами. Пусть для каждой вершины 
задан список 
из более чем 
цветов. Докажите, что существует правильная раскраска вершин графа 
приписывающая каждой вершине 
цвет из ее списка
Подсказка 1
Как можно покрасить двудольный граф правильно? Вообще достаточно двух цветов, одну долю можно покрасить в первый цвет, а другую во второй. Но у нас цветов больше, как быть? Можно все цвета распределить на 2 группы. Как можно это сделать?
Подсказка 2
Рассмотрите все разбиения цветов на 2 группы. Когда разбиение плохое? Только тогда, когда все цвета какой-то вершины попали в другую группу. С какой вероятностью это произошло?
Пусть 
— множество всех цветов в наборах. Рассморим всевозможные разбиения 
на 
непустые группы: первую и
вторую. Тогда если удастся найти разбиение, такое что у всех вершин из первой доли будет цвет из первой группы, а у
второй — из второй, то мы сможем выбрать цвета правильным образом. Далее будем доказывать, что такое разбиение
существует.
Очевидно, что каждый цвет побывает в первой и второй группе поровну раз, поэтому вероятность того, что цвет в определенной группе
составляет 
Пусть какое-то разбиение не подошло, значит, существует вершина, все цвета которой попали в другую группу, вероятность
такого события составляет 
где 
— количество цветов в списке вершины. В силу того, что список состоит более чем из 
цветов,
то данная вероятность строго меньше 
Суммируя по всем вершинам, получим число меньшее единицы, значит, существует правильная
раскраска вершин графа 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
