Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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. u\prec v denotes that the word u is a subsequence of v. The relation \prec is reflexive and transitive, i.e. u\prec u for all u and u\prec v and v\prec w implies u\prec w. 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 i_1<i_2<\ldots of indices such that w_{i_1}\prec w_{i_2}\prec w_{i_3}\prec\ldots.

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 k\ge1 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 w\prec c_{k|w|} 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 c_{f(w)}\prec w; obviously f(w)\le|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 i_\ell is already defined then let i_{\ell+1} be the first index with i_{\ell+1}>i_\ell and f(w_{i_{\ell+1}})\ge
k|w_{i_\ell}|. Since f(w1),f(w2),... is not bounded, there is such an index. Moreover, w_{i_\ell} \prec c_{k|w_{i_\ell}|} \prec
c_{f(w_{i_{\ell+1}})} \prec w_{i_{\ell+1}}. So with this sequence we have i_1<i_2<\ldots and w_{i_1}\prec w_{i_2}\prec\ldots.

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 j_{0,1}<j_{0,2}<j_{0,3}<\ldots of indices with f(w_{j_{0,1}})=f(w_{j_{0,2}})=\ldots=m.

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

p_1(w) = (x_1,\dots,x_{h_1-1}), \quad
p_2(w) = (x_{h_1},\dots,x_{h_2-1}), \quad
\ldots, \quad
p_{m+1}(w) = (x_{h_m},\dots,x_s).

(If h1=1 then p0(w) is the empty word.)

Now we have


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

Note that the indices h1,...,hm do exist in all cases due to c_m\prec m. By the definition, for every 1\lej\lem, 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 c_{m+1}\prec w would hold true, contradicting f(w)=m.

Now split all of w_{j_{0,1}},w_{j_{0,2}},\ldots into m+1 pieces:





The words p_1(w_{j_{0,1}}),p_1(w_{j_{0,2}}),p_1(w_{j_{0,3}}),\ldots do not conatin the letter 1. Applying the induction hypothesis to this sequence, there is an infinite subsequnce j_{1,1}<j_{1,2}<\ldots of the indices j_{0,1}<j_{0,2}<\ldots such that p_1(w_{j_{1,1}})\prec p_1(w_{j_{1,2}})\prec\ldots.

Now consider the sequence p_2(w_{j_{1,1}}),p_2(w_{j_{1,2}}),\ldots. These words do not conatin the letter 2. Applying the induction hypothesis again, there is an infinite subsequnce j_{2,1}<j_{2,2}<\ldots of the indices j_{1,1}<j_{1,2}<\ldots such that p_2(w_{j_{21}})\prec p_2(w_{j_{22}})\prec\ldots.

Repeating this step m+1 times, we obtain an infinite sequence i_1=j_{m+1,1}<i_2=j_{m+1,2}<\ldots of indices such that for every positive integer \ell it holds that p_1(w_{i_\ell}) \prec
p_1(w_{i_{\ell+1}}), p_2(w_{i_\ell}) \prec p_2(w_{i_{\ell+1}}), ..., p_m(w_{i_\ell}) \prec p_m(w_{i_{\ell+1}}) and p_{m+1}(w_{i_\ell}) \prec p_{m+1}(w_{i_{\ell+1}}). But then

w_{i_\ell} =
p_1(w_{i_\ell}) + \ldots + p_{m+1}(w_{i_\ell}) \prec
p_1(w_{i_{\ell+1}}) + \ldots + p_{m+1}(w_{i_{\ell+1}}) =

We have constructed the desired indices i1,i2,... in Case 2 as well.


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