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