EGMO 2020 Problem 1: solution, and the power of 2 that cannot hide
19 November 2026
EGMO 2020 Problem 1 looks like a recurrence problem, and trying to solve the recurrence is the trap. You never need a formula for the terms. You only need to follow one number per term: how many times divides it. That number obeys two simple rules, and once you have them the proof is a count. Here is the statement, a full solution, an independent check, and what in the wording points the way.
The signal in the statement
Every coefficient in the recurrence is a power of : the , the hidden , the . And the conclusion is about divisibility by a power of . When both ends of a problem talk only about , the quantity to track is the exponent of in each term. Write for it, so and .
The other signal is the pair of numbers. There are terms and the target exponent is , a ratio of to . That ratio is a hint that the exponent can rise by about per step for a third of the way, or must fall by per step for the rest. Both halves turn out to be true.
Solution
Write . Every is a positive integer, so every is a whole number at least .
- The lemma. If three nonzero integers add up to , the smallest of their three exponents occurs at least twice. Indeed, if were strictly smaller than both and , then would divide , which is false.
- Apply it to . The three exponents are , and , and the smallest of them appears twice.
- Falling rule. Suppose . Then the minimum is not alone, and it cannot be alone, so it is and it equals . That is, .
- Once falling, always falling. If the falling rule applies at step , then , so it applies at step as well. From the first step where it applies, the exponent drops by exactly per term all the way to .
- Otherwise climbing. At any step where the falling rule does not apply, .
- Case A: the falling rule never applies. Then for every from to , so , far above .
- Case B: it first applies at some step. Call that step . Before that the exponent climbed, so . After it, the exponent falls by per term from to , which is drops. Since , we get .
- The count. If , then . If , then . Either way some term is divisible by .
The numbers in the problem are tight against this argument: the larger of and is never below , and it equals exactly at and . Step 8 is bounding at its plainest, and the whole proof is modular arithmetic done with exponents instead of remainders.
An independent check
The solution rests on the rules in steps 3 and 5, so this page tests them directly. For every pair of positive integers up to that gives a whole-number , the build confirms that the smallest exponent appears twice, that the falling rule holds, and that a climb of more than forces .
It also runs smaller copies of the problem by brute force, using the recurrence itself rather than the proof. With terms the argument promises a term divisible by . For and every start with up to , that holds, and is exactly the best possible: some sequence has no term divisible by . Here is one for , ten terms:
Its exponents of are . They climb by for three steps, then the falling rule takes over and they drop by to the end, exactly the shape the proof describes. The highest exponent is .
Where marks go missing
- Solving the recurrence. The characteristic roots are irrational, and a closed form tells you nothing about powers of . Time spent here is time not spent on the exponents.
- Using the lemma without proving it. It is one line, but it is the whole engine. Graders expect to see why the minimum must appear twice.
- Dropping positivity. The exponent of is not a number, and the argument that the fall must stop above needs . Say where you use that the terms are positive.
- The boundary case. When exactly, the rules say nothing about . That is fine, because the proof only needs there, but a solution that claims the exponent always climbs by exactly is wrong.
- Off by one in the count. The falling run from to has steps, not . The margin in step 8 is zero, so a count that is off by one either proves something false or fails to close.
Practise the idea
Tracking the exponent of and finding the one term where it is largest is also how you prove olympiad problem o2-nt-7: the harmonic sum is never a whole number, because exactly one denominator holds the top power of . The daily problem posts a new one every day, no account needed.
Related guides
- EGMO 2023 Problem 1: solution, and why the ring has to closeA full solution to EGMO 2023 Problem 1: why the largest and smallest terms force every ratio to equal 2, and why the ring has to close.
- EGMO 2025 Problem 1: solution, and the one pair that breaks the restA full solution to EGMO 2025 Problem 1: why every even N and every power of 3 works, the pair that breaks every other N, and the signal in the statement.
- Lifting the exponent lemma explained for competitionsThe lifting the exponent lemma in one line, the p = 2 version that catches almost everyone, and the signals that tell you a contest problem wants it.
- gcd(2^m − 1, 2^n − 1): the proof, and how to spot itWhy gcd(2^m − 1, 2^n − 1) = 2^gcd(m,n) − 1: run Euclid's algorithm on the exponents. A full proof, a second proof by orders, and where it turns up.
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