IMO 2019 Shortlisted Problems

Question

The infinite sequence a_0, a_1, a_2, of (not necessarily different) integers has the following properties: 0 a_i i for all integers i 0, and ka_0+ka_1++ka_k=2^k for all integers k 0. Prove that all integers N 0 occur in the sequence (that is, for all N 0, there exists i 0 with a_i=N ).

Accepted Answer

We prove by induction on k that every initial segment of the sequence, a_0, a_1, , a_k, consists of the following elements (counted with multiplicity, and not necessarily in order), for some 0 with 2 k+1 : 0,1, , -1, 0,1, , k- . For k=0 we have a_0=0, which is of this form. Now suppose that for k=m the elements a_0, a_1, , a_m are 0,0,1,1,2,2, , -1, -1, , +1, , m--1, m- for some with 0 2 m+1. It is given that m+1a_0+m+1a_1++m+1a_m+m+1a_m+1=2^m+1, which becomes aligned (m+10+m+11. & .++m+1-1) & +(m+10+m+11++m+1m-)+m+1a_m+1=2^m+1 aligned or, using m+1i=m+1m+1-i, that aligned (m+10+m+11. & .++m+1-1) & +(m+1m+1+m+1m++m+1+1)+m+1a_m+1=2^m+1 aligned On the other hand, it is well known that m+10+m+11++m+1m+1=2^m+1, and so, by subtracting, we get m+1a_m+1=m+1 . From this, using the fact that the b…