Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let us consider an infinite or finite number string which consists of $0,1,2$. Then, let us call an adjacent pair of repeating number(s) 'a refrain'.

For example, we have three refrains in the following string :

$$01\overline{2}\ \overline{2}01202\overline{12}\ \overline{12}10\overline{201}\ \overline{201}02$$

Question : Does there exist an infinite number string without any refrain?

Motivation : I've known that there exists an infinite number string which consists of $0,1,2,3$ without any refrain. This got me interested in the above expectation, but I'm facing difficutly. Can anyone help?

share|improve this question
1  
The length of the longest string with no refrain using only $0$ and $1$ is three. To see this, note that no two adjacent terms can be equal, so we either start with $010$ or $101$. In both cases, no matter what comes next, there will be a refrain. Therefore, if we can find an infinitely long string with no refrain using $0, 1,$ and $2$, we must use all three digits. –  Michael Albanese Oct 13 '13 at 15:02
add comment

2 Answers

up vote 6 down vote accepted

What you call "refrain" is called a square in the literature of combinatorics on words. There are many square-free words on an alphabet of three letters. An example is the sequence

$$1, 2, 3, 1, 3, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 3, 1, 3, \ldots$$

which can be obtained by starting with $1$ and then using the morphism $1\to 123$, $2\to 13$, $3\to 2$. (See http://oeis.org/A007413.)

share|improve this answer
1  
Thank you very much for great information! –  mathlove Oct 13 '13 at 15:16
1  
A lot of work is being done on questions like these. For example, a subword repeated three times in a row is called a cube. There are many infinite cube-free words on an alphabet of two letters, the most famous of which is the Thue-Morse word –  Joel Reyes Noche Oct 13 '13 at 15:24
add comment

There is an example for 4-letter alphabet in: G. Lallement, Semigroups and combinatorial applications, Chapt.10, Ex.10.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.