The numbers from $1$ to $2000$ are placed on the vertices of a regular polygon with $2000$ sides, one on each vertex, so that the following is true: If four integers $A, B, C, D$ satisfy that $1 \leq A<B<C<D \leq 2000$, then the segment that joins the vertices of the numbers $A$ and $B$ and the segment that joins the vertices of $C$ and $D$ do not intersect inside the polygon. Prove that there exists a perfect square such that the number diametrically opposite to it is not a perfect square.
Problem
Source: Mexico 2023/2
Tags: combinatorics
09.11.2023 21:55
Let's assume that every perfect square is diametrically opposite to another perfect square. We know there is a perfect square, $x^2$ diametrically opposite to a perfect square $y^2$, that satisfies that $1 \leq y^2 \leq x^2 \leq 23^2$. There are at least $2000 - 23^2 = 1471$ numbers greater than $x^2$. By the pigeonhole principle, we know that there are at least 2 of these numbers on opposite sides of the diameter formed by $x^2$ and $y^2$. The segment that joins these 2 points intersects the diameter $x^2 y^2$, which contradicts the conditions of the problem. Therefore, it cannot happen that all perfect squares are opposite to another perfect square, and consequently there exists a perfect square diametrically opposed to a number that is not a perfect square.
14.11.2023 09:27
why $23^2$ and not $18^2$?
14.11.2023 13:19
Derfu37 wrote: why $23^2$ and not $18^2$? The total number of square numbers below $2000$ is $44$. In addition, the number of groups of perfect squares diametrically opposite each other is $22.$ Notice that there are $21$ square numbers from $24^{2}$ to $44^{2}$, and among them, the maximum number of groups they can partially occupy is $21$. So, there will be at least one group that will have square numbers that are less than or equal to $23^{2}$.
18.11.2023 00:52
I found it more intuitive to reformulate the condition as follows: For any $k \le 2000$, the numbers $1,2,\dots,k$ form a contiguous block of numbers (but not necessarily in this order). (This is easily proved by induction, since otherwise the number $k+1$ will have gaps to the $1,2,\dots,k$ block at both ends, and then $k,k+1$ and the two larger numbers in the gaps form a counterexample to the condition.) From here, the problem is almost trivial: Each number in $1,2,\dots,1000$ is opposite to a number in $1001,\dots,2000$. But the former contains $31$ perfect squares while the latter has only $13$...