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.

- Start with an initial sequence just given by: A.
- Stick a copy of the sequence that you've got at the end, but with "A"s and "B"s switched.
- Go back to step 2.

A\(\rightarrow\)AB\(\rightarrow\)ABBA\(\rightarrow\)ABBABAAB\(\rightarrow\)ABBABAABBAABABBA\(\rightarrow\)\(\ldots\)

So how can we prove this? Well, I'm certainly not going to write up a proof right now - I'm off to Easter camp tomorrow and there's much packing and stuff to be done! =)

## No comments:

## Post a Comment