Lemma › Guides › EGMO 2020 Problem 1: solution, and the power of 2 that cannot hide
Guide

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 22 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 problem. The positive integers a0,a1,a2,…,a3030a_0, a_1, a_2, \ldots, a_{3030} satisfy 2an+2=an+1+4an2a_{n+2} = a_{n+1} + 4a_n for n=0,1,2,…,3028n = 0, 1, 2, \ldots, 3028. Prove that at least one of the numbers a0,a1,a2,…,a3030a_0, a_1, a_2, \ldots, a_{3030} is divisible by 220202^{2020}.

The signal in the statement

Every coefficient in the recurrence is a power of 22: the 22, the hidden 11, the 44. And the conclusion is about divisibility by a power of 22. When both ends of a problem talk only about 22, the quantity to track is the exponent of 22 in each term. Write v(x)v(x) for it, so v(12)=2v(12) = 2 and v(7)=0v(7) = 0.

The other signal is the pair of numbers. There are 30313031 terms and the target exponent is 20202020, a ratio of 33 to 22. That ratio is a hint that the exponent can rise by about 22 per step for a third of the way, or must fall by 11 per step for the rest. Both halves turn out to be true.

Solution

Write un=v(an)u_n = v(a_n). Every ana_n is a positive integer, so every unu_n is a whole number at least 00.

  1. The lemma. If three nonzero integers add up to 00, the smallest of their three exponents occurs at least twice. Indeed, if v(p)v(p) were strictly smaller than both v(q)v(q) and v(r)v(r), then 2v(p)+12^{v(p)+1} would divide q+r=−pq + r = -p, which is false.
  2. Apply it to 2an+2−an+1−4an=02a_{n+2} - a_{n+1} - 4a_n = 0. The three exponents are un+2+1u_{n+2} + 1, un+1u_{n+1} and un+2u_n + 2, and the smallest of them appears twice.
  3. Falling rule. Suppose un+1<un+2u_{n+1} < u_n + 2. Then the minimum is not un+2u_n + 2 alone, and it cannot be un+2+1u_{n+2} + 1 alone, so it is un+1u_{n+1} and it equals un+2+1u_{n+2} + 1. That is, un+2=un+1−1u_{n+2} = u_{n+1} - 1.
  4. Once falling, always falling. If the falling rule applies at step nn, then un+2=un+1−1<un+1+2u_{n+2} = u_{n+1} - 1 < u_{n+1} + 2, so it applies at step n+1n+1 as well. From the first step where it applies, the exponent drops by exactly 11 per term all the way to a3030a_{3030}.
  5. Otherwise climbing. At any step where the falling rule does not apply, un+1≥un+2u_{n+1} \ge u_n + 2.
  6. Case A: the falling rule never applies. Then un+1≥un+2u_{n+1} \ge u_n + 2 for every nn from 00 to 30283028, so u3029≥2⋅3029u_{3029} \ge 2 \cdot 3029, far above 20202020.
  7. Case B: it first applies at some step. Call that step nn. Before that the exponent climbed, so un≥2nu_n \ge 2n. After it, the exponent falls by 11 per term from an+1a_{n+1} to a3030a_{3030}, which is 3029−n3029 - n drops. Since u3030≥0u_{3030} \ge 0, we get un+1≥3029−nu_{n+1} \ge 3029 - n.
  8. The count. If n≥1010n \ge 1010, then un≥2n≥2020u_n \ge 2n \ge 2020. If n≤1009n \le 1009, then un+1≥3029−n≥2020u_{n+1} \ge 3029 - n \ge 2020. Either way some term is divisible by 220202^{2020}.

The numbers in the problem are tight against this argument: the larger of 2n2n and 3029−n3029 - n is never below 20202020, and it equals 20202020 exactly at n=1009n = 1009 and n=1010n = 1010. 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 an,an+1a_n, a_{n+1} up to 30003000 that gives a whole-number an+2a_{n+2}, the build confirms that the smallest exponent appears twice, that the falling rule holds, and that a climb of more than 22 forces un+2=un+1u_{n+2} = u_n + 1.

It also runs smaller copies of the problem by brute force, using the recurrence itself rather than the proof. With 3k+13k + 1 terms the argument promises a term divisible by 22k2^{2k}. For k=1,2,3k = 1, 2, 3 and every start with a0,a1a_0, a_1 up to 15001500, that holds, and 2k2k is exactly the best possible: some sequence has no term divisible by 22k+12^{2k+1}. Here is one for k=3k = 3, ten terms:

1,28,16,64,64,160,208,424,628,11621, 28, 16, 64, 64, 160, 208, 424, 628, 1162

Its exponents of 22 are 0,2,4,6,6,5,4,3,2,10, 2, 4, 6, 6, 5, 4, 3, 2, 1. They climb by 22 for three steps, then the falling rule takes over and they drop by 11 to the end, exactly the shape the proof describes. The highest exponent is 6=2k6 = 2k.

Where marks go missing

Practise the idea

Tracking the exponent of 22 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 22. 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