IMO 2001 SL N3

Origin: GBR | Category: Number Theory

Problem

Let a1 = 1111, a2 = 1212, a3 = 1313, and an = |an−1 −an−2| + |an−2 −an−3|, n \geq4. Determine a1414.

Solution

Define bn = |an+1−an| for n \geq1. From the equalities an+1 = bn−1+bn−2, from an = bn−2 + bn−3 we obtain bn = |bn−1 −bn−3|. From this relation we deduce that bm \leqmax(bn, bn+1, bn+2) for all m \geqn, and consequently bn is bounded. Lemma. If max(bn, bn+1, bn+2) = M \geq2, then max(bn+6, bn+7, bn+8) \leq M −1. Proof. Assume the opposite. Suppose that bj = M, j \in{n, n + 1, n + 2}, and let bj+1 = x and bj+2 = y. Thus bj+3 = M −y. If x, y, M −y are all less than M, then the contradiction is immediate. The remaining cases are these: (i) x = M. Then the sequence has the form M, M, y, M −y, y, . . . , and since max(y, M −y, y) = M, we must have y = 0 or y = M. (ii) y = M. Then the sequence has the form M, x, M, 0, x, M −x, . . . , and since max(0, x, M −x) = M, we must have x = 0 or x = M. (iii) y = 0. Then the sequence is M, x, 0, M, M −x, M −x, x, . . . , and since max(M −x, x, x) = M, we have x = 0 or x = M. In every case M divides both x and y. From the recurrence formula M also divides bi for every i < j. However, b2 = 1212 −1111 and b4 = 1111 are relatively prime, a contradiction. From max(b1, b2, b3) \leq1313 and the lemma we deduce inductively that bn \leq1 for all n \geq6\cdot1313−5. Hence an = bn−2+bn−3 takes only the values 0, 1, 2 for n \geq6 \cdot 1313 −2. In particular, a1414 is 0, 1, or 2. On the other hand, the sequence an modulo 2 is as follows: 1, 0, 1, 0, 0, 1, 1; 1, 0, 1, 0, . . .; and therefore it is periodic with period 7. Finally, 1414 \equiv0 modulo 7, from which we obtain a1414 \equiva7 \equiv1 (mod 2). Therefore a1414 = 1.