IMO 2026 Day 2 Livesolve

-

 

It's Glen again.

At last, I have time to write this out. Again two of these were done without paper but I've tried to reconstruct the thought process as faithfully as possible. The wording might be a little fuzzy because I'm transcribing pictures in my head. Probably everything would have been better written out if I had given names to everything. Apologies in advance.

Problem 4

(IMO 2026/4) Shan-Yu and Mulan are playing a game. Let $\theta$ be an angle with $0^\circ<\theta<180^\circ$ known to both players. Initially, Shan-Yu makes a paper triangle $\mathcal{T}$ with measurements of his choice. Then, they repeatedly perform the following steps:

  • If $\mathcal{T}$ has at least one angle measuring exactly $\theta$, then the game stops and Mulan wins.
  • Otherwise, Mulan chooses a point $P$ on the perimeter of $\mathcal{T}$, different from its three vertices. She then makes a straight cut from $P$ to the opposite vertex of $\mathcal{T}$, splitting it into two triangles.
  • Shan-Yu discards one of the two triangles. The remaining triangle becomes the new $\mathcal{T}$.

For which real values of $\theta$ can Mulan guarantee her victory in finitely many steps, no matter how Shan-Yu plays?

I just realised that I know the problem proposer. Congratulations, Valentin!

  • This reminds me of Jeck's SMO problem. Open 2022/5 or something? That was cursed. (Edit: It was SMO Open 2023/5.)
  • It also reminds me of that robot problem from SMO Open 2019. I think it was Q3? (Edit: Yes it was.)
  • I feel like some similar approach to that should work: for values for which Mulan loses, we need to show that Shan-Yu can always pick a triangle for which some condition is met.
  • What about Mulan's strategy? I think in that robot question there was some sort of monovariant. Maybe we should first think about what the answer should be.
  • Here's another way of thinking about this: suppose we can cut the triangle into a bunch of smaller triangles which all have a correct angle. Then at each stage Mulan can force Shan-Yu to choose between two halves of the decomposition, until we're left with a single triangle.
  • From what I remember of the Jeck SMO problem, the answer was something like $<120^\circ$ but it was some cursed construction that I can't recall.
  • Actually, we need some other conditions on our decomposition. At each stage, Mulan has to be able to cut our current triangle into triangles. So that's a lot more restrictive.
  • Ok, so if $\theta=90^\circ$ she can draw an altitude and win.
  • I guess more generally she can radiate lines with angles of $\frac{180^\circ}n$ between them. By choosing a relevant point on one of the sides probably one of the lines will go through the opposite vertex?
  • Yeah, by considering the angle of a Cevian from the largest angle to the opposite side this always exists.
  • Great, then now she can do exactly as stated above. The only restriction is that her first move has to be along the cut that goes through the opposite vertex.
  • More generally, she can try to radiate from one of the vertices. So each vertex angle can't be a multiple of $\theta$. I guess for any $\theta$ Shan-Yu can always achieve that.
  • Aha, so for the remaining $\theta$, the condition that Shan-Yu wants to maintain is: none of the angles are multiples of $\theta$. Can he do that?
  • Look at the four new angles formed. Suppose two of them are multiples of $\theta$. There are four cases. These correspond to $180^\circ$ and the three vertex angles being multiples of theta (for two of them, you have to use the deep fact that an external angle is the sum of the opposite internal angles. Not gonna lie I got stuck on this for a minute). So he can maintain this forever and Mulan can't win. Cool.

I take back what I said yesterday. This IMO doesn't have 5 questions; it has 4. (Difficulty aside, this is a very nice problem, though.)

Problem 5

(IMO 2026/5) Let $\mathbb{R}_{>0}$ be the set of positive real numbers. Determine all functions $f :\mathbb{R}_{>0}\to \mathbb{R}_{>0}$ such that  $$\sqrt{\frac{x^2 + f(y)^2}2}\ge \frac{f(x) + y}2 \ge \sqrt{xf(y)}$$ for every $x ,y\in\mathbb{R}_{>0}$.

  • What in the QM-AM-GM. Isn't this always true?
  • Oh, the terms in the middle are swapped.
  • Ok, put $x=f(y)$, then the first and last thing are equal. This gives us $\frac{f(f(x)) + x}2 = f(x)$, so $x,f(x),f(f(x)),\ldots$ are in arithmetic progression.
  • Ah, this means that $f(x)\ge x$ for all $x$.
  • Is there a way to chain this with the existing inequalities to get something interesting? I try for a bit but only get things that already follow from QM-AM-GM.
  • A common trick for $\mathbb{R}^+ \rightarrow \mathbb{R}^+$ FEs is to try to show continuity. Maybe I could try to do that.
  • Put $(f(x)+\delta, x)$, then we have $$\sqrt{f(x)^2 + f(x)\delta + \frac{\delta^2}2} \ge \frac{f(f(x)+\delta)+x}2 \ge \sqrt{f(x)^2+\delta f(x)}.$$
  • For $\delta >0$ we can loosen this a little to $f(x) + \delta > \frac{f(f(x)+\delta)+x}2 > f(x)$ and putting $\frac{f(f(x)) + x}2 = f(x)$ from before we obtain $$f(f(x)) + 2\delta > f(f(x)+\delta) > f(f(x)).$$
  • Replacing $\delta$ with $-\delta$ above we instead get something like $f(x)-\delta \le \frac{f(x)-\delta + x}2 \le f(x)$ for $\delta>0$ sufficiently small. So we have $f$ continuous at $f(x)$ for each $x$.
  • That's...not exactly useful. Oops.
  • I guess we also know that for each $y>f(x)$ we have $f(y) > f(f(x))$.
  • Suppose $f(x) = x+c$ for some fixed $x,c>0$. Then our arguments above give us $x+2c \le f(x+c+\delta) + x+2c+2\delta$ for each $\delta>0$, which sort of gives a restriction on the values?
  • Maybe suppose $f(x+c+\delta) = x+2c+d$, so $0<d<2\delta$ or something. Surely we will be done from this somehow.
  • Probably we want to show that everything increases by the same amount otherwise that breaks somehow.
  • Is that even correct? Let's put in $f(x)=x+c$. Oh, then the middle term is now the AM of $x,f(y)$ so this exactly holds by QM-AM-GM. That's pretty cool.
  • Ok, now suppose $f(x)=x+c$ for some fixed $x$. What does the graph look like? Something like: (I am redrawing this because it's easier than scanning)

  • Is there a more exact way to draw these fixed points? After some effort I come up with: 

  • Suppose there are two such lines:

  • This has to fail somehow.

  • Probably we want to find blue $a$ and red $b$ such that $a<b$ (but $b$ is close to $a$) and $f(b)<f(a)$, which would then contradict the $y>f(x)\Rightarrow f(y)>f(f(x))$ from earlier.

  • Let our two lines be $y=x+c$ and $y=x+d$ with $c>d$. For each $a+nc$ there's a "death zone" that the $b+md$ cannot land in:

  • If $\frac{c}d$ is irrational then the multiples of $d$ are dense mod $c$ so something is going to land in the death zone.

  • Oh wait, we also have the funny case where $d=0$ and we don't get an infinite sequence of fixed points. I guess we'll fix that later.

  • If $\frac{c}d$ is rational and $d\ne 0$ then the red peaks have "wavelength" $d$ while the death zones are of length $c-d$ and occur every $c$. Is that enough to get a contradiction? If $d$ is close to $c$ we could keep skipping over the death zones...I think instead we have to let $\frac{d}c = \frac{p}q$ where $p,q$ coprime, then the red peaks occupy positions that are $\frac{c}q$ apart mod $c$, while $c-d = c\left(1-\frac{p}q\right) \ge \frac{c}q$ which gives a contradiction (the death zone is a closed interval, so it works out).

  •  Right, so we're left with the case where we have a fixed constant $c$ and $f(x)=x+c$ or $f(x)=x$ for each $x$. Ew. 

  • Ok, but our arguments from before show that if $f(a)=a+c$ then $f(x)=x+c$ for all $a\le x\le a+c$ (or it'd be in the death zone) so by induction $f(x) = x+c$ for all $x\ge a$. So $f$ must be of the form: $x$ up to some value, then $x+c$ from that value.

  • Surely now we can just mutter something about continuity? I think so. I guess more concretely if $f(a)=a$ for some $a$ then $f(a+\delta) \le a + 2\delta$ for each $\delta>0$ so choosing $\delta < \frac{c}2$ we get $f(x)=x$ for all $a\le x < \frac{c}2$ or something. Then induction gives us $f(x) = x$ for all $x\ge a$.

  • Ok, now we must have $f(x)=x+c$ for a fixed $c$ (possibly $0$) otherwise one of the previous two bullet points fails.

  • That was a bit more complicated that I thought it would be but it does work, I think.

I feel like the statement of the FE is simple and weird enough that there aren't really many useful things to substitute in. Once you manage to draw that blue/red picture above it's then a matter of believing you can get a conclusion from there.

Problem 6

(IMO 2026/6) Let $a_1, a_2, a_3, \ldots$ be an infinite sequence of positive integers greater than $1$. Suppose that for all positive integers $n$, the number $a_{n+1}$ is the smallest positive integer greater than $a_n$ such that $\text{gcd}(a_{n+1}, a_i)>1$ for every $i=1,2,\ldots, n$. Prove that there exist positive integers $T$ and $L$ such that $$a_{n+T}=a_n+L$$ for every positive integer $n$.

(Note that $\text{gcd}(x,y)$ denotes the greatest common divisor of positive integers $x$ and $y$.)

  •  I read this a couple of times to make sure that the only thing we were free to choose was $a_1$ (as opposed to IMO 2024/3, which let you choose the first $N$ numbers).
  • Ok, let's try $a_1=1$. Oh wait, that's not legal.
  • Let's try $a_1=2$. Then we get $2,4,6,8,\ldots$ oh it's just the even numbers.
  • In general if we start with a prime number $p$ then we end up with the multiples of $p$.
  • So to get something interesting we need to start with a composite number. Let's try $4$. We have $4,6,8,\ldots$ ok we are getting even numbers again. Right, so if we land on a power of a prime $p$, then everything after that has to be a multiple of $p$ and conversely every multiple of $p$ always works. So we also have to avoid prime powers.
  • I continue bashing through small cases but it seems I keep landing on a prime power which then forces everything else.
  • Eventually I find the $a_1=15$ case. This goes $15,18,20,24,30,36,40,\ldots$. Looking at the first 3 terms, their prime factors are $3$ and $5$, $2$ and $3$, and $2$ and $5$ respectively. This means that everything has to be a multiple of at least $2$ of $2,3,5$. Conversely, we can induct to show that everything of that form works. So whether something is an $a_i$ only depends on its remainder mod $30$, which gives us the desired result.
  • An observation: we should just be looking at the sets of prime divisors of each of the terms. If one of the sets has one element (the prime power case), then everything else must be divided by that prime. The other case that we have is that we have all three $2$-element subsets of $\{2,3,5\}$, and so we get everything which is divisible by at least two of them.
  • One possible way to think about this would be to look at the sets of the prime divisors of each term, but only look at the "minimal" ones: if one set is contained in another, we ignore the bigger one. This is fine since sharing a prime factor with the smaller one implies sharing a prime factor with the bigger one.
  • So far, we have found two "stable" configurations: a single set $\{p\}$, and the sets $\{p,q\},\{q,r\},\{p,r\}$. In both cases, any set of primes that intersects all sets has to contain one of the sets listed, so then we can induct to show that the set of (sufficiently large) $a_i$ is exactly the set of (sufficiently large) numbers whose prime factors contain at least one of the given sets.
  • What other stable configurations are there? I guess something of the form "all $r$-element subsets of some set of $m$ primes" should work for the correct $r,m$. Maybe we can show that we always end up in this situation?
  • Now I'm imagining drawing a lot of Venn diagrams in my head. At each stage, we add a new circle. If the new circle contains some other circle, we delete it. If a new circle is contained in some other circles, we delete the other circles.
  • It seems like a useful thing to consider would be the smallest set which contains at least one element of all the sets we currently have. (Call a set which intersects each of the sets of prime factors so far a legal set.) If all our sets intersect, there exists a legal set of size $1$. If we have three sets which intersect pairwise but have empty common intersection, then the smallest legal set has size $>1$. From picturing Venn diagrams, it seems that the size of this smallest legal set is nondecreasing. Can we prove this?
  • Oh, this is sort of obvious: as we go along, we are adding strictly more conditions, so any set which currently works would have worked before. In other words, if a set intersects the first $n$ sets, then it would also intersect the first $n-1$ sets.
  • Ok, we've found a monovariant. That means we're probably on the right track. Presumably now we show that this can't increase to infinity?
  • This feels like some Hall's marriage lemma/max-flow-min-cut situation but I can't quite put my finger on it. Also it turns out that my brain doesn't have enough RAM to imagine large bipartite graphs.
  • Suppose that for each set of size $k$, one of our $n$ sets doesn't intersect with it. Then max-flow-min-cut tells us that we have $k+1$ of the sets such that something? Not sure.
  • After getting stuck in this direction for a while, I eventually realise that I am being very silly: the initial set corresponding to $a_1$ intersects with all the others, so is always a legal set. This means that the size of the smallest set which can intersect all the current sets is also bounded above, and so eventually constant, say at $r$.
  • This seems like good progress. Presumably now we want to show that we eventually have all the size $r$ subsets of something?
  • In the first place, how do we even know that we can't have infinitely many possible legal sets of size $r$. I can only picture Venn diagram with like, five circles tops, so this doesn't seem quite so impossible to me.
  • When $r=1$, all the one-element legal sets must be subsets of the initial set corresponding to $a_1$, so there are finitely many of those. Maybe in general we can find $r$ sets such that their union contains all legal size $r$ legal sets?

  • Does max-flow-min-cut say that we must have $r$ disjoint sets or something? Ok, that's obviously false. I'm shelving this idea until I get desperate.
  • Ok, as before, sets that were illegal cannot become legal. So our pool of legal sets is always shrinking. The first time the size of the smallest legal set hits $r$, there are only finitely many possible legal sets of size $r$: they must all only contain elements in the union of the sets we currently have, otherwise we could remove the extra elements to get a smaller legal set. As we go along, the number of legal sets of size $r$ does not increase, so always remains finite.
  • So eventually, we have some finite set of legal sets of size $r$, and no smaller sets are legal.
  • In the examples above, in fact these legal sets actually appear as a set of prime factors of some $a_i$. I think this should probably be the case? Right, if some set is legal forever, then pick some large number whose set of prime powers is exactly that set. Then it will eventually appear in the sequence. So eventually, all of these forever-legal sets of size $r$ will appear as sets of prime factors of some $a_i$.
  • Maybe now we want to show that all forever-legal sets contain one of the above sets? Or that the minimal forever-legal sets are of the form described above ("all $r$-element subsets of some big set")?

  • I get stuck on this for a while before realising that we probably don't need such a strong classification to get the answer. All we want is some large $N$ such that eventually, whether an integer is part of our sequence depends only on its remainder mod $N$. So there's nothing stopping us from having a larger forever-legal set, but that's probably okay.
  • Let $S$ be the union of our forever-legal sets of size $r$. Suppose some other subset of $S$ is forever legal. Then by the same argument as before this subset must appear as the set of prime factors of some $a_i$.
  • For any $a_i$, its set of prime factors must thus intersect each forever-legal subset of $S$. We now want this intersection to be forever-legal, I guess? Actually, maybe this isn't true...
  • From the arguments above, every forever-legal set appears as the set of prime factors of some $a_i$. Conversely, every set of prime factors of some $a_i$ is forever-legal. So these two are the same thing.
  • Really all we need is for the union of all the minimal forever-legal sets to be finite, then everything is determined by the primes in their union.
  • Given a forever-legal set, first note that it contains a minimal forever-legal set. Indeed, consider its largest subset that is forever-legal. (It has finitely many subsets.)
  • Now how do we show that the union is finite. Suppose it isn't, I guess. Maybe let's consider the case where $r=2$, so there's a forever-legal set of the form $\{p,q\}$. Then WLOG there's infinitely many minimal forever-legal sets containing $p$ but not $q$. Intuitively it feels like now $p$ should be forever-legal? Suppose not, then there's some minimal forever-legal set (here we're using the fact that forever-legal is the same thing as being the set of prime factors of some $a_i$) that contains $q$ but not $p$, which means it also has to intersect all the forever-legal sets that contain $p$ but not $q$. 

  • After some effort, I come up with the following example:

  • This is arranged such that every two sets intersect, and each set doesn't contain a strict subset that intersects everything else. That means that it isn't enough to work purely combinatorially in the world of minimal forever-legal sets; we have to look back at the question to get more restrictions.
  • This also tells us that really we should be forgetting about the idea of looking at the smallest forever-legal sets, since they don't give us enough information.
  • Our example seems to be adding new primes by making two new sets go through each new prime before a set has the chance to shrink to a smaller forever-legal set. But surely that should fail by some sort of size argument.

  • How can we make this rigorous? A legal set becomes a minimal legal set at the point when all of its strict subsets become illegal. When do sets become illegal? That only happens when conditions strictly tighten, which is when the set of prime factors of our new $a_i$ is minimal (doesn't contain the set of prime factors of any of the previous $a_i$). So we just need to show that any such set can't contain large primes.
  • Effectively, we are replacing the $S$ from earlier with some set of primes that aren't too large.

  • Suppose we have a new set which contains some large prime. Then we probably want to show that this set couldn't have been minimal, i.e. there's some previous $a_i$ whose set of prime divisors is everything except for that large prime.
  • Probably we want to choose some definition of "large" for which that works. If this set was legal, then the set minus the large prime was legal before this: by induction or something, all the current minimal sets don't contain this large prime. This means that if something had its set of divisors being this set minus the large prime, then it was legal at points before this.
  • So we just need to show that there was some number of this form that's $\ge a_1$ and $<a_i$. Presumably here's where the choice of "large" comes in.

  • Okay, suppose our large prime is $p$. Then if $\frac{a_i}p \ge a_1$, then we're done. Ugh not exactly - replace $p$ by $p^{v_p(a_i)}$ or something. The point is that if the contribution from all the other primes is sufficiently large then we're done.
  • Now suppose not, then all the other primes multiply to $<a_1$. But if "large" is sufficiently large, then these are much smaller than $a_i$. I think as long as $\frac{a_i}{a_1}$ is larger than the smallest of these primes then by repeatedly multiplying by the smallest prime we eventually get something that's $\ge a_1$ and $<a_i$.
  • Right, so we should just define "large" to mean something like $>a_1^2$, then if $p$ is large, any $a_i$ with $p|a_i$ satisfies $\frac{a_i}{a_1} \ge p > a_1$ which makes this case work.
  • I think we're done?

This felt a lot like P3 in the sense that it's a mostly combinatorial problem with some noncombinatorial input to finish. I found this a little easier than P3 because the noncombinatorial input was a bit easier to come up with, but it could also be argued that the combinatorial bit was harder because there are more approaches that you have to rule out.

Comments

Post a Comment

Popular posts from this blog

IOI 2025/1 was surprisingly mathy

-
Image
(Glen here.) Recently, there was some discussion about this year's IOI in a group chat, and Ker Yang remarked that the first task, " Souvenirs ", was basically a math question. Of course, I had to have a look. The original description is pretty long, so here's a rewriting in a more math olympiad style: Sheldon is buying french fries from a fast food restaurant, which sells fries in $N$ different sizes (with packagings labelled from largest to smallest from $0$ to $N-1$), with integer costs $P_0 > P_1 > \ldots > P_{N-1} > 0$. To buy fries, Sheldon can pay $\$M$ where $M$ is a positive integer, and then define a sequence $i_1,i_2,\ldots$ as follows: $i_1$ is the smallest integer such that $P_{i_1}\le M$, and in general, $i_k$ is the smallest integer $>i_{k-1}$ such that $P_{i_k} \le M - P_{i_1} - \cdots P_{i_{k-1}}$. If no such $i_k$ can be defined, the sequence terminates. Then, Sheldon receives the fries with labels $i_1,i_2,\ldots$ along with his chang...
Read more

IMO 2025 Livesolve (Day 1)

-
Image
(Drew here.) As a retired contestant, I decided it would be fun to attempt the IMO 2025 paper and see how well I would do on it! Let's get started. Problem 1 (IMO 2025/1) A line in the plane is called sunny if it is not parallel to any of the $x$–axis, the $y$–axis, or the line $x+y=0$.  Let $n\ge3$ be a given integer. Determine all nonnegative integers $k$ such that there exist $n$ distinct lines in the plane satisfying both of the following: for all positive integers $a$ and $b$ with $a+b\le n+1$, the point $(a,b)$ lies on at least one of the lines; and exactly $k$ of the $n$ lines are sunny. To begin, I decided to try the $n=3$ case, as that's the smallest one. The points form a right triangle with $3$ points on each edge, and a sunny line is a line not parallel to any of the edges of the main triangle. We can shift the points a bit to instead form an equilateral triangle, and a sunny line is any line not parallel to any of the sides of the equilateral triangle. Important...
Read more