IMO 2024 Livesolve (Day 2)
(David here.) Continued from Day 1 here.
Problem 4
(IMO 2024/Q4) Let $ABC$ be a triangle with $AB < AC < BC$. Let the incenter and incircle of triangle $ABC$ be $I$ and $\omega$, respectively. Let $X$ be the point on line $BC$ different from $C$ such that the line through $X$ parallel to $AC$ is tangent to $\omega$. Similarly, let $Y$ be the point on line $BC$ different from $B$ such that the line through $Y$ parallel to $AB$ is tangent to $\omega$. Let $AI$ intersect the circumcircle of triangle $ABC$ at $P \ne A$. Let $K$ and $L$ be the midpoints of $AC$ and $AB$, respectively.
Prove that $\angle KIL + \angle YPX = 180^{\circ}$.
We spent 25 min drawing diagram in Geogebra (heh).
1. The tangents through $X$ and $Y$ actually concur on $AI$. This is because with $AB$ and $AC$, they form a rhombus.
2. The obvious thing to do to eliminate the two midpoints is to homothety $I$ out 2x to $J$. This gives $\angle KIL =\angle BJC$. And we can safely erase $K$ and $L$.
3. Maybe we could "push out" $PX$ and $YX$ - construct $Q$ such that $BQ//PX$ and $CQ // PY$, and maybe we'd have that $Q$ is also on the angle bisector? But then we'd need $DX\cdot XB = DY\cdot YC$ (where $D = AI\cap BC$), which seems false.
4. Maybe $K,X,P$ collinear? But this is false.
5. After staring for a while: realize that $B,X,J,P$ are concyclic. This is easy, because $\angle JXC = \angle C = \angle BPJ$. Similarly, $C,Y,J,P$ are concyclic. Then we're done by some angle chase.
Afterthoughts. Pretty clean geometry. The double circle is a common theme for lots of circle-to-circle tangency problems.
Problem 5
Turbo the snail plays a game on a board with $2024$ rows and $2023$ columns. There are hidden monsters in $2022$ of the cells. Initially, Turbo does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.
Turbo makes a series of attempts to go from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move, and Turbo remembers whether or not each cell he has visited contains a monster. If he reaches any cell in the last row, his attempt ends and the game is over.
Determine the minimum value of $n$ for which Turbo has a strategy that guarantees reaching the last row on the $n$-th attempt or earlier, regardless of the locations of the monsters.
1. We started with some small cases - let the generalization have $N$ columns, $N+1$ rows and $N-1$ monsters. It seem that the answer for $N=2$ is 2, and the answer for $N=3$ is 3.
2. It seems like $n\le N$, because one of the columns has to work.
3. For a lower bound: maybe we can put a monster the first time we reach level $i$? This almost works, except that there's a restriction that monsters cannot be on the same column (so we could plausibly enter a row on a column which already has a monster).
4. Actually, this is a pretty strong condition. I had a vague idea that this "clears out a grid" which can be used to safely traverse a lot of the grid e.g.
x x x x x x
x o x x o x
o m o o o o
x o x x o x
o o o o m o
x o x x o x
x x x x x x
5. Given that no two monsters are on the same column or row, the only way $n$ monsters can block $n$ columns has to be diagonal.
6. This suggests the following approach to get roughly $\log n$ using binary search:
- check where the monster is on the leftmost and rightmost column
- check the "middle" column. depending on the position of the middle monster, we will find that one side (either left to middle or middle to right) is not a diagonal, so we can pass on that side
- repeat the second step.
7. We were convinced that this was right, because to find the column with no monsters we could have one of $N$ distinct cases (with diagonals on either side). So one way to capture this is to draw the following "double diagonal"
x x x x x
o o x x x
x o o x x
x x o o x
x x x o o
x x x x x
When Turbo crosses the diagonal, we can decide whether to put a monster along the first or second diagonal (which corresponds to putting the hole to the left or the right) - so we can pick the larger side to place the diagonal.
At this point we claimed victory, but we were given the bad news that the answer was not $\Theta(\log N)$!
The reason why this doesn't work is because we don't have to cross into the second diagonal; we can actually "walk along" the first diagonal with absolutely no repercussion from this strategy.
8. Continuing the idea from (4) - could we try to "get around" a monster? Well, we must block one of the diagonals along the monster, otherwise we can just go around it and follow the path below it:
x x m m x x
x m x x m x
m x x x x m
But we're still searching for an unknown hole somewhere...
9. The lesson we learnt from (7) was that this is the latest possible diagonal we could safely explore:
x x x x x
x o o x x
x x o o x
x x x o o
x x x x o
x x x x x
So putting this and (8) together, we piece together the following strategy:
start from one right of the top left, and go right-down until monster.
then, go from left of the monster left-down until a monster. (This is to rule out the diagonal going the other way - in that case we win!)
if we do find one, get to right of monster #2. Then go right until you're below the first monster (which somewhat follows (4)).
Hence $n\ge 3$! And it's easy to show that $n\ge 3$ using (3).
Afterthoughts. I think it's really easy to get stuck with the $n=\Theta(\log N)$ idea - we might have been during the fakesolve if not for the prompt. Makes me think of the box question (IMO 2010/5), which had about 60 near-solves. Nevertheless, the stats prove me wrong; with about 182 near-solves (defined as $\ge 5$ points), this ranks on the easier side for a medium problem!
Problem 6
(IMO 2024/6) Let $\mathbb{Q}$ be the set of rational numbers. A function $f: \mathbb{Q} \to \mathbb{Q}$ is called aquaesulian if the following property holds: for every $x,y \in \mathbb{Q}$, $$ f(x+f(y)) = f(x) + y \quad \text{or} \quad f(f(x)+y) = x + f(y). $$ Show that there exists an integer $c$ such that for any aquaesulian function $f$ there are at most $c$ different rational numbers of the form $f(r) + f(-r)$ for some rational number $r$, and find the smallest possible value of $c$.
1. Substituting $x=y$ we get that $x+f(x)$ is a fixed point.
2. If $x$ was a fixed point,
$$f(x+f(y)) = x+y \quad \text{or} \quad f(x+y) = f(x+f(y))$$
it doesn't seem super helpful (...yet?).
3. If $x,y$ are both fixed points, then $x+y$ is a fixed point.
3.5. I also had some stray thoughts about interpreting $f$ as a directed graph. Then this means that each $x+f(y)$ and $y+f(x)$ are linked (in some direction).
4. Try $x=f(0), y=-f(0)$, because this cancels the $f$ in the second equation. Then $f(f(0) + f(-f(0)))$ or $f(-f(0)) = 0$. Conclusion: $f(?) = 0$.
5. Let $x=y=a$ such that $f(a)$ = 0. Then $f(a) = a$, so $a=0$. Combining with (4), $f(0) = 0$.
6. Let $z$ be a fixed point, and substitute $(x,y) = (z,-z) $. Then $f(z+f(-z)) = 0$ or $f(0) = z+f(-z)$, so $z+f(-z) = 0$, hence $-z$ is also a fixed point.
7. More generally, for $y=-f(x)$, we have $x+f(-f(x)) = 0$. So $f(-f(-x)) = x$. $f$ is bijective!
8. At this point we started suspecting $c=2$.
9. We make the substitution $y \mapsto -f(y)$. This transforms the condition to $$f(x - y) = f(x) - f(y) \quad \text{or} \quad f(f(x) - f(y)) = x-y$$ Using (7), we can write the second condition as $f(x) - f(y) = -f(y-x)$.
10. If $x-y = t$ and $f(x+t) - f(x) = f(t)$ or $-f(-t)$.
11. At some random point I wrote down the construction $f(x) = \lfloor 2x \rfloor - x$. The idea was to "flip the fractional part", but in light of $f(-x)$ being the involution I'd say it was more of flipping the integer part if anything.
12. Following (10): there's the idea that we shouldn't be able to "switch" between the two choices too much. In particular, for each $t$, we can split it into a good set (where $x$ follows the Cauchy equation) and a bad set (where $x$) doesn't, and that this split should be the same across $t$'s.
Concretely, define: $G_k := \{x \mid f(x+k)-f(x) =f(k)\}$ and $B_k := \{x \mid f(x+k) - f(x) = -f(-k)\}$. Then $B_k, G_k$ form a partition of $\mathbb Q$ if $f(k) + f(-k) \neq 0$, and furthermore for two different such $k$'s we expect the partition $\{B_k, G_k\}$ to be the same (even though their order might be flipped). We get this because $f(x+k_2) - f(x+k_1)$ can only take two possible values.
13. Actually, the good set should form an additive subgroup of $\mathbb Q$. We don't know this, but the fixed points are a subset of the good set and those form an additive subgroup. It should also be a nontrivial additive subgroup, otherwise $x+f(x) = 0$ for all $x$ which is trivial.
(We didn't get this during thel live solve, but in retrospect $0\in G_k$, which let's us figure out which one the good set was.)
14. What about considering this in the other direction, with a fixed $x$ "across" $k$'s? This looks like thinking about chains of the form $$[f(x+k)-f(x)] + [f(x+2k) - f(x+k)]$$ which can always only be one of two possible values, but each summand is also one of two possible values. And then maybe we can chain them together.
15. Stupid idea: actually, $$f(x+k) - f(x) = f(k) \pmod {f(k) + f(-k)}$$ so by chaining them together we have $$nf(k) \equiv f(nk) \text{ or } -f(-nk) \pmod {f(k) + f(-k)}$$
16. Actually, the reduced system $$\begin{cases} f(x+k) - f(x) = f(k) \text{ or } -f(-k)\\ f(-f(-x)) = x \end{cases} $$ is equivalent to the original FE, so we can safely work using this instead.
17. We might as well consider $g(-x) =f(x)$, so we can get a neat involution instead:
$$\begin{cases} g(x+k) - g(x) = g(k) \text{ or } -g(-k)\\ g(g(x)) = x \end{cases}$$
18. We have:
$$ \begin{align*} g(y) - g(x) &= g(y-x) \text{ or } -g(x-y),\\ g(-x) - g(-y) &= g(y-x) \text{ or } -g(x-y). \end{align*} $$
Subtracting the second from the first gives $$g(y) + g(-y) - (g(x) + g(-x)) = 0 \text{ or } \pm [g(y-x) + g(x-y)].$$
This is all very tempting to write in terms of $h(x) = g(x) + g(-x)$, which is that $h(x) = h(y)$ or $h(y) - h(x) = \pm h(y-x)$ (with $h$ even).
19. Let's try some small cases. If $h(1)\neq 0$, then $h(2)$ is either 0, $h(1)$ or $2h(1)$, and so on to get that $h(n)$ is a multiple of $h(1)$ for all $n\in \mathbb Z$. But at some point, our additive subgroup from (13) kicks in and we get $h(n) = 0$ for some $n$ and that $h$ has period $n$.Writing $y=x+t$, we must also have $h(x+t) = h(x)$ or $h(x+t) - h(x) =\pm h(t)$. This suggests taking the largest possible $|h(t)|$ for integer $t$. However, we also know that $h(x+t) - h(t)$ can change by at most $2h(1)$ when we increase $x$ by 1, and it has to eventually change sign due to the periodicity. Hence, $|h(t)| \le 2|h(1)|$. As a result, we can at most see 3 distinct values of $t$.
Unfortunately, it seems that something like
$$h(x) = \begin{cases} 0 & \text{for even integer }x\\ 2 & \text{for odd integer }x\\ 1 & \text{for all other } x \end{cases}$$ seems to work. We spend a long time trying to construct an $f$ or $g$ that gives this but to no avail.
Postmortem. We could have got $c\ge 2$ by doing (19) at the $f$ (or $g$) level instead of going to $h$, where we lost information. Just goes to show that you can have probably all possible progress on a problem and still trip up somewhere. I don't know how one might overcome this in a contest setting - maybe a toilet break? Or just setting some point during the test where you take stock of your current progress and try to get a bird's eye view? P3/P6's are hard.
It turns out that this FE is still valid for $\mathbb R\to\mathbb R$! I don't know if knowing that, I would still propose the $\mathbb Q$ version.
In retrospect, probably somewhere among (12-15) one can find the other solution (which actually uses the fact that it was over $\mathbb Q$), but we definitely missed it during the livesolve.
Comments
Post a Comment