Taiwan IMO Selection Camp, 2022

There are 2022 distinct lattice points on the plane. Let $I$ be the number of pairs of points among these points whose distance is exactly 1. Find the maximum possible value of $I$.

Note: A lattice point is a point whose $x$-coordinate and $y$-coordinate are both integers.

The maximum possible $I$ is 3954; this maximum is achieved by a $45 \times 45$ grid of points with three corners removed.

For any 2022 distinct lattice points, suppose that they have a total of $n$ distinct $x$-coordinates $x_1, x_2, \dots, x_n$, and there are $a_i$ points with $x$-coordinate equal to $x_i$. Note that among the points on the column $x = x_i$, one can form at most $a_i - 1$ segments of length 1 perpendicular to the $x$-axis, so the total number of segments of length 1 perpendicular to the $x$-axis $\le \sum_{i=1}^n (a_i - 1) = 2022 - n$.

Similarly, if these points have a total of $m$ distinct $y$-coordinates, then the total number of segments of length 1 perpendicular to the $y$-axis $\le 2022 - m$.

Moreover, since a segment of length 1 between lattice points must be perpendicular to one of the coordinate axes, we have
$$I \le (2022 - n) + (2022 - m) = 4044 - (n + m)$$
But also note that 2022 distinct points guarantee $mn \ge 2022$, so by AM-GM we have
$$m + n \ge 2\sqrt{mn} > 89 \Rightarrow m + n \ge 90.$$
Therefore $I \le 4044 - 90 = 3954$.