Ed Felten, the Deputy Chief Technology Officer at the White House Office of Science and Technology Policy, posted this fun, little coordination problem. The gist is that Alice and Bob are a team. Each in separate rooms, they flip a coin. They note what they flipped (Heads or Tails) and write down a guess as to the other’s flip. They win as a team as long as either of them are correct. It’s helpful to enumerate all the possible flip outcomes across both Alice and Bob to try to work out a winning strategy. Here’s the four possibilities:
(Bob flips Heads, Alice flips Tails)
(Bob flips Tails, Alice flips Heads)
(Bob flips Tails, Alice flips Tails)
(Bob flips Heads, Alice flips Heads)
Those are the only four possibilities. Having enumerated all of the cases, we can start to make some guesses and check if it results in a win for any of the possibilities. As noted in the original blog post, it’s easy to see that Alice and Bob simply agreeing to always pick Heads or Tails isn’t going to work. If they both always pick Heads, then neither will guess correctly when they both flip a Tails.
It’s helpful to try some other possibilities and see where it comes up short. One idea is to have Bob always pick the opposite of what he flips (if he flips a Heads then he guesses Tails and vice versa). Alice, on the other hand, just always picks Tails. Does this work?
(Bob Heads, Alice Tails) √ that works because Bob guesses the opposite
(Bob Tails, Alice Heads) √ ditto
(Bob Tails, Alice Tails) √ this works because Alice always guesses Tails
(Bob Heads, Alice Heads) x this is where it fails Alice guessed tails and so did Bob.
You can keep trying out cases — and it’s helpful to do so because it gets your mind engaged in the problem. All of the losing strategies suffer from the same problem, there’s always one case where it doesn’t work out.
We can simplify the problem here by making one observation. Even though there are four concrete possibilities as to the combination of Alice and Bob’s flips, conceptually there’s only two: they either flip the same side of the coin or they flip a different side. This simplifies the problem and directs us to what exactly we’re trying to solve. We simply need to make sure that, together, Bob and Alice account for both situations. So, again, they either flipped the same side or they flipped different sides. With this, we can formulate the winning strategy. Alice and Bob, together, need to cover both cases. How? One of them bets that they landed on the same side and one of them bets that they landed on a different side.
In code, the solution looks like this:
data Coinside = Heads | Tails
data Person = Bob | Alice
type Strategy = Person -> (Coinside -> Coinside)
opposite :: Coinside -> Coinside
opposite Heads = Tails
opposite Tails = Heads
winningStrategy :: Strategy
winningStrategy Bob = id
winningStrategy Alice = opposite
Or in words: Alice always guesses the opposite of what she flipped and Bob always guesses the same side as what he flipped. They could flip the same sides or different ones. Either way one of them will always be right.