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