Let $N=10^{2024}$. $S$ is a square in the Cartesian plane with side length $N$ and the sides parallel to the coordinate axes. Inside there are $N$ points $P_1$, $P_2$, $\dots$, $P_N$ all of which have different $x$ coordinates, and the absolute value of the slope of any connected line between these points is at most $1$. Prove that there exists a line $l$ such that at least $2024$ of these points is at most distance $1$ away from $l$.
Problem
Source: 2024 CTST P24
Tags: combinatorics, 2024 CTST, expected value
30.03.2024 13:46
My first AoPS solution with latex!Quite ez as the problem 6 in the final test,just use the trick of expected value then the problem could be solved. WLOG let $P_i(x_i,y_i),x_1<...<x_N$.Then $|x_1-x_N|\le N$,and $|P_{i}P_{j}|\le\sqrt{2}|x_i-x_j|$. Consider a line $l$ with the tilt angle of $\theta$ through $P_i$,let $f_{i}(\theta)$ denote the number of points in $\mathcal{S}$ whose distance from $l$ is less than $1$.$(0\le\theta\le\pi)$ Now we compute the expected value of every $f_i(\theta),1\le i\le N$.It suffices to show that the sum exceeds $N\lg{N} (*)$.Actually,we have: $$\mathbb{E}[f_i(\theta)]=\frac{1}{\pi}\int_{0}^{\pi}f_i(\theta)d\theta\ge\frac{2}{\pi}\sum_{\substack{j=1\\j\neq i}}^{N}\arcsin(\frac{1}{|P_iP_j|+1})>\frac{2}{\pi}\sum_{\substack{j=1\\j\neq i}}^{N}\frac{1}{|P_iP_j|+1}$$Hence $$\mathbb{E}[\sum_{i=1}^{N}f_i(\theta)]>\frac{2}{\pi}\sum_{i\neq j}\frac{1}{|P_iP_j|+1}\ge\frac{2\sqrt{2}}{\pi}\sum_{1\le i<j\le N}\frac{1}{1+x_j-x_i}$$Notice that $$\sum_{i=1}^{N-d}\frac{1}{1+x_{i+d}-x_i}\ge\frac{(N-d)^2}{\sum_{i=1}^{N-d}(1+x_{i+d}-x_i)}\ge\frac{(N-d)^2}{N+d(x_N-x_1)}\ge\frac{(N-d-1)^2}{(d+1)N}$$. Thus the sum of the expected value exceeds $$\frac{2\sqrt{2}}{\pi}\sum_{d=2}^{N-1}\frac{N}{d}+\frac{d}{N}-2>\frac{2\sqrt{2}}{\pi}(N\ln N-3N)>N\lg N$$When $N=10^{2024}$.So the claim$(*)$ holds and we complete the proof.$\blacksquare$
31.03.2024 03:08
Very nice problem
06.04.2024 02:36
Suppose that the statement is not true. WLOG none of the coordinates are rational. Let $x=\lfloor\log_2N\rfloor=\lfloor2024\log_210\rfloor>6072$. Do the following procedure $x$ times: draw a vertical line splitting the current rectangle in half, then take the rectangle with more points. Now, in the smallest rectangle, pick a point $X$ such that the slopes from $X$ to $P_i$ has absolute value at most $1$. Consider the two lines through $X$ with slope $\pm1$, which have at most $4048$ total points distance at most $1$ away from those lines. WLOG $X=(0,0)$. If $P_i=(a,b)$, then any line with slope between $\frac{b-1}a$ and $\frac{b+1}a$ has $P_i$ distance at most $1$ away. This interval is entirely within $[-1,1]$ and has size $\frac2a$ for $N-4048$ of those points. We will show that the sum of the intervals is at least $4048$, which shows that at least one slope is in at least $2024$ intervals, corresponding to a line that is distance at most $1$ away from $2024$ points. Consider the rectangles $0$, $1$, $2$, $\ldots$, $x$ with widths $c_0=\frac N{2^x}$, $c_1=\frac N{2^x}$, $c_2=\frac N{2^{x-1}}$, $\ldots$, $c_x=\frac N2$. Suppose rectangle $i$ has $a_i$ points. Rectangle $i$ contributes at least $\frac2{2c_i}a_i=\frac{a_i}{c_i}$, and $a_i\leq a_{i-1}+a_{i-2}+\cdots+a_0+4048$. By smoothing, the minimum total occurs at $a_i=c_i-b_i$ where $b_i\leq c_i$, $\sum b_i=4048$, and $(b_0,b_1,b_2,\ldots)$ is as large as possible. The total is at least $x+1-\frac{c_0}{c_0}-\frac{c_1}{c_1}-\cdots-\frac{c_{14}}{c_{14}}\geq x-15>4048$. Therefore, there exists a line through $X$ with slope with absolute value at most $1$ that is distance at most $1$ away from $2024$ points.