Author |
Topic: Single Digit Series (Read 1307 times) |
|
Wonderer
Newbie
Posts: 18
|
 |
Single Digit Series
« on: Dec 23rd, 2005, 3:21am » |
 Quote  Modify
|
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. 
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
|
Re: Single Digit Series
« Reply #1 on: Dec 23rd, 2005, 3:44am » |
Quote Modify
|
on Dec 23rd, 2005, 3:21am, 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. |
|
Well, that's actually answers your question, doesn't it? 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Single Digit Series
« Reply #2 on: Dec 23rd, 2005, 3:58am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Wonderer
Newbie
Posts: 18
|
|
Re: Single Digit Series
« Reply #3 on: Dec 23rd, 2005, 4:11am » |
Quote Modify
|
on Dec 23rd, 2005, 3:58am, Grimbal wrote: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.
|
|
That would be ok. hehe..
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Single Digit Series
« Reply #4 on: Dec 23rd, 2005, 4:12am » |
Quote Modify
|
on Dec 23rd, 2005, 3:58am, 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.
|
|
IP Logged |
|
|
|
Wonderer
Newbie
Posts: 18
|
|
Re: Single Digit Series
« Reply #5 on: Dec 23rd, 2005, 4:23am » |
Quote Modify
|
on Dec 23rd, 2005, 4:12am, Barukh wrote:
I somehow have a feeling that such a program will never stop.
|
|
Me too
So, try not to use a program. Do it with a pen, a sheet of paper and your wisdom.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Single Digit Series
« Reply #6 on: Dec 23rd, 2005, 4:31am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Single Digit Series
« Reply #7 on: Dec 23rd, 2005, 7:38am » |
Quote Modify
|
on Dec 23rd, 2005, 4:12am, 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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Single Digit Series
« Reply #8 on: Dec 24th, 2005, 12:55am » |
Quote Modify
|
It can never become 0,1,0,1,0,1
Here is why...
| hidden: |
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 F5
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
x1, x2, ....
Let Mn be the 6x6 matrix
[xn+1 xn+2 xn+3 xn+4 xn+5 xn+6]
[xn+2 xn+3 xn+4 xn+5 xn+6 xn+7]
[xn+3 xn+4 xn+5 xn+6 xn+7 xn+8]
[xn+4 xn+5 xn+6 xn+7 xn+8 xn+9]
[xn+5 xn+6 xn+7 xn+8 xn+9 xn+10]
[xn+6 xn+7 xn+8 xn+9 xn+10 xn+11]
Notice that A*Mn= Mn+1
So Determinant(Mn+1) = - Determinant(Mn)
We have M0 =
[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(M0) = 84 = 4 (working in F5)
Thus for any i, det (Mi) = 4 or 1.
Suppose 0,1,0,1,0,1 were possible to achieve.. then for some k
Mk =
[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!
|
|
| « Last Edit: Dec 24th, 2005, 1:01am by Aryabhatta » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Single Digit Series
« Reply #9 on: Dec 24th, 2005, 9:58am » |
Quote Modify
|
Nice solution, Aryabhatta! 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Single Digit Series
« Reply #10 on: Dec 24th, 2005, 10:17am » |
Quote Modify
|
Thanks Barukh.
I wonder what Wonderer had in mind...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print