Define a sequence a(n) such that a(3k)=0, a(3k+1)=1, and a(3k+2) = a(k) for all nonnegative 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 20131005 01:54:53 