Mathematics binary puzzle

  • #1
98
25
The society on Jupiter's moon Io has a very odd way of counting. They count in binary using special counters: small discs with 0 printed on one side and 1 on the other. To increase speed when counting they made a rule:

Rule #1: To get the next number in the sequence, only one counter can be turned over.


To ensure all of their numbers are unique they made a second rule:

Rule #2: The next number in the sequence must not have already appeared.

They start counting with a single counter showing 0 and then flip it to get 1. To progress any further a new counter is needed. Again, to ensure speed, they made this third rule:

Rule #3: When no more numbers can be made a single counter can be added on the left.

They can't put the new counter down with the 0 on top to get 01 because 01 equals 1, which has already been used. Instead, the sequence continues like this:

11, 10

Now another counter must be added on the left:

110

Here there appears to be a choice: do they flip the second counter along to get 100 or the third to get 111? To avoid ambiguity they made a fourth rule:

Rule #4: The next number in the sequence must have the lowest possible value.

So the sequence continues like this:

100, 101, 111, 1111, 1011, 1001, 1000, 1010, 1110, 1100, 1101, 11101, 10101, etc.

The question is: can the Ionians continue to count like this indefinitely while adhering strictly to their four rules?

If you solve the puzzle please explain how you did it.
 

Answers and Replies

  • #2
35,263
11,513
With a different rule 4 you get a Gray code.
The question is: can the Ionians continue to count like this indefinitely while adhering strictly to their four rules?
Yes. How could you not? You can always add a 1 to the left to create a new number if there is no other option left, creating a new number (as no previous number had the same number of digits).
 
  • #3
phinds
Science Advisor
Insights Author
Gold Member
16,738
7,425
With a different rule 4 you get a Gray code.Yes. How could you not? You can always add a 1 to the left to create a new number if there is no other option left, creating a new number (as no previous number had the same number of digits).
Yeah. What he said.
 
  • #4
98
25
Before I post what I think is the solution I will say there is "still scope for further answers".
 
  • #5
98
25
Sorry folks, to make the puzzle work as intended I should have specified a 5th rule:

The Ionians are very concerned about efficient use of materials so:

Rule #5: Leading zero counters must be removed.

i.e. if the most significant bit counter flips to zero, it has to be taken away.

Does this change things at all?
 
  • #6
35,263
11,513
Ah, so we can remove digits. Then it gets more interesting. For the first few digits all options are visited before another 1 is added, but this changes once we go to 6-digit numbers, and more 6-digit numbers are visited after a couple of 7-digit numbers, first at 1101100 -> 101100.
Just by continuing the sequence with some computer assistance, we run into a dead end at 111101101->11101101 after 488 steps.
Code:
import math

def  getsortedoptions(word):
  len=int(math.ceil(math.log(word+1,2)))
  options=[]
  for i in range(0, len+1):
    options = options + [word ^ 2**i]
  options.sort()
  return options

words=[0]
for k in range(0,1000):
  okay=0
  for option in getsortedoptions(words[-1]):
    if option not in words:
      words = words + [option]
      okay=1
      break
  if not okay:
    print "no options left after "+str(k)+" steps"
    break

for word in words:
  print "{0:b}".format(word)
 
  • #7
98
25
Correct! Sorry for the delay in confirming. I was just a bit embarrassed by the blunder about omitting Rule #5.

Here's the solution as intended:

Let’s join the sequence at the 486th term:

#486 1 1 1 1 0 1 1 1 1 = 495
#487 1 1 1 1 0 1 1 0 1 = 493
#488 1 1 1 0 1 1 0 1 = 237

For the first time in the sequence, the most significant bit is changed from 1 to 0 to get the next number, 1 1 1 0 1 1 0 1 (237).

Rule #5 says that leading zeros must be removed so now let’s try to get term #489:

#488 1 1 1 0 1 1 0 1 = 237
Try: 0 1 1 0 1 1 0 1 = 109 Already used as the 121st term
1 0 1 0 1 1 0 1 = 173 the 163rd term
1 1 0 0 1 1 0 1 = 205 the 203rd term
1 1 1 0 0 1 0 1 = 229 the 231st term
1 1 1 0 1 0 0 1 = 233 the 237th term
1 1 1 0 1 1 0 0 = 236 the 193rd term
1 1 1 0 1 1 1 1 = 239 the 235th term
1 1 1 1 1 1 0 1 = 253 the 407th term
1 1 1 1 0 1 1 0 1 = 493 the 487th term

So, because of rule #5 we can’t now add a single counter to get the next term.

Thanks for the Python program. I'm just learning the language and this puzzle was actually my first ever program in this language.

BTW, I discovered the sequence generated is OEIS A163252.
 
  • Like
Likes jim mcnamara

Related Threads on Mathematics binary puzzle

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
20
Views
582
Challenge Math Trick Puzzle
Replies
5
Views
1K
  • Last Post
Replies
4
Views
3K
Replies
10
Views
1K
Replies
39
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
8
Views
2K
Top