When will a string have a repeating substring? 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...
 A: 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.
