INMO 2024

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$

Solution 1.

Set $k = 2023$. If one of $a, b, c$ is divisible by $p$, then all of them are. Indeed, for example, if $p \mid a$, then $p \mid a^k + b^k$ implies $p \mid b$, and then $p \mid b^{k+1} + c^{k+1}$ implies $p \mid c$. The other cases follow similarly. So for the sake of contradiction assume none of $a, b, c$ is divisible by $p$. Then

and

So $b^{k(k+2)} \equiv c^{k(k+2)} \pmod{p}$. But then

which forces $b \equiv c \pmod{p}$. Thus

implying $p \mid b$, a contradiction. Thus the proof is complete. □

Solution 2.

As before, we may assume $p$ divides none of $a, b$, and $c$ and set $k = 2023$. Then

and multiplying these three equations yields $a^k b^{k+1} c^{k+2} \equiv -b^k c^{k+1} a^{k+2} \pmod{p}$. By cancelling the factor $a^k b^k c^{k+1}$, we get $a^2 \equiv -bc \pmod{p}$. Now

so

so either $b \equiv c \pmod{p}$ or $b \equiv -c \pmod{p}$. In the latter case, $a^2 \equiv c^2 \pmod{p}$ so $a \equiv c \pmod{p}$ or $a \equiv -c \pmod{p}$. In any case, two out of $\{a, b, c\}$ are the same mod $p$, so one of the equations gives $p \mid 2x^y$ where $x \in \{a, b, c\}$ and $y \in \{k, k+1, k+2\}$, hence $p$ odd implies $p \mid x$ so $p \mid abc$, the desired contradiction. □

Solution 3.

We have

Thus,

Thus, $p \mid 2 \cdot a^{2023 \cdot 2024 \cdot 2025}$ and hence $p \mid a$ since $p$ is odd. Now, finish as before. □

Solution 1.

Solution 1. The possible values are 1, 2, and 2024.

Construction. The function $f(x) = 1$ for all $x \in \mathbb{N}$ works. Also, $f(x) = 1$ for all $x \neq 2024$ and $f(2024) = 2$, works. Finally, $f(x) = x$ for all $x \in \mathbb{N}$ works as well. It remains to show these are the only possible values for $f(2024)$.

Proof. Denote $\text{Im}(f) = \{f(x) \mid x \in \mathbb{N}\}$. The cardinal set $\{1\}$ gives $f(1) = 1$. Consider the following two cases:

• $\text{Im}(f)$ is unbounded. Fix any $n \in \mathbb{N}$, with $n > 1$. Pick $n-1$ distinct integers $k_1, \dots, k_{n-1}$ such that $f(k_i) \notin \{n, f(n)\}$ and $f(k_i)$ are all pairwise distinct, for $1 \le i < n$. Then $\{n, k_1, \dots, k_{n-1}\}$ is a cardinal set. Then $\{f(n), f(k_1), \dots, f(k_{n-1})\}$ is a cardinal set with $n$ distinct elements, so $n$ lies in this set, hence $f(n) = n$. This gives the identity function.

• $\text{Im}(f)$ is bounded. Suppose $f(x) \le M$ for all $x \in \mathbb{N}$ and some integer $M > 0$.

Claim. For any integer $a$ satisfying $1 \le a \le M$, if there are infinitely many integers $n \in \mathbb{N}$ such that $f(n) = a$, then $a = 1$.

Proof. Let $b > 1$ be one of the integers with $f(b) = a$. Consider $b-1$ other integers $c_1, \dots, c_{b-1}$, such that $f(c_i) = a$ for $1 \le i < b$, and $c_i$ are all pairwise distinct. Then $\{b, c_1, \dots, c_{b-1}\}$ is a cardinal set, so the image set, which consists of the singleton $\{a\}$ is cardinal, hence $a = 1$. $\square$

So for every $2 \le m \le M$, there are only finitely many integers $x$ such that $f(x) = m$. Thus, there exists an integer $N > 1$ such that for all $n \ge N$, $f(n) = 1$. Now for every $1 < l < N$, consider the cardinal set $\{l, N+1, N+2, \dots, N+l-1\}$. Then the image set consists of $\{1, f(l)\}$, which can be cardinal only when $f(l) = 1$ or $f(l) = 2$.

By the above reasoning, $f(2024)$ can only be 1, 2, or 2024, each of which occurs as an example. $\square$

Solution 2.

Solution 2. We present a second proof of the fact that the proposed values are the only possibilities. Considering the singleton cardinal set $\{1\}$, we see that $f(1) = 1$. The cardinal set $\{1, 2\}$ gets mapped to $\{1, f(2)\}$, so $f(2)$ must be 2 or 1.

Case 1. Suppose $f(2) = 1$. Now $\{2, 2024\}$ is a cardinal set, and therefore so is $\{1, f(2024)\}$. This means $f(2024)$ is 1 or 2.

Case 2. Suppose $f(2) = 2$. The cardinal set $f(\{1, 2, 3\}) = \{1, 2, f(3)\}$ shows that $f(3) \in \{1, 2, 3\}$, but the cardinal set $f(\{2, 3\}) = \{2, f(3)\}$ proves $f(3)$ cannot be 2. Thus there are two sub-cases:

2.1. $f(3) = 1$. Then the set $\{1, 3, 2024\}$ is cardinal, hence so is $\{1, f(2024)\}$, implying, as before, $f(2024) \in \{1, 2\}$.

2.2. $f(3) = 3$. In this case, we show via induction that $f(n) = n$ for all $n \in \mathbb{N}$.

The base cases $n = 1, 2, 3$ are already known. Now consider $n \ge 4$, and assume $f(k) = k$ for all $k < n$. Consider the cardinal $f(\{1, 2, \dots, n\}) = \{1, 2, \dots, n-1, f(n)\}$ which implies $f(n) \in \{1, 2, \dots, n\}$.

However, consider the $n-1$-element cardinal set $\{1, 2, \dots, n\} \setminus \{n-2\}$. For its image to be cardinal $f(n)$ cannot equal any number in $\{1, 2, \dots, n-1\} \setminus \{n-2\}$; else its cardinality would be $n-2$, which isn’t in the set. So $f(n) \in \{n-2, n\}$.

Finally, consider the $n-2$-element set $\{1, 2, \dots, n\} \setminus \{n-1, n-3\}$. If $f(n) = n-2$, its image would only have $n-3$ elements, and thus would not be cardinal. So we conclude that $f(n) = n$ and the induction is complete. In particular, $f(2024) = 2024$.

Solution 1.

Solution 1. Fix an index $i \in \{1, 2, 3\}$. Let $D_1, D_2, D_3$ be the points of tangency of the incircle of triangle $\triangle A_1A_2A_3$ with its sides $A_2A_3$, $A_3A_1$, $A_1A_2$ respectively. The key observation is that given a line $\ell$ in the plane, the image of $\ell$ under the mapping $\tau_{i+2}(\tau_i(\tau_{i+1}(\ell)))$ is a line parallel to $\ell$. Indeed, $\ell$ is rotated thrice by angles equal to the angles of $\triangle A_1A_2A_3$, and the composition of these rotations induces a half-turn and translation on $\ell$ as the angles of $\triangle A_1A_2A_3$ add to $180^\circ$. Since $D_i$ is a fixed point of this transformation (by the chain of maps $D_i \xrightarrow{\tau_{i+1}} D_{i+2} \xrightarrow{\tau_i} D_{i+1} \xrightarrow{\tau_{i+2}} D_i$), we conclude that the line $\overline{PD_i}$ maps to the line $\overline{P_iD_i}$. But the two lines are parallel and both of them pass through $D_i$ hence they must coincide, so $D_i$ lies on $\overline{PP_i}$. Further, each rotation preserves distances, hence $P_i$ is the reflection of $P$ in $D_i$. In other words, the triangle $P_1P_2P_3$ is obtained by applying a homothety with ratio 2 and center $P$ to the triangle $D_1D_2D_3$. Thus, the radius of the circumcircle of $\triangle P_1P_2P_3$ is twice the radius of the circumcircle of $\triangle D_1D_2D_3$, i.e., twice the radius of the incircle of $\triangle A_1A_2A_3$, which is known to be at most the radius of the circumcircle $\Gamma$.

Now, for any complex number $z$, the rotation at $z_0$ with angle $\theta$ counterclockwise sends $z$ to $(z - z_0)e^{i\theta} + z_0$. Therefore, one computes that

Thus, $\tau_{312}(z)+z$ is independent of $z$. Similarly $\tau_{123}(z)+z$ and $\tau_{231}(z)+z$ are also independent of $z$. Note that adding $z$ is the same as translation by $z$, hence we have shown that the circumradius of $\triangle P_1P_2P_3$ is independent of $P$. Thus, it suffices to prove the result for $z = z_0 = a + b + c$. Let $U = -\tau_{312}(z_0)$, $V = -\tau_{123}(z_0)$, $W = -\tau_{231}(z_0)$. So, it is enough to prove that the circumradius of $\triangle UVW$ at most the radius of $\Gamma$. Name the vertices $A_1, A_2, A_3$ as $A, B, C$ for convenience. Let the parallel line to $BC$ passing through $A$ intersect $\Gamma$ again at $K$. Similarly, define $L$ as the second intersection of the line through $B$ parallel to $CA$ and finally $M$ for $C$ parallel to $AB$. We claim that $U$ lies on the line segment $\overrightarrow{AK}$: We have $U = a - (b-a)e^{i(A+C)} + (c-a)e^{iC}$, hence $\overrightarrow{AU}$ is parallel to $\overrightarrow{AK}$ hence $U$ lies on the line $AK$. If $AB = AC$ then $U = A$, and the claim is proven. Else suppose that $AB < AC$. Then $\overrightarrow{AU}$ points towards $K$ and $|AU| = AC - AB$, so it suffices

to show that $AK > AC - AB$. But this is clear because $KCBA$ is an isosceles trapezium, so $AB = KC$, and then triangle inequality on $\triangle KAC$ to get $KA + KC > AC$. Thus, $U \in \overline{AK}$, and similarly $V \in \overline{BL}$, $W \in \overline{CM}$. We claim that for any $U,V,W$ on the segments $AK, BL, CM$ respectively, the circumradius of $\triangle UVW$ is less than or equal to the radius of $\Gamma$. Now let $X,Y$ be two fixed points on the same side of a line $\ell$. Fix a side of $\overleftrightarrow{XY}$, and let $Z$ be a variable point on $\ell$ which always remains on this fixed side of $\overleftrightarrow{XY}$. Then the circumradius of $\triangle XYZ$ is minimized at the unique point $Z_0$ (on this fixed side of $\overleftrightarrow{XY}$) for which the circumcircle of $\triangle XYZ_0$ is tangent to $\ell$ and it is an increasing function as one goes further away from this unique point $Z_0$. Thus, the maximum circumradius of $\triangle UVW$ is achieved only if $U \in \{A,K\}$, $V \in \{B,L\}$, $W \in \{C,M\}$. For each of these, the circumradius is the radius of $\Gamma$, hence we are done. $\square$

Solution 2.

Toss the figure on the complex plane, and let $A_1 = a$, $A_2 = b$, $A_3 = c$ without loss of generality. Let the angles of the triangle at $A_1, A_2, A_3$ be denoted by $A, B, C$. Now, for any complex number $z$, the rotation at $z_0$ with angle $\theta$ counterclockwise sends $z$ to $(z - z_0)e^{i\theta} + z_0$.

The key observation is that given a line $\ell$ in the plane, the image of $\ell$ under the mapping $\tau_{i+2}(\tau_i(\tau_{i+1}(\ell)))$ is a line parallel to $\ell$. Indeed, $\ell$ is rotated thrice by angles equal to the angles of $\triangle A_1A_2A_3$, and the composition of these rotations induces a half-turn and translation on $\ell$ as the angles of $\triangle A_1A_2A_3$ add to $180^\circ$. Since $D_i$ is a fixed point of this transformation (by the chain of maps $D_i \xrightarrow{\tau_{i+1}} D_{i+2} \xrightarrow{\tau_i} D_{i+1} \xrightarrow{\tau_{i+2}} D_i$), we conclude that the line $\overline{PD_i}$ maps to the line $\overline{P_iD_i}$. But the two lines are parallel and both of them pass through $D_i$ hence they must coincide, so $D_i$ lies on $\overline{PP_i}$. Further, each rotation preserves distances, hence $P_i$ is the reflection of $P$ in $D_i$. In other words, the triangle $P_1P_2P_3$ is obtained by applying a homothety with ratio 2 and center $P$ to the triangle $D_1D_2D_3$. Thus, the radius of the circumcircle of $\triangle P_1P_2P_3$ is twice the radius of the circumcircle of $\triangle D_1D_2D_3$, i.e., twice the radius of the incircle of $\triangle A_1A_2A_3$, which is known to be at most the radius of the circumcircle $\Gamma$.

Let $M = n^2 + \frac{1}{2}n$.

Lemma 1. $B_n - A_n < \frac{1}{2}$.

Indeed,

proving the lemma.

Lemma 2. $A_n < M < B_n$.

Proof. Observe that

as $\sum_{k=1}^{n}(2k-1) = n^2$, proving $A_n - n^2 < \frac{n}{2}$ or $A_n < M$. Similarly,

as $\sum_{k=1}^{n}(2k) = n(n+1)$, so $B_n - n^2 > \frac{n}{2}$ hence $B_n > M$, as desired. $\square$

By Lemma 2, we see that $A_n$ and $B_n$ are positive real numbers containing $M$ between them. When $n$ is even, $M$ is an integer. This implies $\lfloor A_n \rfloor < M$, but $\lfloor B_n \rfloor \ge M$, which means we cannot have $\lfloor A_n \rfloor = \lfloor B_n \rfloor$.

When $n$ is odd, $M$ is a half-integer, and thus $M - \frac{1}{2}$ and $M + \frac{1}{2}$ are consecutive integers. So the above two lemmas imply

This shows $\lfloor A_n \rfloor = \lfloor B_n \rfloor = M - \frac{1}{2}$.

Thus, the only integers $n \ge 3$ that satisfy the conditions are the odd numbers and all of them work. $\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.

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$.