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 w1,w2,... is an infinite sequence of words that contain only a finite number of different letters. Then there exists an infinite sequence of 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 w1,w2,.... We prove the Theorem by induction on k. If k=0 then w1,w2,... are all empty ant the statement is trivial. So suppose k1 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 cn=(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=(x1,...,x|w|) since the letter x1 appears among the first k letters of ck|w|, the letter x2 apears ammong the second k letters of ck|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(w1),f(w2),... is not bounded, i.e. there are arbitrary big values anong f(wi).
In this case define the sequence i1,i2,... inductively. Let i1=1. If is already defined then let be the first index with and . Since f(w1),f(w2),... is not bounded, there is such an index. Moreover, . So with this sequence we have and .
Case 2: the sequence f(w1),f(w2),... is bounded; there are only finitely many values among f(wi).
There is a value m which appears infinitely many times among f(wi). Then there is a sequence of indices with .
Now consider an arbitrary word w=(x1,...,xs) 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 h1th letter. After this point, take the first letter 2; let this be the h2th letter and so on. In the mth step we take the first letter m from the subword xhm-1+1,...,xs. Then let
(If h1=1 then p0(w) is the empty word.)
Now we have
w=p1(w)+p2(w)+...+pm+1(w),
so indeed the word w is split in m+1 subwords.
Note that the indices h1,...,hm do exist in all cases due to . By the definition, for every 1jm, the word pj(w) does not contain the letter j and the first letter of pj+1(w) is j. Finally, the word pm+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:
wj0,1=p1(wj0,1)+p2(wj0,1)+...+pm+1(wj0,1),
wj0,2=p1(wj0,2)+p2(wj0,2)+...+pm+1(wj0,2),
wj0,3=p1(wj0,3)+p2(wj0,3)+...+pm+1(wj0,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 i1,i2,... 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