Search code examples
combinatoricsgame-theory

Game puzzle: Blindfolded coin flipping with adversary

Bad rendition of problemThere's a table with four coins with random initial faces. You're blindfolded and each turn, you have to choose a subset of coins to flip over. Your objective is to make them all face the same way.

There is also someone else who, after you flip some coins, will rotate the table as much as they want during their turn. Their objective is to not let you win. Since you're blindfolded, you're not aware of how much the table has been rotated.

A sample game would look like: You go first, flip the top and left coins. Then, the adversary rotates the board 180 deg. Then it's your turn and you flip the bottom and right coins ( in this case, zero work was done).

What is the strategy to win?

Solution

  • I'm using the following moves:

    • 1 : Flip a single coin (eg: the one in front of you)
    • D : (Diagonal) Flip two opposite coins (the one in front of you, the one in front of your adversary)
    • A : (Adjacent) Flip two adjacent coins (the one in front of you and the one on the right)

    Then the sequence

    D A D 1 D A D

    passes always though a winning state !

    This is proved by case analysis.

    1. You don't start with a winning position. So there are at least one head and one tail coins.

    2. I assume first that there are 2 heads and 2 tails.

      Remark that, in this case, any D and A move either wins or keep 2 heads and 2 tails.

      2a. If the two head are facing then D wins.

      2b. If not then D doesn't change the state upto rotation (two adjacent head coins) Then if you do A, either you win or you get two facing heads. So you arr back in 2a.

      Summary : D A D wins if they are 2 heads and 2 tails.

    3. If not, D A D keeps a state with one coins of a sort and three of the other. So if D A D didn't win you know that you are in such a state.

      Now if you just flip a coin, either you win or you end up with a 2 heads and 2 tails state. Therefore another D A D wins.

    So

    D A D 1 D A D

    always wins !!!

    I dont know in English, but in French this is a classical in automaton called "Le barman aveugle" (the blind bartender). There are a lot of page about this problem. EG: This page

    EDIT: I just dicovered an English page on Wikipedia