Brain Teasers
0-1-3-2-6-7-5-4-12-_-_-_
The following series is an alternate method of counting. Every whole number will appear in the series exactly once. What are the next three numbers?
0-1-3-2-6-7-5-4-12-_-_-_
0-1-3-2-6-7-5-4-12-_-_-_
Hint
This sequence was derived in binary. Many types of digital error correction are based on this series due to an important characteristic of the binary pattern.Answer
13-15-14-10-11-...The sequence is called "Gray Code" or sometimes "Gray's Binary" and has many real-world applications. The sequence will count all of the numbers less than 2^n before counting any of the numbers greater than or equal to 2^n.
If you look at the differences between the terms you get:
+1, +2, -1, +4, +1, -2, -1, +8
Looking at every 2nd delta you get:
+1, -1, +1, -1 ...
Every 4th delta:
+2, -2 ...
This continues with every 8th:
+4, -4 ...
and so on.
The pattern is most easily demonstrated in binary. Each successive code in the series has exactly one bit (binary digit) changed, either from 0 to 1 or from 1 to 0. This is the complete 4-bit Gray Code:
0000 = 0
0001 = 1
0011 = 3
0010 = 2
0110 = 6
0111 = 7
0101 = 5
0100 = 4
1100 = 12
1101 = 13
1111 = 15
1110 = 14
1010 = 10
1011 = 11
1001 = 9
1000 = 8
The first 5-bit code is:
11000 = 24
A simple application of this pattern is that it describes the sequence of discs to move in solving the Towers of Hanoi puzzle. Numbering the binary digits from right to left as:
3210
then gives the following sequence when identifying the bit number that is changed:
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
This sequence continues with:
bit 0 changed every 2nd time;
bit 1 changed every 4th time;
bit 2 changed every 8th time;
.
.
.
bit n changed every 2^(n+1) time
If you number the discs with 0 being the smallest disc, 1 the next smallest and so on, then the bit number changed each time is the disc number to move each time. An n-bit Gray Code describes the moves needed to solve an n-disc Towers of Hanoi.
Hide Hint Show Hint Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
That is one giant explanation...
The scariest part is that I actually managed to read it all
You obviously put alot of time in this, and I appreciate that. Well done.
BTW: I couldn't figure it out
The scariest part is that I actually managed to read it all
You obviously put alot of time in this, and I appreciate that. Well done.
BTW: I couldn't figure it out
Excellent! Keep 'em coming. Thanks.
Wow. I still don't get it, and I read the explanation.
More than once...
More than once...
Helpful explanation, I now know the secret to Hanoï
To post a comment, please create an account and sign in.
Follow Braingle!