Game puzzle: Blindfolded coin flipping with adversary

user_2229589 0
Viewed 226

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?

game-theory combinatorics
2 Answers

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

user_16921070

Note that in every turn there are precisely 2 subsets that are winning moves. The total number of subsets is 2^4=16. Therefore, in every turn there is a probability of 2/16=1/8 to win instantly if you randomly choose a subset, where the universe is {1, 2, 3, 4} and 1 denotes the coin in front of you, 2 its neighbor under clockwise order and so on.

If the number of rounds is unbounded, one winning strategy is to repeatedly 'guess' a subset of the coins to flip over. The probability to win within the first n turns is 1 - (7/8)^n. The probability is strictly increasing in n and is asymptotically 1. You will win p-a.s.

Your moves are independent of each other: Your strategy does not incorporate any information from previous turns.

Your adversary does not have any strategy to counter your efforts. Turning the table amounts to relabelling the coins in the set you draw from. You do not exploit the labelling in choosing the subset, therefore the adversary's actions cannot foil your strategy. In particular, after your k-th turn, each of your possible subset choices in turn k+1 has the same likelihood to occur and does not depend on the adversary's action.

To be precise, the relabelling is not completely arbitrary - only 4 out of 4^4=256 possible relabellings can be implemented by turning the table. Again, while this may imply a more efficient strategy for you, it cannot harm you as you do not exploit the information.

Refinement

Never choose 0 or 4 coins as your subset as this can never be a winning move (these moves only ever produce a set of coins with the same face on top if you start with such a configuration). Thus the probability for an instant win is now 2/(16-2)=1/7, with the probability to win within the first n turns becoming 1 - (6/7)^n. This refinement has no effect on the general reasoning behind the strategy.

user_5889160
Related