All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 No Triple Repetitions (Posted on 2013-08-06)
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).

 No Solution Yet Submitted by Brian Smith No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Proof Comment 1 of 1
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

 Search: Search body:
Forums (0)