Skip to main content
2 of 2
added 1331 characters in body

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