Олимпиадная задача: максимальная сумма на дугах между разноцветными точками на окружности
Задача
По окружности отметили 40 красных, 30 синих и 20 зеленых точек. На каждой дуге между соседними красной и синей точками поставили цифру 1, на каждой дуге между соседними красной и зеленой – цифру 2, а на каждой дуге между соседними синей и зеленой – цифру 3. (На дугах между одноцветными точками поставили 0.) Найдите максимальную возможную сумму поставленных чисел.
Решение
Поставим в каждой красной точке число 0, в каждой синей – 1, а в каждой зеленой – 2. Тогда каждое число на разноцветной дуге равно сумме чисел в ее концах, а каждое число на одноцветной дуге меньше суммы в ее концах. Значит, сумма чисел на дугах не превосходит удвоенной суммы чисел в точках, причем равенство достигается, когда все дуги – разноцветные. Сумма чисел в точках равна40· 0+30· 1+20· 2=70, поэтому сумма чисел на дугах не больше 140.
Осталось привести пример, когда эта оценка достигается (то есть когда все дуги разноцветны). Расставим сначала по кругу 40 красных точек; затем вставим между соседними красными по точке другого цвета– 30 синих и 10 зеленых. Наконец, вставим оставшиеся 10 зеленых на дуги между красными и синими точками (таких дуг образовалось 60, поэтому их хватит).
Ответ
Чтобы оставлять комментарии, войдите или зарегистрируйтесь