Define a sequence a(n) such that a(3k)=0, a(3k+1)=1, and a(3k+2) = a(k) for all non-negative integer k.
The sequence starts out as: 0 1 0 0 1 1 0 1 0 0 1 0 0 1 ...

Prove there is no string that repeats three consecutive times. For example 1 0 1 0 1 0 will never occur (1 0 three times). Note that 1 0 1 0 1 1 0 can occur (the extra one breaks the repetition).

Oh look, it's an unsolved problem.

Let N be the length of the string to be repeated.

First consider the case where N is not divisible by 3.  On one of the repetitions, the first character of the string will be determined by a(3k)=0.  On another repetition, the first character will be determined by a(3k+1)=1.  On another repetition, the first character is determined by a(3k+2)=a(k).  Therefore 0=1=a(k).  But this is a contradiction.

Suppose N is divisible by 3.  Let N = 3M.  The string will have lots of a(3k) and a(3k+1) characters, and these pose no problem.  The problem is that each string will have M characters given by a(3k+2)=a(k).

So if N repeats three consecutive times, then there is a string of length M that repeats three consecutive times.  Using the same argument as before, M must be divisible by 3.

We can repeat this argument ad infinitum to show that N must be an infinite power of 3.  Alas, no finite number fits the bill.

Edited on October 5, 2013, 1:55 am

Posted by Tristan on 2013-10-05 01:54:53