8

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?

mathlove
  • 139,939
  • 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

2 Answers2

6

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.)

JRN
  • 6,566
  • 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 – JRN Oct 13 '13 at 15:24
0

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

Boris Novikov
  • 17,470