Game puzzle: Blindfolded coin flipping with adversary
There'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?
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.
You don't start with a winning position. So there are at least one head and one tail coins.
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.
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
- Calculating the Amount of Combinations
- Cyclic group generator of [1, 2, 3, 4, 5, 6] under modulo 7 multiplication
- Is there a simple and efficient way to evaluate Elementary Symmetric Polynomials in Python?
- Manually calculate all coin flip probabilities from real data
- How to iterate through categorical combinatorics of different Enum classes in Python?
- How do I generate all permutations of a list?
- Generate all possible Boolean cases from n Boolean Values
- How many ways can I choose numbers (repeatable) from a set that amount to the same sum?
- Number of ways to tile a W x H Grid with 2 x 1 and 1 x 2 dominos?
- Using multi-indexing to find all combinations matching a certain pattern
- Cartesian product of a dictionary of lists
- Is there an iterator in Python that gives the product but omits permutations of the classes itself?
- Variations with repetition of r integers in {0...k} that sum to u
- number to unique permutation mapping of a sequence containing duplicates
- Count the number of integers in range [0,k] whose sum of digits equals s
- Summing Nodes in a Network
- Count possibilities to reach top of stairs by Taking one, two or three steps at a time
- Checking all possible combinations of integers with a fixed sum and size
- N choose r possibilities as increasing binary numbers
- Parse every k-element subset of an n-element vector
- How can I get my GA to converge?
- Generating combinations in pandas dataframe
- While generating all possible combinations itertools.combinations_with_replacement() vs itertools.product()?
- Get the indices and corresponding combinations that contain given term from a list of combinations with replacement
- Find the vertices of all the sub-simplexes following Barycentric subdivision
- Find most efficient groups of pairs
- Filtering the Results of Expand.Grid
- Find nonnegative integer weights of integer inputs array for integer output, minimizing sum of weights
- List all ways to draw n numbers with replacement out of m < n values (i.o.w.: all partitionings of a set of size n into m distinct subsets) in R
- Formula for the Nth bit_count (or population count) of size M