MathDB
USAMO 2003 Problem 3

Source:

September 27, 2005
AMCUSA(J)MOUSAMOLaTeXinductionstrong inductionalgebra proposed

Problem Statement

Let n≠0n \neq 0. For every sequence of integers A=a0,a1,a2,…,an A = a_0,a_1,a_2,\dots, a_n satisfying 0≤ai≤i0 \le a_i \le i, for i=0,…,ni=0,\dots,n, define another sequence t(A)=t(a0),t(a1),t(a2),…,t(an) t(A)= t(a_0), t(a_1), t(a_2), \dots, t(a_n) by setting t(ai)t(a_i) to be the number of terms in the sequence AA that precede the term aia_i and are different from aia_i. Show that, starting from any sequence AA as above, fewer than nn applications of the transformation tt lead to a sequence BB such that t(B)=Bt(B) = B.
Back to ProblemsView on AoPS