Given two points $p_1=(x_1, y_1)$ and $p_2=(x_2, y_2)$ on the plane, denote by $\mathcal{R}(p_1,p_2)$ the rectangle with sides parallel to the coordinate axes and with $p_1$ and $p_2$ as opposite corners, that is, \[\{(x,y)\in \mathbb{R}^2:\min\{x_1, x_2\}\leq x\leq \max\{x_1, x_2\},\min\{y_1, y_2\}\leq y\leq \max\{y_1, y_2\}\}.\]Find the largest value of $k$ for which the following statement is true: for all sets $\mathcal{S}\subset\mathbb{R}^2$ with $|\mathcal{S}|=2024$, there exist two points $p_1, p_2\in\mathcal{S}$ such that $|\mathcal{S}\cap\mathcal{R}(p_1, p_2)|\geq k$.
Problem
Source: Spain MO 2024 P5
Tags: combinatorics, combinatorial geometry, Spain, geometry, rectangle
MathSaiyan
16.03.2024 20:45
The answer is around $2024/5$, instead of the obvious conjecture $2024/4$. To be precise, the answer is $406$.
Bound
Shorten $(X,Y) = \mathcal R(X,Y)$. Let $P,Q,R,S$ be the points with maximal $y$-coord, maximal $x$-coord, minimal $y$-coord, and minimal $x$-coord, respectively. If any two of them coincide our job is made easier, so it's not really a thing to worry about. Consider the rectangles $(P,Q)$, $(Q,R)$, $(R,S)$ and $(S,P)$. If they cover al the points, we're done by a easy PHP. So suppose they do not, hence there is a rectangular region $r$ that fits between those four rectangles. Suppose $(P,Q)$, $(Q,R)$, $(R,S)$, $(S,T)$ and $r$ contain $a,b,c,d$ and $k$ points, respectively. But now we can consider $(P,R)$, which has at least $k+2$ points, hence we can guarantee a region with at least $\max\{a,b,c,d,k+2\}$ points. But we know that $a+b+c+d+k-4 = 2024$. Now one only needs a boring "counting with your fingers" argument to show that $\max\{a,b,c,d,k+2\} \ge 406$.
Construction
It's easy to find the construction with the bound in mind, just force $a=b=c=d=406$, $k=404$ placing the points as shown in the attachment.
Attachments:
