Lemma › Guides › EGMO 2021 Problem 1: solution, and why you only need to halve
Guide

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 202120212021^{2021} 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 mm to 2m2m, 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 problem. The number 20212021 is fantabulous. For any positive integer mm, if any element of the set {m,2m+1,3m}\{m, 2m+1, 3m\} is fantabulous, then all the elements are fantabulous. Does it follow that the number 202120212021^{2021} is fantabulous?

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 2m+12m+1 is fantabulous, so is mm. So the rule lets you go down as well as up, and the question becomes: is 202120212021^{2021} connected to 20212021 by a path of links?

Now look at 2m+12m+1 in binary. It is mm with a 11 written on the end. Going down from an odd number to mm deletes its last binary digit. If you could also delete a final 00, that is link mm to 2m2m, then every number above 11 would link to the number you get by halving and rounding down, and every number would sit on a path down to 11. That is the whole plan. The link m↔3mm \leftrightarrow 3m is the tool you use to build m↔2mm \leftrightarrow 2m, 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.

  1. For every positive integer mm, the rule links mm with 2m+12m+1 and with 3m3m.
  2. Take any positive integer mm and follow this chain. The set for mm links mm with 3m3m. The set for 3m3m links 3m3m with 6m+16m+1. The set for 6m+16m+1 links 6m+16m+1 with 12m+312m+3.
  3. Now 12m+3=3(4m+1)12m+3 = 3(4m+1), so the set for 4m+14m+1 links 12m+312m+3 with 4m+14m+1.
  4. Finally 4m+1=2(2m)+14m+1 = 2(2m)+1, so the set for 2m2m links 4m+14m+1 with 2m2m. Every number used is a positive integer, so every set used is one the rule covers. Chaining steps 2 to 4, mm is linked with 2m2m.
  5. Together with step 1, every positive integer mm is linked with both 2m2m and 2m+12m+1. Equivalently, every integer n≥2n \ge 2 is linked with ⌊n/2⌋\lfloor n/2 \rfloor, which is again a positive integer.
  6. Starting from any n≥2n \ge 2 and halving with rounding down, the numbers strictly decrease and stay positive, so after finitely many steps you reach 11. So every positive integer is linked with 11. This is induction on nn written as a descent.
  7. In particular 20212021 and 202120212021^{2021} are both linked with 11, so they are linked with each other. Since 20212021 is fantabulous, so is 202120212021^{2021}.

You never need the size of 202120212021^{2021}. The descent from it takes 2219222192 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 20212021 marked, then sweeps every mm whose set stays below 200000200000, marking the whole set whenever one member is marked, until nothing changes. Every number from 11 to 50005000 ends up marked, so the rule really does reach small numbers from 20212021, not only large ones. It also checks the four links of the chain for every mm up to 100000100000 by testing set membership directly, and walks 202120212021^{2021} down to 11 in exact integer arithmetic. The simulation never uses the chain, so it would catch a slip in the algebra.

One more run shows why 3m3m is in the problem at all. With only the m↔2m+1m \leftrightarrow 2m+1 links, the same sweep starting from 20212021 never reaches 11 or 22: 20212021 goes down to 10101010, which is even, and the walk stops.

Where marks go missing

Practise the idea

The solution works from the target down: instead of building 202120212021^{2021} from 20212021, it shrinks both to 11. 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

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