1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Mathematics binary puzzle

Tags:
  1. Jun 3, 2018 #1
    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.
     
  2. jcsd
  3. Jun 3, 2018 #2

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    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).
     
  4. Jun 3, 2018 #3

    phinds

    User Avatar
    Gold Member

    Yeah. What he said.
     
  5. Jun 4, 2018 #4
    Before I post what I think is the solution I will say there is "still scope for further answers".
     
  6. Jun 4, 2018 #5
    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?
     
  7. Jun 4, 2018 #6

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    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 (Text):
    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)
     
  8. Jun 14, 2018 #7
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted