INMO 2023

Strategy for the Detective: Pick a card $A$ and compare against all others except one. If he ever gets a “Yes”, that pair works; else the remaining card is consecutive with $A$. This process takes at most $50$ queries.

Strategy for the Magician: We show that it is not always possible to obtain a “Yes” in $50$ turns, hence showing that $49$ turns are not enough to figure out a consecutive pair. It is enough to conjure a labelling of cards for which denying all $50$ inquiries is valid.

Replace $52$ by any $N>3$. Think of the cards as vertices of a complete graph $K_{N}$. Delete all edges joining vertices which correspond to pairs of cards the Detective inquired about. We will show that deleting any $N-2$ edges of $K_{N}$ still leaves a graph that admits a path containing all the vertices. Labelling all cards along this path as $1$ to $N$ would finish. Several proofs of this claim are possible. We present three of them.

Proof 1

For any two vertices $a$ and $b$, since $\operatorname{deg} a + \operatorname{deg} b \geq 2(N-1)-(N-2)=N$, they share a common neighbour. Hence the graph is connected.

Pick the longest path $\mathcal{P}: u=u_{0} \rightarrow u_{1} \rightarrow \cdots \rightarrow u_{k}=v$. All neighbours of $u$ and $v$ must remain within the path, else we could get a longer path. Let $u$ have $x$ neighbours $\{u_{i_{1}}, u_{i_{2}}, \ldots, u_{i_{x}}\}$ with $1=i_{1}<i_{2}<\cdots<i_{x} \leq k$. Let $v$ have $y$ neighbours $\{u_{j_{1}}, \ldots, u_{j_{y}}\}$. Since $x+y \geq n$, we see that $i_{s}=j_{r}+1$ for some $r$ and $s$. Thus there exists $i$ such that $u \rightarrow u_{i+1}$ and $u_{i} \rightarrow v$ are edges. Thus the path is a cycle

Suppose a vertex $w$ is not in the path $\mathcal{P}$. By connectedness, we have a path $\mathcal{P}'$ from $w$ to some vertex of $\mathcal{P}$. Continue along this path via the cycle $\mathcal{C}$ to obtain a path longer than $\mathcal{P}$; contradiction! Thus the graph has a path of length $N-1$, as desired.

Proof 2

Pick the longest cycle $\mathcal{C}=v_{1} \rightarrow \cdots \rightarrow v_{k} \rightarrow v_{1}$. Note that any vertex $w$ not in the cycle can be incident to no more than $\frac{k}{2}$ of the vertices in it; else there exists $i$ such that $w v_{i}$ and $w v_{i+1}$ (indices mod $k$) are edges, so we can put $w$ in to get a longer cycle. Thus our graph is missing at least $\frac{1}{2} k(N-k)$ edges. So $2(N-2) \geq k(N-k)$. Clearly $k>2$ so we see that $k \in\{N-2, N-1\}$.

Case 1. $k=N-1$. Pick the leftover $w$ outside $\mathcal{C}$. Not all edges from $w$ to the cycle are missing (since only $N-2$ are missing in total), so follow an edge from $w$ to $\mathcal{C}$ and continue along $\mathcal{C}$ to get a path of length $N-1$.

Case 2. $k=N-2$. Pick the leftover $a, b$ outside $\mathcal{C}$. It is clear that both of them have edges to the cycle and $ab$ is also an edge (since $k(N-k)=2(N-2)$ in this case). So starting at $a$, going to $b$, to some vertex of $\mathcal{C}$ and following along $\mathcal{C}$ gives us a path of length $N-1$.

The proof is complete.

Proof 3

The idea is to prove the stronger claim by induction on $N \geq 3$: a graph on $N$ vertices with $\binom{N-1}{2}+2$ edges has a cycle of length $N$. Deleting the extra edge will give a path of length $N-1$ through all the vertices.

The base case $N=3$ is trivial. Suppose it holds for all $k \leq N$, we prove it for $N+1$. Since $\frac{2\left(2+\binom{N}{2}\right)}{N+1}>N-2$ we see that some vertex $v$ has degree either $N-1$ or $N$.

Case 1. If degree of $v$ is $N-1$. Then we have an edge $e=uv$ missing among all the edges through $v$. Delete $v$ along with all the edges through it in the graph. The induced graph has a cycle of length $N$. Pick two consecutive vertices that are not $u$, and append $v$ between them.

Case 2. If degree of $v$ is $N$. Delete $v$ along with all its edges. Add an arbitrarily chosen extra edge to the graph so obtained. By induction hypothesis, this resulting graph has a cycle of length $N$. If removing the extra edge does not disrupt the cycle, append $v$ anywhere between two consecutive vertices. If it does break the cycle, use $v$ to connect the vertices it joined.

The induction is complete.

First we show that $\angle DEC = 30^{\circ}$. Choose a point $F$ on $AB$ such that $CF = CB$. Join $FC$ and $FD$. Observe that $\angle DCB = 75^{\circ} + 25^{\circ} = 100^{\circ}$. Since $CD = CB$, we have $\angle CDB = \angle CBD = 40^{\circ}$. Therefore $\angle CBF = 40^{\circ} + 30^{\circ} = 70^{\circ}$. This gives $\angle CFB = 70^{\circ}$. Since $CD = CB = CF$, we have the isosceles triangle $CDF$. But $\angle BCF = 40^{\circ}$. Hence $\angle FCD = 60^{\circ}$. Therefore we have an equilateral triangle $CDF$. This means $FD = FC = CD$ and $\angle DFC = 60^{\circ}$.

Observe that $\angle AFC = 110^{\circ}$ and $\angle FCA = 35^{\circ}$. Hence $\angle FAC = 35^{\circ}$. This means $FA = FC = FD$. Thus $F$ is the circumcentre of $\triangle ADC$. This implies that

Therefore $\angle DEC = \angle DAC = 30^{\circ}$. Now concentrate on triangle $DCE$. Construct an equilateral triangle $ECG$ with $CE$ as base, on the side of $B$. Join $GD$.

We have $\angle CGE = \angle GCE = \angle CEG = 60^{\circ}$ and $CE = EG = GC$. Since $\angle CED = 30^{\circ}$, we get $\angle GED = 30^{\circ}$. Thus $ED$ is the angle bisector of the isosceles triangle $GEC$. This implies that $ED$ is also the perpendicular bisector of $GC$. Thus $D$ is on the perpendicular bisector of $GC$. Therefore $DC = DG$ and hence $\angle DGC = \angle DCG$. But $\angle DCG = 100^{\circ} - 60^{\circ} = 40^{\circ}$. This implies that $\angle DGC = 40^{\circ}$ and hence $\angle CDG = 100^{\circ}$. Consider the quadrilateral $GBCD$. We have $DG = DC = CB$, $\angle GDC = 100^{\circ} = \angle DCB$. It is an isosceles trapezium. (or we can show that $\triangle GDC \cong \triangle BCD$.) Therefore $DB = GC$. But $GC = CE$. Thus we get $DB = CE$.

Alternate Solution As in the previous solution, one shows that $F$ is the circumcenter of $\triangle ADC$. Since $E$ lies on this circumcircle, this means $FE$ is equal to all of the sides $FA, FD, FC$ and thus also to $CD$ and $CB$. Now $CDB$ and $FCE$ are both isosceles triangles with base angles $40^{\circ}$, and they have $CD = FC$, so they are in fact congruent. This directly implies $CE = BD$, as required.

We have $f(p)=p$ for all $p \in \mathbb{R}[x]$, or $f(p)=-p$ for all $p \in \mathbb{R}[x]$. These clearly satisfy the given conditions.

Proof Claim 1 For all $p \in \mathbb{R}[x], f(f(p))=p$. Proof. Using condition 3 on the polynomials $p$ and $f(p)$, we see that $p-f(f(p))$ has the same set of real roots as $f(p)-f(p)=0$, which is $\mathbb{R}$. Therefore $p-f(f(p))$ is identically zero.

Note that this implies $f$ is bijective. In what follows, $p \sim q$ will mean that $p$ and $q$ have the same set of real roots. Note that putting $f(q)$ for $q$ in condition 2 gives $p-q \sim f(p)-f(q)$ for all $p, q$ (call this statement $(\star)$ ). In particular, putting $q=0$ here, $p \sim f(p)$ for all $p$ (call this $(\star\star)$).

Claim 2 For all non-zero $p \in \mathbb{R}[x]$, $\operatorname{deg} p-1 \leq \operatorname{deg} f(p) \leq \operatorname{deg} p+1$. Proof. The right inequality is simply condition 2. Now using condition 2 on the polynomial $f(p)$, we see that $\operatorname{deg} f(f(p)) \leq \operatorname{deg} f(p)+1$ which gives $\operatorname{deg} f(p) \geq \operatorname{deg} p-1$ because of claim 1.

Claim 3 For all $p \in \mathbb{R}[x], \operatorname{deg} f(p)=\operatorname{deg} p$. Proof. Note that nonzero constant polynomials have no root, so by $(\star\star)$, their image must have no root. This is impossible if that image has degree 1; so by condition 2, the image has degree 0, i.e., is a constant polynomial. First consider the case when $\operatorname{deg} p$ is even; assume for now the leading coefficient of $p$ is positive. That means $p(x) \rightarrow \infty$ for $x \rightarrow \pm \infty$, so it has a global minimum, say $C$. Then the polynomial $p+k$ ($k>C$) has no real roots. Using $(\star)$ on $p$ and the constant polynomial $-k$, we see that $f(p)-f(-k)$ has no roots. But this is impossible if $\operatorname{deg} f(p)$ is odd (since $f(-k)$ is a constant), so by claim 2, we must have $\operatorname{deg} f(p)=\operatorname{deg} p$. A similar argument holds if $p$ has negative leading coefficient.

Now if $\operatorname{deg} p$ is odd, then $\operatorname{deg} f(p)$ cannot be even, otherwise $q=f(p)$ would be an even degree polynomial whose image $f(q)=f(f(p))=p$ has odd degree, contradicting the last paragraph. Thus $\operatorname{deg} f(p)$ is odd, and using claim 2, we infer that $\operatorname{deg} f(p)=\operatorname{deg} p$.

We call a polynomial $p$ ninth-grade if all $\operatorname{deg} p$ roots of $p$ are real and distinct. Clearly for any ninth-grade $p$, $p$ and $f(p)$ have the roots and same degree, so $f(p)=c_{p} p$ for some non-zero $c_{p} \in \mathbb{R}$.

Claim 4 Given any non-constant $q \in \mathbb{R}[x]$, we can choose $r$ with degree bigger than $q$ so that both $r$ and $q-r$ are ninth-grade. Proof. Assume that all real roots of $q$ are inside the interval $[a, b]$. Now choose a number $n$ which has the same parity as $\operatorname{deg} q$ and is bigger than $\operatorname{deg} q$, and choose numbers $c_{1}=a< c_{2}<\cdots<c_{n-1}<c_{n}=b$. Consider the polynomial $p=k\left(x-c_{1}\right)\left(x-c_{2}\right) \cdots\left(x-c_{n}\right)$, so that $k$ has the same sign as the leading coefficient of $q$ (value of $k$ will be chosen later). Clearly $p$ has alternating signs on the intervals $\left(-\infty, c_{1}\right),\left(c_{1}, c_{2}\right), \cdots,\left(c_{n-1}, c_{n}\right),\left(c_{n}, \infty\right)$, and has the same sign as $q$ outside $[a, b]$. Let $k_{1}, k_{2}, \cdots, k_{n-1}$ be the extrema of $p$ on the intervals $\left[c_{1}, c_{2}\right], \cdots\left[c_{n-1}, c_{n}\right]$ in that order, and suppose they are attained at $x_{1}, \cdots x_{n-1}$. Make $|k|$ large enough so that $\left|k_{i}\right|>\max _{x \in[a, b]}|q(x)|$ for all $i$. Then $p+q$ has degree $n$, and has alternating signs at $a-\epsilon, x_{1}, \cdots, x_{n}, b+\epsilon$ for $\epsilon>0$, so it has exactly $n$ distinct roots. Now it is enough to take $r=-p$.

Claim 5 For any $q \in \mathbb{R}[x], f(q)=c_{q} q$ for some non-zero real $c_{q}$. Proof. We have already proved this for ninth-grade polynomials. Take ninth-grade $r$ so that $q-r$ is ninth grade and $n=\operatorname{deg}(q-r)>\operatorname{deg} q$. Then $q-r \sim f(q)-f(r)=f(q)-c_{r} r$. Since $q-r$ is ninth-grade and has the same degree as $f(q)-c_{r} r$, $q-r=c\left(f(q)-c_{r} r\right)=c f(q)-c_{1} r$ for non-zero reals $c, c_{1}$. Comparing the leading term (which belongs to $r$) on both sides, $c_{1}=1$, therefore $q=c f(q) \Longrightarrow f(q)=c_{q} q$.

Claim 6 For any $p, q \in \mathbb{R}[x], c_{p}=c_{q}$. Proof. We note that for any two polynomials $p, q$ if $p-q$ has a real root which is not a root of $p$, then $c_{p}=c_{q}$. Indeed, if $s$ is a root of $p-q$ (meaning $p(s)=q(s) \neq 0$), then it’s also a root of $f(p)-f(q)=c_{p} p-c_{q} q$, so that $c_{p} p(s)=c_{q} q(s) \Longrightarrow c_{p}=c_{q}$.

Now for any two $p, q$, choose odd $N$ such that $N>\max \{\operatorname{deg} p, \operatorname{deg} q\}$. Then the polynomial $r=x^{N}$ is such that $r-p$ and $r-q$ both have real roots, so $c_{q}=c_{r}=c_{p}$.

Claim 6 clearly means there is $c \in \mathbb{R}$ so that $f(p)=c p$ for all $p \in \mathbb{R}[x]$. Using the fact $f(f(p))=p$, we see that the only possibilities are $c=1$ or $c=-1$, completing the proof.

Solution 1.

We have $FG = FA$ since $FG$ is parallel to $BC$. But also $\triangle GAE$ is a right angle triangle. Thus, if $F'$ is the midpoint of $GE$, then $\angle GAF = \angle FGA = \angle F'GA = \angle GAF'$ which implies $F \equiv F'$. Thus, $F$ is the midpoint of $GE$.

If $O$ is the circumcenter of $\triangle EBG$, then

Thus, we get $\angle FOE = \angle FCE$ as desired. $\square$

Solution 2.

($\angle BCA$ acute case) Let $O_1$ be the circumcenter of $\triangle ABC$, $O$ be the circumcenter of $\triangle EBG$ and $\omega$ be the circumcircle of $\triangle ECF$.

First, show that $F$ is the midpoint of $EG$ as in Solution 1. Next, we show that $O_1$ lies on $\omega$. This follows from

Now, $O_1$ is the midpoint of $EB$ and $F$ is the midpoint of $EG$, therefore the homothety at $E$ with ratio $1/2$ takes $\triangle EGB$ to $\triangle EFO_1$. Thus, it takes $O$, the circumcenter of $\triangle EGB$, to the circumcenter of $\triangle EFO_1$, thus proving that the midpoint of $EO$ is the center of $\omega$. This immediately implies that $O$ lies on $\omega$. $\square$

Solution 1.

We have $FG = FA$ since $FG$ is parallel to $BC$. But also $\triangle GAE$ is a right angle triangle. Thus, if $F'$ is the midpoint of $GE$, then $\angle GAF = \angle FGA = \angle F'GA = \angle GAF'$ which implies $F \equiv F'$. Thus, $F$ is the midpoint of $GE$. If $O$ is the circumcenter of $\triangle EBG$, then

Thus, we get $\angle FOE = \angle FCE$ as desired. $\square$

Solution 2.

($\angle BCA$ acute case) Let $O_1$ be the circumcenter of $\triangle ABC$, $O$ be the circumcenter of $\triangle EBG$ and $\omega$ be the circumcircle of $ECF$. First, show that $F$ is the midpoint of $EG$ as in Solution 1. Next, we show that $O_1$ lies on $\omega$. This follows from

Now, $O_1$ is the midpoint of $EB$ and $F$ is the midpoint of $EG$, therefore the homothety at $E$ with ratio $1/2$ takes $\triangle EGB$ to $\triangle EFO_1$. Thus, it takes $O$, the circumcenter of $\triangle EGB$, to the circumcenter of $\triangle EFO_1$, thus proving that the midpoint of $EO$ is the center of $\omega$. This immediately implies that $O$ lies on $\omega$. $\square$

Let $n = 2024$ and $k = 1000$. We claim that the maximum number of squares that can be coloured in this way is $k(2n - k)$, which evaluates to $3048000$.

Indeed, call a row/column bad if it has at least one red square. After the first move, there are exactly $k+1$ bad rows and columns: if a row was picked, then that row and the $k$ columns corresponding to the chosen squares are all bad. Any subsequent move increases the number of bad rows/columns by at least $1$. Since there are only $2n$ rows and columns, we can make at most $2n - (k+1)$ moves after the first one, and so at most $2n - k$ moves can be made in total. Thus we can have at most $k(2n-k)$ red squares.

To prove this is achievable, let’s choose each of the $n$ columns in the first $n$ moves, and colour the top $k$ cells in these columns. Then, the bottom $n-k$ rows are still uncoloured, so we can make $n-k$ more moves, colouring $k(n+n-k)$ cells in total. $\square$