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!

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


    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


    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Game of Alternating Bits
  1. Bit string (Replies: 1)

  2. Probability Game (Replies: 15)

  3. Game theory (Replies: 2)