3
$\begingroup$

What's the minimum number M such that any string with M elements taking values from 1 to N will have a substring repeating itself at least 2 times in a row? The case where N=2 is trivial, you have M=4: 1212 for example the substring 12 repeats itself 2 times in a row, or 1111 where the substring 1 reapeats itself 4 times in a row. It's difficult to find the number even for N=3...

$\endgroup$
  • $\begingroup$ The question is if there's a number of elements such that any string with this number of elements will have a substring repeating itself 2 times in a row $\endgroup$ – Marcelo Campos Dec 5 '15 at 20:24
  • $\begingroup$ You already showed that $4$ works. I think, I'm really not clear on what the question is. These are binary strings? You say "string where values from $1$ to $N$" . Anyway, if it's binary then you have to have a repeat within any four consecutive entries. $\endgroup$ – lulu Dec 5 '15 at 20:27
  • 1
    $\begingroup$ i think i made the question more clear, sorry for the mess $\endgroup$ – Marcelo Campos Dec 5 '15 at 20:29
  • 6
    $\begingroup$ Oh. There is no length $M$ that works, even for $N=3$. en.wikipedia.org/wiki/Square-free_word $\endgroup$ – lulu Dec 5 '15 at 20:36
  • $\begingroup$ I think that is $$M=N+1$$ $\endgroup$ – AsdrubalBeltran Dec 5 '15 at 20:38
3
$\begingroup$

As requested in the comments...

Words of the desired type are said to be "square free". As the OP correctly observes, for binary strings there aren't many instances. $0,1,01,10,101,010$ are the only examples. Somewhat surprisingly, however, even for ternary strings there are infinitely long examples. Wikipedia has a good survey here

Perhaps the simplest, and so far as I know the first, example of an infinite square free ternary word was produced by Thue. It begins with the so-called Thue-Morse binary string, obtained by starting with either character and then successively appending the complement of what's come before. Thus:

$$1,\;10,\;1001,\;10010110,\;1001011001101001,\dots$$

Thue's square free example is then derived from this by taking successive differences. Thus:

$$-1,0,1,-1,1,0,-1,\dots$$

References for these and related results can be found in the Wikipedia article linked to earlier. The proof that the difference sequence of the Thue-Morse word is square free is somewhat lengthy, but it isn't difficult. A good reference for that can be found here.

$\endgroup$

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.