Salem witches – a math puzzle

[update 7-1]: I’m on vacation…will be back with posts the week of the 12th!

I came across a fun math puzzle that’s relates to the game theory of guessing.

The puzzle was posted by James Grime, a mathematician who has posted some nice videos under the name singingbanana.

Let’s get right into it.

The puzzle

I’ve transcribed the puzzle from the original video:

It’s the Salem witch trials and two villagers are accused of being witches.

Now the witch-finder general says “There is a very simple test to tell whether you are witches. Each pick a card from a deck, and you can look at it if you want. But what I want you to do is predict the color of the other person’s card.

I’m going to put you in separate rooms so there is no communication between you. And if you’re both wrong, or one of you is wrong, then you are free to go. But if you both correctly predict the color of the other person’s card, then you are in league with the devil and will be burned at the stake.”

….

You have one minute to discuss strategy before the game begins. What is the strategy to survive?

What do you think? Give it a try before reading the solution below.

The solution

James describes the answer and demonstrates it in detail in this six-minute Youtube video

I came up with the solution when I thought about the possible strategies.

Each witch can either base a guess on the card or perhaps make a random guess. A few ideas that came to mind were:

–each could guess the same color as the card
–each could guess randomly
–one could guess the same color, and the other the opposite

Guessing the same color is not a good idea and they will lose if they are both given the same color cards.

Guessing randomly fares poorly too. There is a 1/2 chance either person guesses correctly, so there is a 1/4 chance both will guess correctly and they will lose.

So the last one to check is the third strategy, and simple deduction shows this is a guaranteed winning strategy.

Imagine the first person guesses the same color and the other guesses the opposite. Then we can see that always one guess of the other person’s card will be wrong:

1 gets red, 2 gets red –> 1 guesses red, 2 guesses blue –> 2 is wrong and they win

1 gets red, 2 gets blue –>1 guesses red, 2 guesses red –> 1 is wrong and they win

1 gets blue, 2 gets red –>1 guesses blue, 2 guesses blue–> 1 is wrong and they win

1 gets blue, 2 gets blue –> 1 guesses blue, 2 guesses red –> 2 is wrong and they win

This proves the strategy works every time, but what exactly is the reason? Why should the cards lead them to a better answer than random guesses?

The trick is based on the logic of the strategies. The cards allow the players to coordinate because they have common knowledge about the structure of the game.

The first player is guessing the same color as the card she gets. In other words, the first player is correct if and only if the two cards are the same color.

The second player does the opposite. The second player’s guess is only right if the two cards are the opposite color.

Obviously the cards are the same color or opposite colors, and therefore only one of the guesses will be right.

This  means no matter which cards are given, the two players will be able to coordinate so that one player guesses wrong and they can both live.