wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Single Digit Series
        
(Message started by: Wonderer on Dec 23^rd, 2005, 3:21am)

Title: Single Digit Series
Post by Wonderer on Dec 23^rd, 2005, 3:21am

There’s a series of single digit numbers. The first 6 numbers are 1,0,1,0,1,0. After these, every number in the series equals to the right most digit of the sum of the previous 6 numbers. i.e. 1,0,1,0,1,0,3,5,0,9,8,5,0,……
Question: Is it possible to ever see the following sequence in this series?
0,1,0,1,0,1
Justify your answer!

Well, you are not supposed to write a program, but I can’t really stop you from doing that. However, you need to prove your answer mathematically; your program result doesn’t count. :P

Title: Re: Single Digit Series
Post by Barukh on Dec 23^rd, 2005, 3:44am

on 12/23/05 at 03:21:31, Wonderer wrote:

Well, you are not supposed to write a program, but I can’t really stop you from doing that. However, you need to prove your answer mathematically; your program result doesn’t count. :P

Well, that's actually answers your question, doesn't it? ;D

Title: Re: Single Digit Series
Post by Grimbal on Dec 23^rd, 2005, 3:58am

What if the program outputs a mathematical proof? Not a difficult proof, just a proof with many many steps.

For instance it could make explicit all the terms up to the point where it reaches 0,1,0,1,0,1 or 1,0,1,0,1,0.

Title: Re: Single Digit Series
Post by Wonderer on Dec 23^rd, 2005, 4:11am

on 12/23/05 at 03:58:35, Grimbal wrote:

That would be ok. hehe..

Title: Re: Single Digit Series
Post by Barukh on Dec 23^rd, 2005, 4:12am

on 12/23/05 at 03:58:35, Grimbal wrote:

For instance it could make explicit all the terms up to the point where it reaches 0,1,0,1,0,1 or 1,0,1,0,1,0.

I somehow have a feeling that such a program will never stop.

Title: Re: Single Digit Series
Post by Wonderer on Dec 23^rd, 2005, 4:23am

on 12/23/05 at 04:12:26, Barukh wrote:

I somehow have a feeling that such a program will never stop.

Me too ;D
So, try not to use a program. Do it with a pen, a sheet of paper and your wisdom.

Title: Re: Single Digit Series
Post by towr on Dec 23^rd, 2005, 4:31am

There's a finite number of states, at most 1000000. And because it's deterministic each state can only lead to one other state. So once you have a cycle, you have proved no states except the ones leading to it, and those in the cycle itself, are possible.

Title: Re: Single Digit Series
Post by Grimbal on Dec 23^rd, 2005, 7:38am

on 12/23/05 at 04:12:26, Barukh wrote:

I somehow have a feeling that such a program will never stop.

I don't see why it shouldn't. Given six terms, there is a unique digit that can come before. That means two sequences can not join and become identical, and therefore, the sequence can enter a loop only by restarting the sequence from the start, with 1,0,1,0,1,0. Since the number of states is finite, it must loop, so it must eventually get back to 1,0,1,0,1,0. The only question is whether it will pass thru 0,1,0,1,0,1 before ending the loop or not. But it will definitely stop and give an answer.

Title: Re: Single Digit Series
Post by Aryabhatta on Dec 24^th, 2005, 12:55am

It can never become 0,1,0,1,0,1

Here is why...

[hideb]

Instead of modulo 10, consider modulo 5.
(if acheiving 0,1,0,1,0,1 is possible for 10, it _must_ be possible for 5)

We show that it is not possible for 5.

We are working in the field F₅

Consider the 6x6 matrix A
=

[0 1 0 0 0 0]
[0 0 1 0 0 0]
[0 0 0 1 0 0]
[0 0 0 0 1 0]
[0 0 0 0 0 1]
[1 1 1 1 1 1]

Determinant of A is -1.

let the sequence which we have be
x₁, x₂, ....

Let M_n be the 6x6 matrix

[x_n+1 x_n+2 x_n+3 x_n+4 x_n+5 x_n+6]
[x_n+2 x_n+3 x_n+4 x_n+5 x_n+6 x_n+7]
[x_n+3 x_n+4 x_n+5 x_n+6 x_n+7 x_n+8]
[x_n+4 x_n+5 x_n+6 x_n+7 x_n+8 x_n+9]
[x_n+5 x_n+6 x_n+7 x_n+8 x_n+9 x_n+10]
[x_n+6 x_n+7 x_n+8 x_n+9 x_n+10 x_n+11]

Notice that A*M_n= M_n+1
So Determinant(M_n+1) = - Determinant(M_n)

We have M₀ =

[1, 0, 1, 0, 1, 0]
[0, 1, 0, 1, 0, 3]
[1, 0, 1, 0, 3, 0]
[0, 1, 0, 3, 0, 0]
[1, 0, 3, 0, 0, 4]
[0, 3, 0, 0, 4, 3]

Now Det(M₀) = 84 = 4 (working in F₅)

Thus for any i, det (M_i) = 4 or 1.

Suppose 0,1,0,1,0,1 were possible to achieve.. then for some k

M_k =

[0, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 3]
[0, 1, 0, 1, 3, 1]
[1, 0, 1, 3, 1, 1]
[0, 1, 3, 1, 1, 2]
[1, 3, 1, 1, 2, 3]

But the determinant value of this is -117 = 3 (mod 5) which is not 4 or 1.

Hence, 0,1,0,1,0,1 isn't possible to achieve!

[/hideb]

Title: Re: Single Digit Series
Post by Barukh on Dec 24^th, 2005, 9:58am

Nice solution, Aryabhatta! :D

Title: Re: Single Digit Series
Post by Aryabhatta on Dec 24^th, 2005, 10:17am

Thanks Barukh. :D

I wonder what Wonderer had in mind...