Subwords of cube-free binary words I'm currently working on subwords of cube-free binary words.
A binary word is one composed of letters from a two-letter alphabet such as $\{0,1\}$.  A word $y$ is a subword of $w$ if there exist words $x$ and $z$ (possibly empty) such that $w=xyz$. Thus, $01$ is a subword of $0110$, but $00$ is not a subword of $0110$.  A word is cube-free if it does not contain subwords of the form $xxx$, where $x$ is a word of one or more letters.
I suspect that all sufficiently long cube-free binary words (those whose length is greater than a certain $n$) contain all the subwords $001$, $010$, $011$, $100$, $101$, and $110$.  I know that $n\ge 21$ because the cube-free binary word $110011001101100110011$ has a length of 21 and does not contain the subword $010$.
Does anyone know the length of the longest cube-free binary word that does not contain all the three-letter subwords I mentioned above?
 A: The word $1001$-$1001$-$101$-$1001$-$101$-$1001$-$1$ (separated to show how it was constructed and to ease reading) is cube-free and does not contain the subword $010$.
Perhaps you can prove that no 24 letter word begins with a $1$ and avoids $010$ by arguing about possible arrangements of the words $1001$ and $101$. 
A: I may lose my own bet.  By hand I computed less than 50 binary words of length 10 that start with 0.  A little less than 40 of them have 4 or 5 of the subwords.  This should be easily handled by computer, and with some patience can be completed by hand.  My guess is that 21 is close to the maximum, and that there will be less than 10 words of maximal length.
EDIT 2012.09.20: Here is more detail on my pseudo elegant idea mentioned in comments to the question.  
Assume we are trying to make a cubefree word which avoids 011.  Then after an initial block of at most two ones, our word has a subword matching the regexp ((0|00)1)*, where the subpattern repeats more than 3 times if we are getting a long such word.
Then 001001001 and 010010010 and 010101 and 101010 are other words to be avoided, so the pattern has to alternate between 00101 and 01001, but also cannot contain that pattern three times in a row. So it can have at most 5 occurrences of 00 , one of which appears in 10100101, and two occurrences of 101,
otherwise a cube will appear.  So the regexp repetition will happen at most 7 times, by my mental (mis?)calculation.
A similar argument appears for avoiding 011, and also avoiding 010, in which case 11 is the subpattern replacing 1 in the regexp above.  A similar case for 0 occurs in the 0-1 reversal of letters for the remaining words.
By this analysis, I get 28 as an upper bound, with candidate word
1100110011011001101100110011. Unfortunately that has a cube in it, so the real bound is likely to be lower.
Again, this should be doable by hand, but Joel should verify it by computer, or deflate the above argument.
END EDIT 2012.09.20
Gerhard "Just Keep Adding Another Digit" Paseman, 2012.09.19
A: Try this: start with the infinite Thue-Morse word $TM = 0110100110010110...$ which is known to be cubefree and make the following transformations:
$0 \Rightarrow x0$
$1 \Rightarrow x1$
This gives the the infinite word:
$TM^\prime = x0x1x1x0x1x0x0x1x1x0x0x1x0x1x1x0x...$
Next make the following transformation on $TM^\prime$:
$x\Rightarrow 11$
$0\Rightarrow 0$
$1\Rightarrow 00$
This gives the following infinite word:
$C = 110110011001101100110110110011...$
Clearly $C$ does not contain the subword $010$, and unless I overlooked something in my analysis, the cube-freeness of $TM$ implies $C$ is also cube-free, which would mean there is no upper bound to the size of cube-free binary strings not containing all six of the given strings.
(Incidentally, the composition of these two transformations is equivalent to performing the transformation $0\Rightarrow 110$, $1\Rightarrow 1100$ on $TM$ to get $C$, but I figured the intermediate step makes it a bit clearer, to me at least, why $C$ should be cube-free).
If anyone sees any flaw in the reasoning that $C$ is cube-free, please do point it out.
