Испанская комбинаторика
Mar. 26th, 2024 10:01 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
svyatogorodskiВызвался намедни посмотреть (т.е. порешать) задачки последней мат олимпиады... в Испании. Шарик маленький, где наша не пропадала... В целом, довольно серьезный уровень (не берусь сказать, насколько ниже международной, не слежу, но серьезный), но основная часть не вдохновляет. Кое-что, по-моему, реконструируется к тому, как придумывали -- какой-то факт попроще, который потом пытаются прикрыть заменой координат или еще чем. В частности, первый шаг решения довольно однозначный, на эквивалентное упрощение. Но одна задачка -- шедевр. Вот она:
Для точек А,В на плоскости пусть 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.
no subject
Date: 2024-03-26 08:58 pm (UTC)Иначе можно дать ответ x=0, т.е.
для любого выбора 2024 точек P1,...,P2024 на плоскости нашелся прямоугольник R(Pi,Pj) с 1≤ i,j ≤ 2024, который содержит не менее 0 (=любое их число, отрицательных точек не бывает), точек Pi - просто возьмем любые i, j.
--
ILP
no subject
Date: 2024-03-26 09:04 pm (UTC)