IMO 2025

“Live-solve” / Solution walk-through

Have not been spoiled on the problems, but I have been spoiled on the scores, so I can roughly guess the difficulty of this paper.

Day 1

(0h5m) First thoughts:

CGN and the geom looks weird. Actually the FE looks weird also.
Not much else to think about

(0h10m) I tried the smallest case of $n=3$ and seems like only $k=0,1,3$ works. Then, I moved on to $n=4$ .

$k=0,1$ can be done with the same construction as $n=3$ .
$k=2$ is an interesting case. If we use one of the three lines that covers the most points, then this reduces to $n=3,k=2$ which we have case bashed to shown is not possible
Kind of feels like there will be some induction here
What if we don’t use any of the long lines for $k=2$ ? (long meaning covering the most lattice points)
Since we only get 4 lines to cover 10 points, it has to be $3,3,2,2$ . However all the lines that cover 3 points goes through the center point, hence it is not possible.
Finally, $k=3$ is possible because $n=3,k=3$ is possible, and $k=4$ is not possible because all the lines passing through 3 points are not sunny.

(0h20m) Seems like a sunny line can only clear at most $n/2$ -ish points, and yet the average line has to clear $(n+1)/2$ . This forces some lines to be sunny, but it’s not very helpful. Let’s focus on the induction idea.

Consider the longest diagonal. If all of them are joined together by one line, then we can use our induction. If not, they each have to be cleared separately on one line. This looks like a very useful result.
Oh wait, the diagram is symmetric, we have three longest lines to clear. If any of them are selected, then we can induct. Else, each of the $n$ lines need to clear one point from each of the long edges.
At this point I can feel we are already done. However, some (to be specific 3) of the points lie on multiple edges. How do we deal with that easily? Just count them all together.

(0h30m) Time to formalise the solution

We have $3(n-1)$ points on the perimeter. Assuming none of the three longest lines are chosen, each line can only cover 2 of these perimeter points. Hence, $3(n-1)\le 2n$ , which resolves to $n\le 3$ .
Hence for all $n>3$ , one of the three longest lines must be chosen, resolving to the $n-1$ case.
Only $k=0,1,3$ works for all $n$

Remarks: I keep getting confused between what is sunny and what is not-sunny. I think this is a very, very good question to put as Q1.

(0h45m) Finished drawing a diagram, which really looks quite unconventional. The tangency also looks quite random.

We let the tangency point be $T$ . From the diagram, seems like $MET$ and $NTF$ looks suspiciously collinear. This would make the tangency point a lot easier to deal with
If we define $T$ as the intersection of the lines $ME,NF$ , then can we prove that $BETF$ is concyclic?
This turns out not to be too hard, because $\angle MEB=90^\circ-\angle APB=\angle NFB$ .
Wow okay. Now just need to prove the tangency.

(1h0m) Notice that $\angle ACD=\frac{1}{2}\angle APD=\angle APN$ , hence $CANP$ and $DAMP$ are cyclic. Not sure how helpful that will be.

As a result, $\angle BFE=\angle CNA = \angle CPA$ , so $CP\parallel BF$ and $PD \parallel BE$ .
Also as a consequence, $AMN$ and $BEF$ are similar.
That means $\angle MAN = \angle EBF=\angle MTN$ . Wait, is $AMTN$ a parallelogram?
Well yes! Note that $\angle MEA = \angle MAP = \angle CDP = \angle DCP = \angle NAP$ , so $AN\parallel MT$ .

(1h15m) In fact, that means that $\angle TEF=\angle TFE$ as well due to the parallel lines. Hence, we just need $HT$ to bisect $\angle MTN$ .

Can we show that $H$ is the incenter of $MTN$ ?
Since $NH$ and $AC$ are both perpendicular to $PM$ , we have $\angle MNH=\angle ACD$ . So, we just need $\angle MNT=2\angle ACD=\angle AMN$ , which is true! And we are done.

Remarks: this reminds me of a lot of questions where the proposer has one main point in his full diagram and deliberately crafts the question to hide it. The goal of the solver is then to identify the main point and all the properties it has, and then prove them one by one. He has to stick to one definition and then prove the rest from there, avoiding any circular aguments. One memorable example of this (during NTST) was 2022 G5, but honestly now that I think about it a lot of geom has this concept. Anyways, a bit too easy for a Q2, similar to 2023 Q2.

(1h20m) Q3 is a construct and bound question. We need to find some $f$ such that $f(n)$ is relatively big. We begin as usual with all the trivial substitions

$P(1,1)$ gives $f(1)=1$
$P(a,a)$ gives $f(a)\mid a^a$ which suggests we should focus on primes (wow who would have guessed).
What if some prime gives 1? What if $f(c)=1$ in general? Maybe we can prove injectivity at 1? That’s an idea we can try later. Maybe we can prove injectivity in general?

(1h40m) Let’s do a bit of meta thinking. Because the problem is phrased this way, that suggest that we cannot actually find all functions. Furthermore, it is linearly bounded. That means that if we stare hard at $f(p)\mid p^p$ , we cannot have $f(p)>p$ for sufficiently large $p$ , limiting our options to $f(p)=1$ or $f(p)=p$ .

What if $f(p)=p$ for all $p$ ? Then for any $b$ , if we take a sufficiently large $p$ and use FLT, $p\mid b-f(b)$ , which forces $b=f(b)$ which is of course a solution.
In fact, this argument also works when there are infinitely many $p$ satisfying $f(p)=p$ .
If we combine this logic with the meta-thinking, this means that for any $f$ not the identity, all the large primes must give 1.
Can we find some way to eliminate $f(p)$ ?

(1h50m) Suppose we set $f(p)=p^{g(p)}$ . Then, from $P(p,q)$ we get $p^{g(p)}\mid q^{p^{g(p)}\cdot g(q)}-q^p$ . Converting to a $v_p$ statement using LTE, we get $v_p(q^d-1)+v_p(p^{g(p)}\cdot g(q)-p)\ge g(p)$ where $d\mid p-1$ is the order.

Suppose we pick $q$ such that $p\mid d-1$ but $p^2\nmid d-1$ . This is possible by Dirichlet.
Suppose $g(p)\ge 3$ . Then, $v_p(q-1)=1$ and $v_p(p^{g(p)}\cdot g(q)-p)=1$ , a contradiction.
This implies that $f(p)=1,p,p^2$ , a very big result.

(2h0m) Suppose that $f(p)=p^2$ . Then, $p^2\mid b^p-f(b)^{p^2}$ . If we only focus on $p\mid b^p-f(b)^{p^2}$ , then by FLT $p\mid b-f(b)$ as well, and hence if there are infinitely $f(p)=p^2$ , we get a contradiction.

Let’s take stock of the situation. We have proven that $f(p)\mid p^2$ , and further that if there are infinitely many $f(p)$ that is not 1, then $f$ is the identity. Hence, we are left with one case, that for all sufficiently large $p$ , $f(p)=1$ .For this case, can we force all $f(a)\le a$ ?

(2h10m) If for all sufficiently large primes $p$ , $f(p)=1$ , then for any other primes $q$ , we have $f(q)\mid p^q-1$ . This means that $q\mid p^q-1$ and hence $q\mid p-1$ , a contradiction again by Dirichlet unless $q=2$ . Hence, for all primes $p\ne 2$ , $f(p)=1$ .

Does something like $f(2)=4$ and everything else 1 work? Well no.
How about $f(\text{even})=4$ and $f(\text{odd})=1$ ? Surprisingly, that works! hence $c\ge 2$ .
We know that $f(a)\mid p^a-1$ for all primes larger than 3. Suppose $a$ is odd. Then, $f(a)$ is odd also since it divides $a^a$ . If it is not 1, then we can find an odd prime $p\mid f(a)$ , a contradiction. Hence, $f(\text{odd})$ really has to be 1.
Now it’s about the even numbers. In fact, $f(\text{even})$ cannot have any odd prime factors as well by the same logic, so they must all be powers of 2.

(2h20m) For some even number $a$ , we also have $f(a)\mid 3^a-1,5^a-1,7^a-1,\dots$ . Surely, that can limit the $v_2$ of $f(a)$ .

Note that $v_2(3^a-1)=v_2(a)+2$ , hence $f(a)\le 2^{v_2(a)+2}$ . This is at most 4 times as much as $a$ . Could this work?
Surprisingly yes! Keeping the construction of even as 4 and odd as 1, but changing $f(4)$ to 16 somehow works because $16\mid \text{odd}^4-1$ . And we are done!

Remarks: this really is quite easy for a Q3. Not sure if it is doable without Dirichlet, and I think I overcomplicated some of the arguments here. But hey, if it works it works. Final answer is quite surprising, but if you just ignore getting the answer and solve it like a normal FE, the answer will appear at the end.

More remarks after reading solutions: turns out that $f(p)=1$ for all sufficiently large $p$ is actually a pretty easy thing to get and there was no need for whatever I was doing. Also, it is actually possible to find all functions.

Day 2

(0h5m) Interesting sequence problem. The sequence only breaks when something has less than 3 proper divisors, i.e. it is $1,p$ or $p^2$ . Obviously we start by trying some cases:

If $a_1=6$ , then the sequence is 6 6 6 …, which works.
If $a_1=8$ , then the sequence is 8 7, fails
If $a_1=10$ , then the sequence is 10 8 7, fails
In general, the next term will look like $n/a+n/b+n/c$ . Not too sure if this is a NT or Alg question but maybe we can do some size bound based on modulo 6 or something?
The next number that actually works is 18, which also stays constant at 18. Ah, this is because $n/2+n/3+n/6=n$ . Hence, in general, all multiples of 6 that are not multiples of 4 or 5 work.
To be more mathematical, these are the numbers congruent to $6,18,42,54\pmod{60}$ . We call these the steady numbers.

(0h20m) In fact, there are only two ways that $a_2>a_1$ , which are the $(2,3,4)$ combo (increase of 13/12) or the $(2,3,5)$ combo (increase of 31/30). Can we use this to generate other numbers that work?

The first one, using the $(2,3,4)$ combo, will require us to find some solution to $13n=12(60k+6)$ . There is, surprisingly, an answer: $n=504$ , which leads to the sequence 504 546 546 546 …
Why does the solution set look so weird? Did I read the question wrong or something?

(0h30m) Anyways, the fact that having both 2 and 3 are the only ways to increase the sequence kind of suggests that we have to start with a multiple of 6. Can we make this rigorous?

Suppose we have $a_1$ not a multiple of 2. As mentioned, it will definitely decrease. Can $a_2$ be a multiple of 2? Since the three smallest divisors $a,b,c$ are odd, hence $v_2(\frac{1}{a}+\frac{1}{b}+\frac{1}{c})\le 0$ , hence it cannot be a multiple of 2.
Now for the non-multiples of 3. In this case we need to show that a non-multiple of 3 can never lead to a multiple of 3.
If lets say the three smallest divisors are something like $2,4,8$ , then we are done as that decreases the number by a factor of 7/8. Surely we can just spam every case?
I did this on paper and am a bit lazy to type it out, but to prove this claim, we can just clear the cases $2,p,q$ (gives an odd number), $2,p,2p$ (gives a non-multiple of 3), $2,4,p$ (gives a non-multiple of 3) as well based on either mod 2 or mod 3.
This means that the sequence will continue to decrease and cannot be infinite. Thus, every term is a multiple of 6.
This is good, because for multiples of 6, the next term will never be smaller. This gives us some structure to the sequence.

(0h50m) It seems that we only have to play with the factors of $2,3,5$ as the rest will remain untouched.

Consider if we start with $12k$ . Then, the next term will be $13k$ .
If we start with $30(2k+1)$ , then the next term will be $31(2k+1)$ . This is not good, because we are left with an odd number. We should thus never have to use the $(2,3,5)$ combo.
That leaves us with the $(2,3,4)$ combo. If we keep using it, we will be continuously taking out $2^2\times 3$ from the number. At the end, we should be left with one of the steady numbers.
This allows us to categorise all the possible $a_1$ s, although it looks quite ugly.

The complete solution set should be $12^n(60k+i)$ where $i\equiv 6,18,42,54\pmod{60}$ . What even is this…

Remarks: unfortunately I do not find this nice, as there is no real satisfaction in solving the question, I’m just left with a “did I get this right?” Kind of like 2022 N1 (yes, another NTST question). Difficulty wise, I think it is actually pretty hard for a contestant to nail a 7 point.

(1h0m) Inekoalaty. Nice. Let’s try out some strategies for both Alice and Bazza. For convenience, I will assume Alice is a female and Bazza is a male.

What if Alice just picks $\lambda$ every time? Then from the first move, if $\lambda^2>1$ already, Bazza is doomed. Hence, $\lambda >1$ is a win for Alice.
Next, what if $\lambda\le 1$ , which means Alice is picking relatively small numbers, but Bazza just picks the largest possible number to explode her bound? I.e. if we always set $x_{2i-1}^2+x_{2i}^2=2$ ? Then $x_{2i-1}+x_{2i}\ge \sqrt{2}$ , and hence $x_1+x_2+\dots+x_{2n}\ge \sqrt{2}n$ . Thus, if $\lambda<\frac{1}{\sqrt{2}}$ , Bazza wins.
Wait but pause. How do we know that Bazza can always pick his next term? Well, since at every turn he leaves $x_1+x_2+\dots+x_{2n}\ge \sqrt{2}n$ , Alice will have to pick something that is $\le \frac{1}{\sqrt{2}}$ , and so there is always something for Bazza to pick next. This guarantees his victory.

(1h20m) We are now left with the case that $\frac{1}{\sqrt{2}}\le \lambda \le 1$ . Maybe both of them can guarantee not to lose?

The intuition works something like this: Alice wants to keep SOS (sum of squares) high but sum low, so she wants the values to have a wide range. Bazza wants to keep SOS low but sum high, so he wants the values to be clustered.
With this in mind, what if Alice just keeps picking 0 every turn? Then, in order for Bazza to win, we must have $x_2+x_4+\dots+x_{2n}>(2n+1)\lambda$ but yet $x_2^2+x_4^2+\dots+x_{2n}^2\le 2n$ . In other words, $\lambda\le \frac{1}{\sqrt{2}}$ . Voila. Alice really can guarantee not to lose in this whole range.
Can Alice force a win by finally picking a very large number? Maybe if $\lambda$ is strictly greater than $\frac{1}{\sqrt{2}}$ ?
Suppose this has gone on for $2n$ rounds. We have that $x_2^2+\dots+x_{2n}^2\le 2n$ . If we pick the largest possible $x_{2n+1}=(2n+1)\lambda-x_2-\dots-x_{2n}$ , can we guarantee $x_2^2+\dots+x_{2n}^2+((2n+1)\lambda-x_2-\dots-x_{2n})^2>2n+2$ ?
Well yes! By Cauchy, this will be true for sufficiently large $n$ . Hence, Alice can just play the waiting game and spam zeros until the time is right, and then Bazza will be destroyed.

(1h55m) We have now cleared all cases less $\lambda=\frac{1}{\sqrt{2}}$ , which we have shown Alice can guarantee not to lose. Now for Bazza – in fact we can easily show that our Bazza strategy above allows him not to lose in this case as well. And we are done!

Remarks: I think this is a nice question, even though once again a bit easy for a Q5. The main difficulty lies in getting the correct intuition for what Alice and Bazza wants, and the rest follows naturally.

(2h0m) Very clean statement. We have the obvious bound of $2n-2$ , which works no matter which set of points we choose from. It definitely seems like we can do better asymptotically.

As usual, started with some small cases. However, this feels like the type of question where small cases don’t seem to give a good picture of the general case due to all the local constraints.
Perhaps it would be better to think of a large square and trying to see how we can stuff in rectangles.

(2h30m) If our empty squares are the main diagonal of the grid, then by considering the adjacent squares to this diagonal, no rectangle can cover both of them. Hence, at least $2n-2$ are needed. Maybe we can get the bound by thinking about mutually non-coverable squares? I.e. squares that cannot be covered by a single square (pretty lousy naming, I know, but it kinda makes sense for me intuitively).

If we just take every square on top of an empty one, that is $n-1$ squares that are mutually non-coverable. This gives us a bound of $n-1$ . Can we do better? Maybe using Erdos-Szekeres to find a “staircase”?
Suppose we take the longest increasing set of empty squares. In the diagram below, this is marked by the red squares. For each red squares, consider the cell on its direct top and left. For the empty squares above this “diagonal”, consider the cell directly above. For the empty squares on the right of the “diagonal”, consider the cell directly to the right.

I realised that I am missing two blue squares, and there are two on the same row, but no matter.

Is it guaranteed that none of these cells (marked in orange) can be covered by the same rectangle? Suppose it is possible. Then, we must have the case in the diagram below, where there is an empty square at the two purple slots. However, this will never happen in our construction of the orange cells

How many rectangles does that give us? By Erdos-Szekeres, we have at least $n+\lceil \sqrt{n}\rceil -2$ (-2 for the edges). That is a significant improvement from our previous bound. Can we somehow get equality?
This will mean that our largest possible increasing/decreasing subsequence is exactly $45$ , which is extremely tight as $2025$ is a perfect square. Essentially, our empty squares must be a slightly tilted square.

$n+2\sqrt{n}-3$

(3h0m) Perhaps we can add more mutually non-coverable squares? For example, the purple ones in the diagram below. Essentially, we need to find a better algorithm to select our mutually non-coverable squares.

If we look at the above, basically we are using the two “line segments” as see below.

What if I try to find the longest “cross” instead? That will look something like the diagram below.
This looks promising. Assuming the number of red squares is $k$ , this guarantees, at least $4\times 1+2\times (k-1)+1\times (n-k)-4=n+k-2$ . Hence, we just need $k\ge 2\sqrt{n}-1$ .

(3h30m) Is it possible to show that the sum of the lengths of the longest increasing subsequence and longest decreasing subsequence is at least $2\sqrt{n}$ ? Then, we can combine them together and afford a $-1$ at their intersection.

To do this, we can adapt the original pigeonhole proof of Erdos Szekeres. Suppose the longest increasing sequence has length $A$ and the longest decreasing sequence has length $B$ . Label each square with two numbers $a_i,b_i$ , the length of the longest increasing (resp. decreasing sequence) ending with that square. Then, each pair of labels must be different, leaving only $AB\ge n^2$ possible pairs.
By AM-GM, $A+B\ge 2\sqrt{n}$ , and we are done!

Remarks: I actually think this is a pretty motivatable solution, where one thing leads to another and things kind of just fall into place. The main idea of considering the “mutually un-coverable” squares is a very intuitive idea, and then choosing those next to empty squares is very logical as well. Using the longest increasing subsequence is motivated from the “main diagonal” set of empty squares. Suitable difficulty for a Q6, and looking at the scores I really expected more people to solve it. I wonder what was the main bottleneck…

And that’s it! I think this is the easiest IMO paper to FC in quite a while, even more so than 2022.

Did I make any mistakes? Let me know 🙂

It’s actually insane that there’s an SG problem on the IMO. Congratulations to the proposers!

IMO 2025

Day 1

Day 2

Comments

Leave a comment Cancel reply