Испанская комбинаторика
Вызвался намедни посмотреть (т.е. порешать) задачки последней мат олимпиады... в Испании. Шарик маленький, где наша не пропадала... В целом, довольно серьезный уровень (не берусь сказать, насколько ниже международной, не слежу, но серьезный), но основная часть не вдохновляет. Кое-что, по-моему, реконструируется к тому, как придумывали -- какой-то факт попроще, который потом пытаются прикрыть заменой координат или еще чем. В частности, первый шаг решения довольно однозначный, на эквивалентное упрощение. Но одна задачка -- шедевр. Вот она:
Для точек А,В на плоскости пусть R(A,B) обозначает минимальный прямоугольник со сторонами параллельными осям x,y, содержащий А и В (т.е. АВ -- диагональ, и прямоугольник вырождается в отрезок (или точку) если АВ параллелен одной из осей). Найдите максимальное число х так, чтобы для любого выбора 2024 точек P1,...,P2024 на плоскости нашелся прямоугольник R(Pi,Pj) с 1≤ i,j ≤ 2024, который содержит не менее х точек Pi.
Для точек А,В на плоскости пусть R(A,B) обозначает минимальный прямоугольник со сторонами параллельными осям x,y, содержащий А и В (т.е. АВ -- диагональ, и прямоугольник вырождается в отрезок (или точку) если АВ параллелен одной из осей). Найдите максимальное число х так, чтобы для любого выбора 2024 точек P1,...,P2024 на плоскости нашелся прямоугольник R(Pi,Pj) с 1≤ i,j ≤ 2024, который содержит не менее х точек Pi.