Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Game of Alternating Bits

  1. Sep 8, 2008 #1
    1. The problem statement, all variables and given/known data

    Player 1 starts by choosing 0 or 1, then player 2, repeat infinitely many times and stick a decimal point in front and see the bit string as a real number between 0 and 1. If it's rational player 1 wins, irrational player 2 wins. Does either player have a winning strategy?

    3. The attempt at a solution

    Player 2 has a winning strategy. He can simply randomly choose bits, and hence he wins with probability 1 (not hard to show). But my professor does not want a probabilistic algorithm. I'm drawing a blank.
     
  2. jcsd
  3. Sep 8, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Pick a definite string of bits for player 2 that will sabotage any chance player 1 has of making the sequence repeat. If you have a repeating binary expansion, then every second bit is also a repeating sequence. Any ideas? The simpler the better.
     
  4. Sep 8, 2008 #3
    It is not clear to me that a sequence is eventually repeating if and only if each subsequence (even and odd) is eventually repeating.
     
  5. Sep 8, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If the odds repeat with period m and the evens repeat with period n, then the whole expansion repeats with period at most 2*m*n. Compare a_i with a_{i+2*m*n}. Can you do the converse?
     
    Last edited: Sep 8, 2008
  6. Sep 8, 2008 #5
    Yes, I got it. Thanks.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook