Alphabet $A$ contains $n$ letters. $S$ is a set of words of finite length composed of letters of $A$. It is known that every infinite sequence of letters of $A$ begins with one and only one word of $S$. Prove that the set $S$ is finite. Proposed by F. Bakharev
Problem
Source: Tuymaada 2003, day 1, problem 3.
Tags: combinatorics proposed, combinatorics
05.05.2007 19:27
Nice problem! Suppose that $S$ is infinite, then there is an $a_{1}\in A$ such that infinitely many words in S begin with $a_{1}$. Likewise, there is a $a_{2}\in A$ such that infinitely many words in S begin with $a_{1}a_{2}$. And so on. Thus we get an infinite sequence $a_{1},a_{2},a_{3},\ldots$ in $A$ such that for every $n$ infinitely many words of $S$ begin with $a_{1}\ldots a_{n}$. (x) As a consequence the infinite word $a_{1}a_{2}\ldots$ does not begin with a word of $S$. (Suppose that $a_{1}\ldots a_{n}\in S$, then by (x) there is also a word $a_{1}\ldots a_{n}b_{1}\ldots b_{m}$ in $S$. Thus every infinite word starting with $a_{1}\ldots a_{n}b_{1}\ldots b_{m}$ begins with at least two words of $S$. Contradiction.)
12.09.2009 15:56
This is an application of Konig's infinity lemma. Assume $ S$ infinite. For any word $ w \in S$ define $ w_n \in A$ to be the letter on $ n^{\textrm{th}}$ position in $ w$, and $ S_n = \{ w_n \; ; \; w \in S\}$. Take now $ V_n = \{n\} \times S_n$. Clearly the sets $ V_n$ are non-empty, finite, and pairwise disjoint, therefore Konig's infinity lemma applies, so there exists an infinite word $ \Omega$ like the one exhibited in the previous post.
20.02.2019 22:41
Sorry for reviving an old topic but what's the problem with the following construction? $n=2,S={a,ba,bba,bbba,\dots }$ Where $a,b$ are the letters of alphabet.
20.02.2019 23:08
The infinite string $bbb\cdots$ does not begin with any words from your set $S$.