A Few Math Riddles

Hello, and welcome! I wanted to make my first post for this blog about something light, so I thought I would share three of my favorite “over-the-dinner-table” math riddles/problems. These are all in the folklore, but you might not have heard of them. (I certainly didn’t make them up myself – they were told to me at various times during casual conversation.) I have posted the problems sans solutions to increase discussion!

I’ll begin with a classic:

THE HATS PROBLEM

Ten mathematicians are captured by a madman and are imprisoned in a cell. The madman tells them that tomorrow, they must play a (possibly fatal) game. The game proceeds as follows:

The ten mathematicians stand in a line, one behind the other, all facing the same direction. The madman places a single black or white hat on each person’s head. The line is so arranged that each person can see everyone in front of him or her (as well as their hat colors) but cannot turn around and cannot see their own hat. Starting from the back of the line (i.e., the person who can see nine people) and proceeding to the front, the madman gives each mathematician the opportunity to say either “black” or “white”. If the spoken color matches the color of hat on their head, then that mathematician goes free; otherwise, he or she is immediately executed.

To heighten the suspense, the madman declares that everyone will be able to hear the “black” or “white” choices (as well as if the person in question lives or dies). The question is: how can the mathematicians devise a strategy to guarantee the safety of some or most of their group?

For example, the mathematicians could pair up into five groups of two: the 10th and 9th places in line, the 8th and 7th places, and so on, with the rearmost person in each pair saying the color of the hat in front of him. The frontmost person in each pair then knows their hat color and can say it in order to go free. With this strategy, five people are guaranteed to live. Can you do better?

Now, another problem:

A DICE PROBLEM

A hundred computer scientists are playing a game. (They are computer scientists because I heard this riddle at a computer science conference dinner.) Each person simultaneously rolls a regular six-sided die. The participants are sitting in a circle in such a way so that each of them cannot see their own die roll, but can see the rolls of all ninety-nine of their co-workers. After all the dice rolls, each of the hundred people writes down a number from one through six. The participants may choose their number based on the dice rolls of everyone else, but are not allowed to communicate in any way or to see what the others are writing.

The hundred numbers are then simultaneously examined. The group wins if every person correctly guessed the number of his or her own die; if even one person writes down a number that does not mach their die roll, the group loses. Can the group devise a strategy which gives them a decent shot at winning?

At first glance it might seem that the group can’t do better than guessing randomly (after all, seeing everyone else’s dice rolls doesn’t help with guessing your own). To convince you that the all-random strategy can be beaten, let’s take a simpler version of the game with only two people, in which guessing randomly evidently gives a (1/6)^2 = 1/36 chance of winning. Consider, however, the following perverse strategy: each participant writes down the die roll of the other person. Since this strategy wins exactly when the two dice rolls are the same, we now have a 1/6 chance of winning the game!

This two-person strategy isn’t the one that generalizes the most easily to the 100-person game. Can you find – with proof! – an optimal strategy in the general case?

Finally, my favorite:

THE FIVE-CARD TRICK

You and your friend are attempting to work out how to perform a magic trick. The setup of the trick is as follows: you (the assistant) will be given five cards, randomly selected from a standard deck of 52 cards. Initially, your friend (the magician) is not allowed to see any of the five cards. You are allowed to select any four of the cards in your hand and lay them down on the table, in any order you choose. (That is, you remove four of the five cards in your hand and show them, one after one, to your friend.) Your friend is then supposed to (“magically”) guess the remaining fifth card. How can you devise a communication strategy by which your friend can always guess correctly?

For example, one way to approach the problem might be to agree on an ordering of the 52 cards beforehand. Then showing your friend a sequence of four cards is the same as communicating a permutation of (1, 2, 3, 4) (simply by mapping the lowest of the four cards to 1, the second lowest to 2, and so on). Unfortunately this doesn’t seem to be enough information, because there are 24 such permutations and 48 possibilities for the fifth card! (Your friend knows the fifth card is not any of the four cards already shown, giving the number 52 – 4 = 48.) What to do?

Hint: you can get the solution started by observing that there are five cards but four suits, and thus two cards of the same suit. Since you (the assistant) can choose which card is the fifth card, you can choose one of these two as the fifth card and use the other card to communicate the suit.