IMO 1993 SL 16

Origin: MCD

Problem

Let n \inN, n \geq2, and A0 = (a01, a02, . . . , a0n) be any n-tuple of natural numbers such that 0 \leqa0i \leqi−1, for i = 1, . . . , n. The n-tuples A1 = (a11, a12, . . . , a1n), A2 = (a21, a22, . . . , a2n), . . . are defined by ai+1,j = Card{ai,l | 1 \leql \leqj−1, ai,l \geqai,j}, for i \inN and j = 1, . . . , n. Prove that there exists k \inN, such that Ak+2 = Ak.

Solution

Let Sn = {A = (a1, . . . , an) | 0 \leqai < i}. For A = (a1, . . . , an), let A′ = (a1, . . . , an−1), so that we can write A = (A′, an). The proof of the statement from the problem will be given by induction on n. For n = 2 there are two possibilities for A0, so one directly checks that A2 = A0. Now assume that n \geq3 and that A0 = (A′ 0, a0n) \inSn. It is clear that then any Ai is in Sn too. By the induction hypothesis there exists k \inN such that A′ k = A′ k+2 = A′ k+4 = \cdot \cdot \cdot and A′ k+1 = A′ k+3 = \cdot \cdot \cdot . Observe that if we increase (decrease) akn, ak+1,n will decrease (respectively in- crease), and this will also increase (respectively decrease) ak+2,n. Hence akn, ak+2,n, ak+4,n, . . . is monotonically increasing or decreasing, and since it is bounded (by 0 and n −1), it follows that we will eventually have ak+2i,n = ak+2i+2,n = \cdot \cdot \cdot . Consequently Ak+2i = Ak+2i+2.