Game of Alternating Bits

1. Sep 8, 2008

Dragonfall

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. Sep 8, 2008

Dick

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.

3. Sep 8, 2008

Dragonfall

It is not clear to me that a sequence is eventually repeating if and only if each subsequence (even and odd) is eventually repeating.

4. Sep 8, 2008

Dick

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
5. Sep 8, 2008

Dragonfall

Yes, I got it. Thanks.