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 w₁,w₂,... 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 w₁,w₂,.... We prove the Theorem by induction on k. If k=0 then w₁,w₂,... are all empty ant the statement is trivial. So suppose k $\ge$ 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 $w\prec c_{k|w|}$ for any word w=(x₁,...,x_|w|) since the letter x₁ appears among the first k letters of c_k|w|, the letter x₂ 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 $c_{f(w)}\prec w$ ; obviously f(w) $\le$ |w|.

Case 1: the sequence f(w₁),f(w₂),... is not bounded, i.e. there are arbitrary big values anong f(w_i).

In this case define the sequence i₁,i₂,... inductively. Let i₁=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(w₁),f(w₂),... 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(w₁),f(w₂),... 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 $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=(x₁,...,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₁th letter. After this point, take the first letter 2; let this be the h₂th letter and so on. In the mth step we take the first letter m from the subword x_{h_m-1+1},...,x_s. 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 h₁=1 then p₀(w) is the empty word.)

Now we have

w=p₁(w)+p₂(w)+...+p_m+1(w),

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

Note that the indices h₁,...,h_m do exist in all cases due to $c_m\prec m$ . By the definition, for every 1 $\le$ j $\le$ 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 $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:

w_{j_0,1}=p₁(w_{j_0,1})+p₂(w_{j_0,1})+...+p_m+1(w_{j_0,1}),

w_{j_0,2}=p₁(w_{j_0,2})+p₂(w_{j_0,2})+...+p_m+1(w_{j_0,2}),

w_{j_0,3}=p₁(w_{j_0,3})+p₂(w_{j_0,3})+...+p_m+1(w_{j_0,3}),

$\ldots$

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}}) = w_{i_{\ell+1}}.$

We have constructed the desired indices i₁,i₂,... 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

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.

Already signed up?
New to KöMaL?