EGMO 2021 Problem 1: solution, and why you only need to halve
18 November 2026
EGMO 2021 Problem 1 hands you a made-up word and a huge number, and the huge number is a distraction. Nothing about matters except that it is a positive integer. The real question is which numbers the rule ties together, and the answer is all of them. The work is finding one short chain of moves, from to , that the rule does not give you directly. Here is the statement, a full solution, an independent check, and what in the wording points the way.
The signal in the statement
Read "if any element is fantabulous, then all the elements are" as a link that works in both directions. If is fantabulous, so is . So the rule lets you go down as well as up, and the question becomes: is connected to by a path of links?
Now look at in binary. It is with a written on the end. Going down from an odd number to deletes its last binary digit. If you could also delete a final , that is link to , then every number above would link to the number you get by halving and rounding down, and every number would sit on a path down to . That is the whole plan. The link is the tool you use to build , because the rule never gives it to you directly.
Solution
The answer is yes. Say that two positive integers are linked when the rule forces one to be fantabulous as soon as the other is. Linked is symmetric, and links chain together.
- For every positive integer , the rule links with and with .
- Take any positive integer and follow this chain. The set for links with . The set for links with . The set for links with .
- Now , so the set for links with .
- Finally , so the set for links with . Every number used is a positive integer, so every set used is one the rule covers. Chaining steps 2 to 4, is linked with .
- Together with step 1, every positive integer is linked with both and . Equivalently, every integer is linked with , which is again a positive integer.
- Starting from any and halving with rounding down, the numbers strictly decrease and stay positive, so after finitely many steps you reach . So every positive integer is linked with . This is induction on written as a descent.
- In particular and are both linked with , so they are linked with each other. Since is fantabulous, so is .
You never need the size of . The descent from it takes halvings, one fewer than its number of binary digits, and the proof does not care.
An independent check
Instead of trusting the chain, this page runs the rule itself. It starts with only marked, then sweeps every whose set stays below , marking the whole set whenever one member is marked, until nothing changes. Every number from to ends up marked, so the rule really does reach small numbers from , not only large ones. It also checks the four links of the chain for every up to by testing set membership directly, and walks down to in exact integer arithmetic. The simulation never uses the chain, so it would catch a slip in the algebra.
One more run shows why is in the problem at all. With only the links, the same sweep starting from never reaches or : goes down to , which is even, and the walk stops.
Where marks go missing
- Only moving up. The rule says "if any element", not "if ". A solution that only builds bigger numbers out of has thrown away half the rule, and it is the half that gets you down to .
- Leaving the positive integers. The rule is stated for positive only. The chain in steps 2 to 4 is fine because every number in it is positive, but a step that needs , or a halving below , is not allowed. Say why every set you use is a legal one.
- Stopping at "it is plausible". Showing that a handful of small numbers connect is evidence, not proof. The marks are for the general chain from to and the descent that follows from it.
Practise the idea
The solution works from the target down: instead of building from , it shrinks both to . That is working backwards, and the descent in step 6 is induction with a strictly decreasing positive integer. The same shrinking move, run as a contradiction, proves olympiad problem o4-2: a smallest solution would produce a smaller one. The daily problem posts a new one every day, no account needed.
Related guides
- What separates a Level 5 problem from a Level 7, side by sideTwo IMO inequalities, both rated 5 out of 6, sit two rungs apart on the ladder. What actually separates a Level 5 problem from a Level 7, and how to cross.
- How to write up a proof so it gets full marksYour proof is right and the score is not. What a marker can and cannot credit, the four places marks leak out of a correct argument, and a read-back that finds them.
- What to do when you have no idea how to startThe blank page is a procedure failure, not a knowledge failure. Five opening moves ordered by cost, and the rule that says when to abandon one for the next.
- How to read a hard problem without giving upMost hard problems are abandoned before they are ever attempted. Five things to do to a statement with a pen, and the rule that decides when to stop.
Train it on Lemma
Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.
Find your level