INMO 2023

Let $S$ be a finite set of positive integers. Assume that there are precisely 2023 ordered pairs $(x, y)$ in $S \times S$ so that the product $x y$ is a perfect square. Prove that one can find at least four distinct elements in $S$ so that none of their pairwise products is a perfect square.

Note: As an example, if $S=\{1,2,4\}$, there are exactly five such ordered pairs: $(1,1),(1,4)$, $(2,2),(4,1)$, and $(4,4)$.

Suppose $a_{0}, \ldots, a_{100}$ are positive reals. Consider the following polynomial for each $k$ in $\{0,1, \ldots, 100\}$ :

$$a_{100+k} x^{100}+100 a_{99+k} x^{99}+a_{98+k} x^{98}+a_{97+k} x^{97}+\cdots+a_{2+k} x^{2}+a_{1+k} x+a_{k}$$

where indices are taken modulo 101, i.e., $a_{100+i}=a_{i-1}$ for any $i$ in $\{1,2, \ldots, 100\}$. Show that it is impossible that each of these 101 polynomials has all its roots real.

Let $\mathbb{N}$ denote the set of all positive integers. Find all real numbers $c$ for which there exists a function $f: \mathbb{N} \rightarrow \mathbb{N}$ satisfying:

(a) for any $x, a \in \mathbb{N}$, the quantity $\frac{f(x+a)-f(x)}{a}$ is an integer if and only if $a=1$;

(b) for all $x \in \mathbb{N}$, we have $|f(x)-c x|<2023$.

Let $k \geq 1$ and $N>1$ be two integers. On a circle are placed $2 N+1$ coins all showing heads. Calvin and Hobbes play the following game. Calvin starts and on his move can turn any coin from heads to tails. Hobbes on his move can turn at most one coin that is next to the coin that Calvin turned just now from tails to heads. Calvin wins if at any moment there are $k$ coins showing tails after Hobbes has made his move. Determine all values of $k$ for which Calvin wins the game.

Euler marks $n$ different points in the Euclidean plane. For each pair of marked points, Gauss writes down the number $\left\lfloor\log _{2} d\right\rfloor$ where $d$ is the distance between the two points. Prove that Gauss writes down less than $2 n$ distinct values.

Note: For any $d>0,\left\lfloor\log _{2} d\right\rfloor$ is the unique integer $k$ such that $2^{k} \leq d<2^{k+1}$.

Euclid has a tool called cyclos which allows him to do the following:

• Given three non-collinear marked points, draw the circle passing through them.
• Given two marked points, draw the circle with them as endpoints of a diameter.
• Mark any intersection points of two drawn circles or mark a new point on a drawn circle.

Show that given two marked points, Euclid can draw a circle centered at one of them and passing through the other, using only the cyclos.