Game of Alternating Bits: Is There a Winning Strategy?

  • Thread starter Dragonfall
  • Start date
  • Tags
    Bits Game
In summary, Player 2 has a winning strategy in this game where player 1 chooses a number and player 2 tries to sabotage their sequence. The strategy involves randomly choosing bits, ensuring a win with probability 1. However, a probabilistic algorithm is not desired. Player 2 can also choose a specific string of bits that will prevent player 1 from creating a repeating sequence. It is not certain that a sequence is eventually repeating only if each subsequence (even and odd) is also eventually repeating. The period of the overall sequence can be at most 2 times the period of the even and odd subsequences. The converse is also possible.
  • #1
Dragonfall
1,030
4

Homework Statement



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?

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.
 
Physics news on Phys.org
  • #2
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
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
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:
  • #5
Yes, I got it. Thanks.
 

1. What is the "Game of Alternating Bits"?

The "Game of Alternating Bits" is a mathematical game where players take turns changing the value of a binary string. The goal of the game is to create a string where all adjacent bits have different values.

2. How do you play the "Game of Alternating Bits"?

To play the game, two players take turns changing the value of a binary string by flipping one or more bits. The first player to create a string where all adjacent bits are different wins the game.

3. What is the significance of the "Game of Alternating Bits"?

The "Game of Alternating Bits" has applications in computer science, particularly in coding theory and digital signal processing. It also has connections to other mathematical concepts such as graph theory and combinatorics.

4. Can the "Game of Alternating Bits" be played with more than two players?

Yes, the game can be played with any number of players. However, it may become more complex and have different strategies depending on the number of players.

5. Are there any variations of the "Game of Alternating Bits"?

Yes, there are variations of the game that involve different rules or objectives. Some variations include changing multiple bits at a time or trying to create a string with alternating bit patterns instead of just alternating values.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
16
Views
3K
Replies
1
Views
967
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
779
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Quantum Interpretations and Foundations
Replies
2
Views
648
Back
Top