IMO 2003 SL N1

Origin: POL | Category: Number Theory

Problem

Let m be a fixed integer greater than 1. The sequence x0, x1, x2, . . . is defined as follows: xi = . 2i, if 0 \leqi \leqm −1; m j=1 xi−j, if i \geqm. Find the greatest k for which the sequence contains k consecutive terms divisible by m.

Solution

Let ri be the remainder when xi is divided by m. Since there are at most mm types of m-consecutive blocks in the sequence (ri), some type will

repeat at least twice. Then since the entire sequence is determined by one m-consecutive block, the entire sequence will be periodic. The formula works both forward and backward; hence using the rule xi = xi+m −m−1 j=1 xi+j we can define x−1, x−2, . . . . Thus we obtain that (r−m, . . . , r−1) = (0, 0, . . . , 0, 1). Hence there are m −1 consecutive terms in the sequence (xi) that are divisible by m. If there were m consecutive terms in the sequence (xi) divisible by m, then by the recurrence relation all the terms of (xi) would be divisible by m, which is impossible.