IMO 2012 Shortlist N7

Category: Number Theory

Problem

Find all n ∈ N for which there exist nonnegative integers a1,a2,...,an such that 2a1 + 2a2

• ··· + 2an = 3a1

3a2

• ··· + n 3an = 1. Solution. Such numbers a1,a2,...,an exist if and only if n ≡ 1 (mod 4) or n ≡ 2 (mod 4). Let Pn k=1 k 3ak = 1 with a1,a2,...,an nonnegative integers. Then 1·x1+2·x2+···+n·xn = 3a with x1,...,xn powers of 3 and a ≥ 0. The right-hand side is odd, and the left-hand side has the same parity as 1+2+···+n. Hence the latter sum is odd, which implies n ≡ 1,2 (mod 4). Now we prove the converse. Call feasible a sequence b1,b2,...,bn if there are nonnegative integers a1,a2,...,an such that 2a1

2a2

• ··· + 2an = b1 3a1

b2 3a2

• ··· + bn 3an = 1. Let bk be a term of a feasible sequence b1,b2,...,bn with exponents a1,a2,...,an like above, and let u,v be nonnegative integers with sum 3bk. Observe that 2ak+1

2ak+1

2ak and u 3ak+1 + v 3ak+1

bk 3ak . It follows that the sequence b1,...,bk−1,u,v,bk+1,...,bn is feasible. The exponents ai are the same for the unchanged terms bi, i 6= k; the new terms u,v have exponents ak + 1. We state the conclusion in reverse. If two terms u,v of a sequence are replaced by one term u+v and the obtained sequence is feasible, then the original sequence is feasible too. Denote by αn the sequence 1,2,...,n. To show that αn is feasible for n ≡ 1,2 (mod 4), we transform it by n − 1 replacements {u,v} 7→ u+v to the one-term sequence α1. The latter is feasible, with a1 = 0. Note that if m and 2m are terms of a sequence then {m,2m} 7→ m, so 2m can be ignored if necessary. Let n ≥ 16. We prove that αn can be reduced to αn−12 by 12 operations. Write n = 12k+r where k ≥ 1 and 0 ≤ r ≤ 11. If 0 ≤ r ≤ 5 then the last 12 terms of αn can be partitioned into 2 singletons {12k − 6}, {12k} and the following 5 pairs: {12k − 6 − i,12k − 6 + i},i = 1,...,5 − r; {12k − j,12k + j},j = 1,...,r. (There is only one kind of pairs if r ∈ {0,5}.) One can ignore 12k − 6 and 12k since αn contains 6k − 3 and 6k. Furthermore the 5 operations {12k − 6 − i,12k − 6 + i} 7→ 8k − 4 and {12k − j,12k + j} 7→ 8k remove the 10 terms in the pairs and bring in 5 new terms equal to 8k − 4 or 8k. All of these can be ignored too as 4k − 2 and 4k are still present in the sequence. Indeed 4k ≤ n − 12 is equivalent to 8k ≥ 12 − r, which is true for r ∈ {4,5}. And if r ∈ {0,1,2,3} then n ≥ 16 implies k ≥ 2, so 8k ≥ 12−r also holds. Thus αn reduces to αn−12. The case 6 ≤ r ≤ 11 is analogous. Consider the singletons {12k}, {12k+6} and the 5 pairs {12k − i,12k + i},i = 1,...,11 − r; {12k + 6 − j,12k + 6 + j},j = 1,...,r − 6. Ignore the singletons like before, then remove the pairs via operations {12k − i,12k + i} 7→ 8k and {12k + 6 − j,12k + 6 + j} 7→ 8k + 4. The 5 newly-appeared terms 8k and 8k + 4 can be ignored too since 4k +2 ≤ n− 12 (this follows from k ≥ 1 and r ≥ 6). We obtain αn−12 again. The problem reduces to 2 ≤ n ≤ 15. In fact n ∈ {2,5,6,9,10,13,14} by n ≡ 1,2 (mod 4). The cases n = 2,6,10,14 reduce to n = 1,5,9,13 respectively because the last even term of αn can be ignored. For n = 5 apply {4,5} 7→ 3, then {3,3} 7→ 2, then ignore the 2 occurrences of 2. For n = 9 ignore 6 first, then apply {5,7} 7→ 4, {4,8} 7→ 4, {3,9} 7→ 4. Now ignore the 3 occurrences of 4, then ignore 2. Finally n = 13 reduces to n = 10 by {11,13} 7→ 8 and ignoring 8 and 12. The proof is complete.50