You Had Me At Hello: Brainteaser Solution

Thanks to everyone who emailed and tweeted about my “Hello, World” blog post and brainteaser! Following in the footsteps of my fellow Deputy CTO DJ Patil, I’m bringing you the brainteaser solution with a little “back-of-the-napkin” math:

Too easy for you? Let’s kick it up a notch.

The “Alice and Bob” brainteaser I offered is a simplified version of a puzzle I learned from my former student Shirley Gaw. Shirley’s version goes like this:

There are K players seated around a table, on which there is a closed box containing colored hats. The hats come in K colors, and there are K hats of each color in the box. (The players are given a list of the hat colors that are in the box.) The players close their eyes, and a referee puts a hat on each player’s head, with each hat chosen randomly from the box.

Now the players open their eyes. Each player can see the colors of the other players’ hats, but cannot see their own hat. The players cannot communicate in any way.

Each player now seals in an envelope a guess as to the color of their own hat. They can’t see each other’s guesses, and they still can’t communicate.

At the end, the envelopes are unsealed and each player’s guess is compared to the color of their own hat. If at least one player guessed right, they all win as a team. But if they all guessed wrong, then they all lose as a team.

The puzzle is this: Can you think of a strategy the players can agree on in advance that is guaranteed to win every time?

Again, I’ll reveal the solution in a future post and will be posting hints on my Twitter stream @edfelten44. Stay tuned!

Ed Felten is Deputy Chief Technology Officer at the White House Office of Science and Technology Policy.