There are $2022$ distinct integer points on the plane. Let $I$ be the number of pairs among these points with exactly $1$ unit apart. Find the maximum possible value of $I$. (Note. An integer point is a point with integer coordinates.) Proposed by CSJL.
Problem
Source: 2022 Taiwan TST Round 2 Independent Study 2-C
Tags: combinatorics, lattice points
10.04.2022 13:48
It can be proved that the answer is at most two times the number of points, minus the "diameter" of the shape on x and y axis. This is done by removing the points one by one and count their contributions. the diameter part can be done with AM-GM. So the answer is $2\times2022 - 45 - 45 = 3954$
10.04.2022 19:57
Replace $2022$ with $n$. In general, the answer is $2n-\lceil \sqrt{4n} \rceil$ Let $C$ be the set of columns the lattice points take. Claim: the number of pairs of adjacent lattice points where one is on top of another is at most $n-|C|$ Proof: if column $j$ has $x_j$ lattice points then there are at most $x_j-1$ such pairs of lattice points. Note $\sum x_j=n$ so the claim holds. Define $R$ similarly. We can note the points are constrainted within the rectangle with rows in R and columns in C so $|R| |C|\ge n$ By AM-GM, $|R|+|C|\ge \sqrt{4n}$ so the total number of points is at most $2n-|R|-|C|=2n-\sqrt{4n}$ Construction: if $\lceil \sqrt{4n} \rceil=2k$ for some integer $k$, then consider the lattice points a $k\cdot k$ grid where I leave out $k^2-n$ points on the right most column. If $\lceil \sqrt{4n} \rceil=2k-1$ do same thing for $k\cdot (k-1)$ grid. The end.
25.08.2022 11:32
The answer is 3954
04.05.2023 07:48
Answer: 3954 This can be attained by taking a $45\times 45$ square with corners $(1,1)$ and $(45,45)$, and removing $(1,1),(1,2),(1,3)$ which has $$45\times44\times 2-6=3954$$pairs as needed. To prove the bound, let set of points be $A$, and let the number of distinct $x$ coordinates and $y$ coordinates be $a,b$ respectively. Then, if $S_L, S_R, S_T, S_B$ are the sets of points that are the leftmost, rightmost, topmost, bottommost of $A$ (not necessarily disjoint). But then, the maximum sum of degrees of points is $$4\times 2022 - (\lvert S_L\rvert+\lvert S_R\rvert+\lvert S_T\rvert+\lvert S_B\rvert)$$But $\lvert S_L\rvert = \lvert S_R\rvert$ and $\lvert S_T\rvert=\lvert S_B\rvert$ so the maximum number of pairs is $4044-(\lvert S_L\rvert+\lvert S_T\rvert)$. It suffices to show $a+b=\lvert S_L\rvert+\lvert S_T\rvert\geq 90$. FTSOC suppose it is at most $89$, then $$2022\leq ab\leq 44\times 45=1980$$by convexity, a contradiction as needed. Thus, $a+b\geq 90$ so we have at most $4044-90=3954$ pairs as needed.