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