Ed Felten, a well-known computer security analyst, recently became the Deputy U.S. Chief Technology Officer for Obama’s White House.
As his introduction to the presidential team, he posted a brainteaser.
I haven’t read any other answers. Here’s mine, and the thought process behind it.
At first it seemed completely impossible, since Alice and Bob have no knowledge of each other’s coin flips. So I reasoned that there had to be a strategy, that both of them knew going in, which would allow each to predict (at least in part) how the other would react.
The coinflips were obviously analogous to 1’s and 0’s. I smelled that there would be a role for the XOR operator, because whenever people do weird things with bitfields, the XOR swap algorithm isn’t far behind.
With that direction it wasn’t hard to figure out. Here’s the strategy:
- Heads are considered 1’s, tails are considered 0’s.
- Alice flips her coin, and XORs her result with 1 to get her guess for Bob’s result.
- Bob flips his coin, and XORs his result with 0, and uses that as his guess for Alice’s result.
It sounds impossible so you just have to do all the truth tables to see that it works. The correct guess is highlighted in green.
| Alice | Bob | |
|---|---|---|
| flip | 1 | 1 |
| XOR | 1 | 0 |
| guess | 0 | 1 |
| Alice | Bob | |
|---|---|---|
| flip | 1 | 0 |
| XOR | 1 | 0 |
| guess | 0 | 0 |
| Alice | Bob | |
|---|---|---|
| flip | 0 | 1 |
| XOR | 1 | 0 |
| guess | 1 | 1 |
| Alice | Bob | |
|---|---|---|
| flip | 0 | 0 |
| XOR | 1 | 0 |
| guess | 1 | 0 |
Why it works
The above truth tables might be a sufficient demonstration, at least for the purposes of a proof, but it still seems like magic. Can we make it intuitively obvious?
We could restate the strategy like this:
- Alice always guesses Bob’s coin is the opposite of hers.
- Bob always guesses Alice’s coin is the same as his.
Then it’s clear that one of them has to be right! The only options, for the whole system, are that the coins are different or the same.