## Thursday, 28 March 2013

### Today I Learned: the Thue-Morse sequence

I did the 15 km run for the kids last Sunday. It took me about 80 minutes to run the whole thing, and I beat my frenemy Han Liang Gan by 1 second. So, yea, pretty much the best run ever! =)

Orrite - it's maths time! Now, let's say that you're only allowed to write "A"s and "B"s, no spaces and no punctuation. What's the length of a longest square-free word that you can write? That is: what is a longest word that you can write before you have the same sequence of letters appearing twice consecutively, such as in AA or ABAB?

Okay, orrite, orrite - that was a pretty silly question. The answer is obviously 3 (either ABA or BAB).

But what if I'd asked for the longest cube-free word instead? That is: subsequences like ABAABAABA are forbidden since it's ABA repeated thrice.

Well, the answer is $$\infty$$.

And in fact, it's actually surprisingly easy to construct an example of an infinitely long cube-free word:

The Thue-Morse sequence.
A$$\rightarrow$$AB$$\rightarrow$$ABBA$$\rightarrow$$ABBABAAB$$\rightarrow$$ABBABAABBAABABBA$$\rightarrow$$$$\ldots$$