# Problem A. 541. (September 2011)

**A. 541.** The elements of the set *H* are finite sequences whose elements are from {1,2,3}. Suppose that no element of *H* is a subsequence of any other element of *H*. Show that *H* is finite.

Proposed by: *András Pongrácz,* Budapest

(5 pont)

**Deadline expired on October 10, 2011.**

**Solution.** We will call the finite sequences as words, their elements will be letters. The empty word is allowed. denotes that the word *u* is a subsequence of *v*. The relation is reflexive and transitive, i.e. for all *u* and and implies . *u*+*v* denotes the concatenation of *u* and *v* and |*u*| denotes the length of *u*.

We prove the following theorem:

Theorem.Suppose that w_{1},w_{2},...is an infinite sequence of words that contain only a finite number of different letters. Then there exists an infinite sequenceof indices such that.

The Theorem implies the statement of the problem immediately.

Let *k* be the number of different letters that appear in the words *w*_{1},*w*_{2},.... We prove the Theorem by induction on *k*. If *k*=0 then *w*_{1},*w*_{2},... are all empty ant the statement is trivial. So suppose *k*1 and that the statement is true for fewer letters. Let the letters used in our words be 1,2,...,*k*. Letters wil be used modulo *k*, i.e. *k*+1=1.

For every positive integer *n* let *c*_{n}=(1,2,...,*n*) be the word consisting of the first *n* letters of the periodic sequence 1,2,...,*k*,1,2,.... Notice that for any word *w*=(*x*_{1},...,*x*_{|w|}) since the letter *x*_{1} appears among the first *k* letters of *c*_{k|w|}, the letter *x*_{2} apears ammong the second *k* letters of *c*_{k|w|} and so on.

*For every word w let f(w) be the greatest nonnegative integer with *; obviously

*f*(

*w*)|

*w*|.

*Case 1: the sequence f*(*w*_{1}),*f*(*w*_{2}),...* is not bounded, i.e. there are arbitrary big values anong f*(*w*_{i})*. *

In this case define the sequence *i*_{1},*i*_{2},... inductively. Let *i*_{1}=1. If is already defined then let be the first index with and . Since *f*(*w*_{1}),*f*(*w*_{2}),... is not bounded, there is such an index. Moreover, . So with this sequence we have and .

*Case 2: the sequence f*(*w*_{1}),*f*(*w*_{2}),...* is bounded; there are only finitely many values among f*(*w*_{i})*. *

*There is a value m which appears infinitely many times among f(w_{i}). Then there is a sequence of indices with *.

Now consider an arbitrary word *w*=(*x*_{1},...,*x*_{s}) with *f*(*w*)=*m*. We split this word in *m*+1 pieces in the following way. Take the first letter 1 in the word *w*; let this be the *h*_{1}th letter. After this point, take the first letter 2; let this be the *h*_{2}th letter and so on. In the *m*th step we take the first letter *m* from the subword *x*_{hm-1+1},...,*x*_{s}. Then let

(If *h*_{1}=1 then *p*_{0}(*w*) is the empty word.)

Now we have

*w*=*p*_{1}(*w*)+*p*_{2}(*w*)+...+*p*_{m+1}(*w*),

so indeed the word *w* is split in *m*+1 subwords.

Note that the indices *h*_{1},...,*h*_{m} do exist in all cases due to . By the definition, for every 1*j**m*, the word *p*_{j}(*w*) does not contain the letter *j* and the first letter of *p*_{j+1}(*w*) is *j*. Finally, the word *p*_{m+1}(*w*) cannot contain the letter *m*+1 because otherwise would hold true, contradicting *f*(*w*)=*m*.

Now split all of into *m*+1 pieces:

*w*_{j0,1}=*p*_{1}(*w*_{j0,1})+*p*_{2}(*w*_{j0,1})+...+*p*_{m+1}(*w*_{j0,1}),

*w*_{j0,2}=*p*_{1}(*w*_{j0,2})+*p*_{2}(*w*_{j0,2})+...+*p*_{m+1}(*w*_{j0,2}),

*w*_{j0,3}=*p*_{1}(*w*_{j0,3})+*p*_{2}(*w*_{j0,3})+...+*p*_{m+1}(*w*_{j0,3}),

The words do not conatin the letter 1. Applying the induction hypothesis to this sequence, there is an infinite subsequnce of the indices such that .

Now consider the sequence . These words do not conatin the letter 2. Applying the induction hypothesis again, there is an infinite subsequnce of the indices such that .

Repeating this step *m*+1 times, we obtain an infinite sequence of indices such that for every positive integer it holds that , , ..., and . But then

We have constructed the desired indices *i*_{1},*i*_{2},... in Case 2 as well.

### Statistics:

9 students sent a solution. 5 points: Ágoston Tamás, Janzer Olivér, Mester Márton, Omer Cerrahoglu, Strenner Péter. 0 point: 4 students.

Problems in Mathematics of KöMaL, September 2011