Задача 109891

Темы:    [ Раскраски ] [ Системы точек ] [ Разбиения на пары и группы; биекции ] [ Подсчет двумя способами ] [ Покрытия ]

Сложность: 5 Классы: 8,9,10,11

Условие

Автор: Изместьев И.В.

На прямой через равные промежутки отмечены 1996 точек. Петя раскрашивает половину из них в красный цвет, а остальные – в синий. Затем Вася разбивает их на пары красная-синяя так, чтобы сумма расстояний между точками в парах была максимальной. Докажите, что этот максимум не зависит от того, какую раскраску сделал Петя.

Решение

Докажем, что Вася достигнет максимума, если поступит следующим образом: в первой паре – первая слева красная точка и первая справа синяя, во второй паре – вторая слева красная и вторая справа синяя, и т.д.

Для этого соединим точки в каждой паре отрезком и сосчитаем, сколько из этих отрезков покрывают отрезок A_k A_{k +} 1 (см. рис.) . Пусть k 998 , и среди точек A1 , A_k l красных. Тогда справа от точки A_k не менее l синих точек (если меньше, то среди A1 , A_k больше, чем 998 - l синих, и k > 998) . Следовательно, все отрезки, красные концы которых находятся среди точек A1 , A_k , покрывают отрезок A_k A_{k +} 1 . То же верно с заменой красных концов на синие. То есть отрезок A_k A_{k +} 1 покрыт k отрезками, а большим числом он и не может быть покрыт. Аналогично, при k>998 отрезок A_kA_k+1 покрыт 1996-k отрезками, и не может быть покрыт большим числом отрезков. Следовательно, сумма, достигнутая Васей, равна 1 + 2 +...+ 997 + 998 + 997 +...+ 2 + 1 = 9982 и не зависит от раскраски.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1996
Этап
Вариант	4
Класс
Класс	10
задача
Номер	96.4.10.8