3
$\begingroup$

Problem description:

Suppose we use a set of digits $\{0,1,2\}$ to form a sequence, for example \begin{equation} 120210120102012102010210120212010\cdots \end{equation} The length can be finite or infinite.

The sequence is invalid if there are two finite subsequences appears consecutively. For example, the following sequences are invalid \begin{equation} 0{\bf 11}\cdots, \quad 010{\bf 201\, 201 }\cdots \end{equation} where the consecutive subsequences are highlighted.

Question: Does there exist a valid sequence of infinite length? (a non-constructive proof is also acceptable; but a constructive one would be better.)

One way to think about it:

We can transform the sequence to a (base 3) real number, \begin{equation} 120\cdots \rightarrow 0.120\cdots \end{equation} Then the only possible infinite sequence should be a irrational number. Irrational number has no period, which means the pattern will not repeat infinite many times, but may repeat finite many times. A famous example is the Feynman point,

The Feynman point is a sequence of six 9s that begins at the 762nd decimal place of the decimal representation of $\pi$.

So not all irrational number($\le 1$) are valid sequences.

I use a short program to do enumeration, but it quickly falls in exponential growth of candidates. I failed to come up with a contraction.

Generalization:

Can we take a larger set like $\{0,1,2,3, \cdots, n\}$? Can we relax the constraint to be three consecutive repetition or more?

Motivation

This problem origins from threefold repetition rule in chess,

In chess and some other abstract strategy games, the threefold repetition rule (also known as repetition of position) states that a player can claim a draw if the same position occurs three times, or will occur after their next move, with the same player to move. The repeated positions do not need to occur in succession. The idea behind the rule is that if the position occurs three times, no progress is being made.

It reduces to the proposed problem if we modify the this rule to be "the same position occurs two times with the same sequences of moves".

Thanks for your help.

Edit: I find a related question: Largest binary sequence with no more than two repeated subsequences

$\endgroup$
  • $\begingroup$ "Not all irrational numbers are valid sequences" is quite an understatement. In fact, almost all real numbers (in the sense of Lebesgue measure) are irrational and "invalid". $\endgroup$ – bof Nov 2 '15 at 6:44
3
$\begingroup$

Yes, there are "valid" infinite sequences with three digits. They are called square-free words. Quoting the Wikipedia article:

In combinatorics, a square-free word is a word (a sequence of characters) that does not contain any subword twice in a row.

Thus a square-free word is one that avoids the pattern $XX.$

One example of an infinite square-free word over an alphabet of size $3$ is the word over the alphabet $\{0,\pm1\}$ obtained by taking the first difference of the Thue–Morse sequence. That is, from the Thue–Morse sequence $$0,\ 1,\ 1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 1,\ 0,\ 0,\ 1,\ 0,\ 1,\ 1,\ 0,\dots$$ one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is $$1,\ 0,\ −1,\ 1,\ −1,\ 0,\ 1,\ 0,\ −1,\ 0,\ 1,\ −1,\ 1,\ 0,\ −1,\dots$$ (sequence A029883 in OEIS).

Another example found by John Leech is defined recursively over the alphabet $\{a,\ b,\ c\}.$ Let $w_1$ be any word starting with the letter $a$. Define the words $\{w_i \mid i \in \mathbb{N} \}$ recursively as follows: the word $w_{i+1}$ is obtained from $w_i$ by replacing each $a$ in $w_i$ with $abcbacbcabcba,$ each $b$ with $bcacbacabcacb,$ and each $c$ with $cabacbabcabac.$ It is possible to check that the sequence converges to the infinite square-free word $$abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb\dots$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! The "square free word" is the keyword I'm looking for. $\endgroup$ – anecdote Nov 2 '15 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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