IMO 2024 Day 2

Jul 19, 2024

—

Was tough doing this in camp, but I’m finally done. It’s rare to see someone’s thought process for an entire paper, so here’s mine – hopefully it’s sufficiently entertaining.

Needless to say, spoilers below.

Here we go again!

(0h0m) First thoughts:

Ok GCA. Is that an FE?! What kind of word is aquaesulian?
Why is the easy geom so long?
Why is Q5 so long?
This paper actually looks bad, let's see how it goes..

(0h5m) Ok, diagram drawn. It actually does not look that bad, although the two angles $\angle KIL$ and $\angle XPY$ are quite weird.

Let the intouch points be $D,E,F$ . Then, $DI$ passes through the tangency point from $Y$ , which we will call $Y_1$ .
Why am I so tempted to draw the Sharky-Devil point?
What happens if we draw in the circumcircle of $(XYP)$ ?
Why is this actually hard? What even are these angles?? Do I split $\angle KIL$ ? Midpoints and incenter are so weird.

What happens if we draw the line through $I$ parallel to $BC$ ? Let it intersect $AB$ , $AC$ at $F_1$ , $E_1$ . Then, $\angle LIE_1$ looks suspiciously like $\angle XPI$ . If we can prove this, then we are done.

Wow. I guessed that $\triangle LIE_1$ and $\triangle XPI$ are similar, and the only way to tell that is if $\angle XIP= \frac{1}{2}\angle B$ . Hence, the guess is wrong.
This means that $ID$ and $IP$ are isogonal in $\angle XIY$ .
By yet more angle chasing, $\angle BIX=\angle CIY=\frac{1}{2}\angle A$ .
In particular, $BIX$ spirals to $BIA$ .

Now the midpoint $K$ seems approachable, because the spiral sends it back to the midpoint of $BI$ (call this $O_B$ ), which is the center of $AFID$ .

Then, $\angle KIA=\angle O_BXI$ .
Could $\triangle XPI$ be similar to $\triangle XO_BD$ ? We just need to bash $XI/XD=PI/O_BD$ .
It’s true! This is because $O_BB/PB=XD/XI$ , and we can use the chicken feet theorem.
OK we are probably done.

Note that $\angle XPI=\angle XO_BD$ .

$\angle XO_BD+\angle IXO_B=(\angle O_BXB-\frac12 \angle B)-(\angle IXB-\angle O_BXB)$ , and we are done by angle chase!

This was a hard Q4, I feel.

(0h45m) Time to read this long, long statement.

This is quite a funny statement, I kinda like it.
One easy bound is $n\le 2023$ , by trying every column. I have a suspicion this might be the best.
There is no point for Turbo to return to a point if he already knows there’s a monster there.
What if we just block Turbo’s first 2022 attempts?
Oh, they must be in different columns… and different rows. This still seems very suspicious though.

This means that for every monster that we discover, we can say for sure that the cells in its row and column are free.

If we go down the first column to find the monster, then in our next move we can try to use the first column as much as possible, except for three cells where we use column 2. This limits the position of the monster in position 2 to two positions.
If we keep going, we get a “diagonal” of monsters.
We are always off by a path by just one or two squares.

Hold up. If we guess three random columns, we can free up enough rows and columns to effectively walk through the whole thing. Hmm. Is $n=3$ ?

Never mind, I am tripping. This fails if the three monsters are in a “diagonal”.
On the other hand, if they are not in a diagonal, then we are done.
What if we dictate monsters to always be on a diagonal, and when Turbo reaches anything on the diagonal we immediately declare it monster?

Put another way, what we can do as Turbo’s enemy is to declare the first square he does not know is free to be monster, and try to keep the monsters in a sort of “diagonal”.

However, there isn’t really a diagonal, since there are $2023$ columns and $2022$ rows.
I would be very surprised if the answer is not $\approx n$ or constant.

(1h20m) I found a $\log$ construction. Here is the strategy:

For $2n$ , Turbo goes straight down $n,n+1$ . They have to be in consecutive rows. Hence, they determine the direction of a “diagonal”.
WLOG the diagonal is topleft – rightbottom. Then, consider the top left rectangle and the bottom right rectangle. One of them is wider than it is tall. We can thus use the same strategy on this rectangle.
This means $f(2n)\le 2+f(n-1)$ and $f(2n+1)\le 2+f(n)$ .

Ok, it is time to try small cases for real.

2 columns: 2
3 columns: 3
4 columns: 3! (Just go down columns 2,3. They have to be in consecutive rows. Either ways, we have a complete path.)
5 columns: 4 is possible. Is 3 possible? Can we always block the first 3 paths?

Can we strong induct on the enemy’s move as well?

Here’s an interesting idea: if a cell is a monster, we can mark it’s “cross” safe. However, for rows up and down it (and columns not adjacent to that monster), we can kind of mark it “safe” as well, as if it occupied then we can guarantee a path in the next move.
What if we change the win condition to reaching either the bottom or the left of the grid? I think this may be easier to induct on, since that is how the board looks after the induction.

(1h50m) OK I think I got it. Let the left column be labelled $1$ and the right column be labelled $n$ . Then, for $i\le \frac{n}{2}$ , put a pseudomonster in column $i$ row $i$ . For $i>\frac{n}{2}$ , put a pseudomonster in column $i$ row $i-1$ . This kind of forms a “wall” of size $n$ .

Call a rectangle fat if its width is one more than its height.
Once Turbo reaches any point on this wall, declare there to be a monster there. We then update the wall as follows:
If the top left (resp. bottom right) rectangle is fat and has width $m$ , Replace it’s pseudomonster with a wall of length $m$ .
The other rectangle would be a square. We keep it’s pseudomonsters. Note that if Turbo ever ventures into that territory and reaches these square pseudomonsters, we can completely block it off. Hence, we can assume Turbo only makes move on the fat rectangle.

This gives $f(2n)\ge 1+f(n)$ and $f(2n+1)\ge 1+f(n)$ .

This confirms that the answer is logarithmic. However, the coefficients don’t match.

We can improve Turbo’s strategy. While we need to guess two columns at the start, after that we can just keep zooming on the fatter rectangle. This will make us off by a constant factor between both bounds.
Can we guess the general formula?
For odd $2n+1$ , if Turbo reaches the middle pseudomonster first, we can delay the decision on the orientation of the diagonal to gain one extra move.

(2h40m) OK this is going nowhere. Let’s just solve $n=5$ first.

Can the enemy always make Turbo go 4 moves? Suppose we block the very first step he takes. Then, in his next attempt he will have to enter the second row on a different column, so we can block that too.
Wait… acutally Turbo can finish it in three like this.
In fact, if Turbo can find the monster in the first row, he can guarantee to finish after two more attempts if he just tries going down its left and right.
Let’s say Turbo goes through the entire first row to find the monster. The only cases where he cannot guarantee to finish on the first move is when the monster is on the first or fifth column. WLOG it’s the first.
What happens then? If he tries going down the second column, he may hit a monster on the second row. Then, he will need 2 more attempts.
This is hard.

(3h30m) WHAT?! After a LOT of bashing, here is a strategy for Turbo in 3 moves.

if the top left most square is a monster, then we can zigzag down -> left -> down -> … from the third column. This works because if we ever hit a monster, we can turn around in the next attempt and reach the bottom through column 1.

The best part is, this generalises. Such an underwhelming problem. I was so ready to divide and conquer to get some logarithmic result. It’s honestly a miracle I even recovered from the log rabbit hole, and probably many people will get stuck here too.

(3h45m) No time for Q6. What in the world is aquaesulian? I’ll call it good from now on.

We have the equation $f(x+f(y))=f(x)+y$ or $f(f(x)+y)=x+f(y)$ . We want to show that $f(x)+f(-x)$ can take finitely many values.
In fact, it is more than “finitely”, it is “finitely across all good functions”. And we need to find the smallest possible upper bound.

We have that $f(x+f(x))=x+f(x)$ always.

I think I have an idea of how to get $f(x)+f(-x)$ . Consider $P(x+f(y),-y)$ .
Case 1: $f(x+f(y)+f(-y))=f(x+f(y))-y$ .
Case 2: $f(f(x+f(y))-y)=x+f(y)+f(-y)$ .
Now if $f(x+f(y))=y+f(x)$ , then either $f(x+f(y)+f(-y))=f(x)$ or $f(f(x))=x+f(y)+f(-y)$ .

Let $T$ be the set of $t$ for which $f(f(t))=t$ .

Obviously, $P(0,t): f(f(t))=f(0)+t$ or $f(f(0)+t)=f(t)$ .
We have $P(f(t),y): f(f(t)+f(y))=t+y$ or $f(t+y)=f(t)+f(y)$ .
If $t\in T$ , so is $f(t)$ .

Can we show $f(0)=0$ ? If it is not, then from $P(f(t),0)$ , we mus thave $f(f(t)+f(0))=t$ . Set $t=f(t)$ , then $f(f(0)+t)=f(t)$ .

Let $S$ be the set of $s$ for which $f(s)=0$ .

$P(s,y): f(s+f(y))=y$ or $f(y)=s+f(y)$ .
If there exists $s\ne 0$ , then $f(s+f(y))=y$ for all $y$ . Take $y=s$ , contradiction.
Hence we get our first result: $f$ is injective at $0$ .
We need to find any $f(c)=0$ .
$P(x,-f(x)): f(x+f(-f(x)))=0$ or $f(0)=x+f(-f(x))$ .
Hence, $f(-f(x))+x=f(0)$ for all $x$ . Put $x=f(0)$ , we get a contradiction.

We now have more progress: $f(0)=0$ and $f$ is injective at $0$ . $P(x,0): f(x,-f(x)): f(x+f(-f(x)))=0$ or $0=x+f(-f(x))$ . Either ways, $f(-f(x))=-x$ . This shows that $f$ is both injective and surjective.

$P(x,-f(y)): f(x-y)=f(x)-f(y)$ or $f(f(x)-f(y))=x-y$ .
If $f(x)-f(y)=-f(z)$ then either $f(x-y)=-f(z)$ or $z=x-y$ .
If $f(f(x)-f(y))=x-y$ then $f(f(x)-f(y))=f(-f(y-x))$ so $f(x)-f(y)=-f(y-x)$ .
In other words, $f(x)-f(y)$ is either $f(x-y)$ or $-f(y-x)$ .

Hence $f(x)=f(x-y)+f(y)$ or $f(y)-f(y-x)$ .

Let $A$ be the set for which $f(a)=a$ .

We have $x+f(x)\in A$ .
The thing I noticed is: if $a,b\in A$ then so is $a+b$ from $P(a,b)$ .
Furthermore, if $a\in A$ then $-a$ is too from $f(-f(a))=-a$ .
Hence, $A$ is closed under addition.
Over $\mathbb{Q}$ , what does this mean?
If $x+f(y)\in A$ , then $y+f(x)\in A$ . Hence, $f(x)-x=f(y)-y$ .
If $x-y\in A$ , then $f(x)-x=f(-f(y))+f(y)=f(y)-y$ .

This looks important: if $x-y\in A$ then $f(x)-x=$ constant. For example, if we take some $a\in A$ , then the set $\{x+na\}$ satisfies $f(x+na)=x+na+c$ for some constant $c$ .

I guess we need to classify $A$ ?
OK let’s go back to our first idea. Suppose $f(c)+f(-c)=k\ne0$ . Then, $P(x+f(c),-c): f(x+k)=f(x+f(c))-c$ or $f(f(x+f(c))-c)=x+k$ .
If $f(x+f(c))=c+f(x)$ for some $x$ , then $f(f(x))=x+k$ .

(4h30m) Time’s up! Closing thoughts:

Q4 is a hard geom for its position. This will probably make the bronze cut off quite low.
Q5 is so out of place. It’s not a bad problem, but I think it’s quite toxic to put this as P5. More people would probably solve it if it were P4. I cannot get over how the logarithmic solution looks so natural and intuitive.
In fact, I would argue that if it were a P4, it would have been as difficult as a normal P4. Similarly, if it were a P6, it would have been as difficult as a normal P6. Weird but true?
Q6 does not look that hard? I kind of feel I’m almost done.

Appendix¹

(Post mock) Ok let’s continue the FE.

If $x-y\in A$ , then $f(x)-x=f(y)-y=c$ .
Taking $P(x,y)$ where this is true, we get $f(x+y+c)=x+y+c$ . This means that $x+y+c\in A$ .
Hence, $x-y\in A\implies x+f(y)\in A$ . Since $x+f(x)\in A$ , this means that $x-y\in A\implies f(y)-f(x)\in A.$ Ok nvm those are the same thing.
The only thing we get from $P(x\not\in A,a)$ is $f(x+a)=f(x)+a$ . This is in fact true for all $x$ .
The only condition that we have not used is $P(x,y)$ when $x,y\not \in A$ .
If $x+f(y)\in A$ then $y+f(x)\in A$ . In fact, they are equal too. So $x+f(y)\in A$ implies $f(x)-x=f(y)-y$ .

Let’s actually try to construct something non-trivial.

Suppose $A=\mathbb{Z}$ . Then, $f(x)=x+n$ for some integer $n$ . Set $f(x)=x+g(x)$ .
Also, $f(x+n)=f(x)+n$ , so we only need to solve for $x$ between 0 and 1.
In other words, only $P(x,y)$ with $x,y$ between $0$ and $1$ matters.
We have that $f(x)=f(x-y)+f(y)$ or $f(x)=f(y)+1-f(1-x+y)$ .
Let’s say we put $y=2x-1$ . Then either $f(2x-1)=-1$ (which is impossible) or $f(x)=f(1-x)+f(2x-1)$ , or $f(x)=f(-x)+f(2x)$ .
Hold up we can do this in general: we have that $f(x)=f(x-y)+f(y)$ or $f(x)=f(y)+a-f(a-x+y)$ .
Set $y=2x-a$ . Then the second one is true only when $f(2x-a)=-a\implies x=0$ by injectivity.
Hence $f(x)=f(a-x)+f(2x-a)$ for all $x\ne0$ , or $f(x)=f(-x)+f(2x)$ , true even when $x=0$ .

I’m getting too distracted. Let’s go back to construction.

$f(x+1)=f(x)+1$ and $f(n)=n$ . What can we do?
Suppose $f(x)=x+1$ for a range of $x$ . The problem is that any of it’s differences must have $f(x)=x$ .
Suppose we have $f(x)=x$ for $0\le x<\frac12$ and $x+1$ for the rest.
Unfortunately, $f(-0.01)$ must be $-0.01$ also.
We cannot have a “range” of $f(x)=x$ .
We cannot have a “range” of same $f(x)-x$ s. This is hard man.
What if $f(x)=-x$ for non-integer $x$ (between 0 and 1)?
If $x>y$ , then $f(x+f(y))=f(x-y)=-x+y=f(x)+y$ . Wow!

This gives the answer of $c=2$ . Could this be the answer? Perhaps for all $x\not \in A$ the value $f(x)+f(-x)$ is constant?

As with above, if $f(r)+f(-r)\ne 0$ , then $f(f(x))=x+f(r)+f(-r)$ or $f(f(x)+r)=x+f(r)$ .
Let $f(s)+f(-s)\ne0$ also. We just need to find $x$ such that $f(x+f(r))=f(x)+r$ and $f(x+f(s))=f(x)+s$ .

Wait! Either $x=r$ or $x=s$ must work! What just happened…

Most of the stuff above was redundant, but that was a beautiful finish.

I took about 4 hours total to solve Q6, so I was wrong about being close to finishing. (Perhaps I was close to bounding c=2, but very far from a solution.) The hardest part, of course, is deciding to actually try for a c>1 solution set. ↩︎

Comments

4 responses to “IMO 2024 Day 2”

a person

Jul 26, 2024

An AI managed to score 28/42 on this year’s IMO, one mark away from gold. What are your thoughts on this? Will IMO still have a purpose if, someday, AI can consistently score full marks on the exam? Or perhaps will the problems just get ever more difficult?

Link to article: https://www.nextbigfuture.com/2024/07/ai-achieves-silver-medal-standard-solving-international-mathematical-olympiad-problems.html

LikeLike

Reply
1. Gabriel Goh
  
  Jul 28, 2024
  
  Oh definitely. Unlike say chess, where engine preparation is a very real thing, it is hard to use “maths olympiad AI” to improve a human’s skill level. This means that when we gather 600 people in a room to work on the problems, the determinants of success and the value of each medal does not change. Until such time where you can “game the system” with AI, I believe the current IMO philosophy (and difficulty) wouldn’t change. (And when such a time comes, I believe the IMO will adapt accordingly.)
  
  I do worry about potential cheating applications though, since from my experience the entrance checks were not in any way strict.
  
  LikeLike
  
  Reply
  1. a person
    
    Jul 28, 2024
    
    Makes sense. Put another way – if we look past the practical issue of cheating, however good AI is at solving IMO questions does not matter as much, because IMO was always designed to reward human ingenuity and hard work. So what if AI surpasses the world’s brightest mathematical minds? It doesn’t – and should never – stop us from rewarding young people for displaying their creativity and resilience in problem-solving, traits that we value so highly today. As you said, the value of a medal (or even participating, for that matter) does not change.
    
    And even if AI were to become extremely proficient in solving IMO problems, I don’t think that would ever stop Math Olympiad enthusiasts, retired or active, from working on and discussing the problems. One of the key lessons taught by Math Olympiad is that even if someone, or many people, are better than you at something, as long as you are interested in it, you should pursue it. With this spirit, a powerful problem-solving AI becomes more of an afterthought.
    
    LikeLiked by 1 person
  2. Gabriel Goh
    
    Jul 28, 2024
    
    Well said!
    
    LikeLike

IMO 2024 Day 2

Appendix1

Comments

4 responses to “IMO 2024 Day 2”

Leave a reply to a person Cancel reply

Appendix¹