Разделы 
Дополнительно
Задача по математике - 1492
2019-01-19 
На прямой через равные промежутки отмечены 1996 точек. Петя раскрашивает половину из них в красный цвет, а остальные - в синий. Затем Вася разбивает их на пары «красная»-«синяя» так, чтобы сумма расстояний между точками в парах была максимальной. Докажите, что этот максимум не зависит от того, какую раскраску сделал Петя.
Решение:
Докажем, что Вася достигнет максимума, если поступит следующим образом: в первой паре - первая слева красная точка и первая справа синяя, во второй паре - вторая слева красная и вторая справа синяя, и т. д.
Для этого соединим точки в каждой паре отрезком и сосчитаем, сколько из этих отрезков покрывают отрезок $A_kA_{k+1}$ (рис.). Пусть $k \leq 998$, и среди точек $A_1,\cdots , A_k \: l$ красных. Тогда справа от точки $A_k$ не менее $l$ синих точек (если меньше, то среди $A_1,\cdots, A_k$ больше, чем $998 - l$ синих, и $k > 998$). Следовательно, все отрезки, красные концы которых находятся среди точек $A_1, \cdots, A_k$, покрывают отрезок $A_kA_{k+1}$. То же верно с заменой красных концов на синие. То есть отрезок $A_kA_{k+1}$ покрыт $к$ отрезками, а большим числом он и не может быть покрыт. Аналогично, при $k > 998$ отрезок $A_kA_{k+1}$ покрыт $1996 - k$ отрезками, и не может быть покрыт большим числом отрезков. Следовательно, сумма, достигнутая Васей, равна $1 + 2 + \cdots + 997 + 998 + 997 + \cdots + 2 + 1 = 998^2$ и не зависит от раскраски.
На прямой через равные промежутки отмечены 1996 точек. Петя раскрашивает половину из них в красный цвет, а остальные - в синий. Затем Вася разбивает их на пары «красная»-«синяя» так, чтобы сумма расстояний между точками в парах была максимальной. Докажите, что этот максимум не зависит от того, какую раскраску сделал Петя.
Решение:
Докажем, что Вася достигнет максимума, если поступит следующим образом: в первой паре - первая слева красная точка и первая справа синяя, во второй паре - вторая слева красная и вторая справа синяя, и т. д.
Для этого соединим точки в каждой паре отрезком и сосчитаем, сколько из этих отрезков покрывают отрезок $A_kA_{k+1}$ (рис.). Пусть $k \leq 998$, и среди точек $A_1,\cdots , A_k \: l$ красных. Тогда справа от точки $A_k$ не менее $l$ синих точек (если меньше, то среди $A_1,\cdots, A_k$ больше, чем $998 - l$ синих, и $k > 998$). Следовательно, все отрезки, красные концы которых находятся среди точек $A_1, \cdots, A_k$, покрывают отрезок $A_kA_{k+1}$. То же верно с заменой красных концов на синие. То есть отрезок $A_kA_{k+1}$ покрыт $к$ отрезками, а большим числом он и не может быть покрыт. Аналогично, при $k > 998$ отрезок $A_kA_{k+1}$ покрыт $1996 - k$ отрезками, и не может быть покрыт большим числом отрезков. Следовательно, сумма, достигнутая Васей, равна $1 + 2 + \cdots + 997 + 998 + 997 + \cdots + 2 + 1 = 998^2$ и не зависит от раскраски.
