Interesting Stuff

This is closer to the unsolved hat problem I have previously discussed than the solved hat problem I discussed. It made the rounds on a “Math Enthusiasts” mailing list I’m on today.

There are n people who have been given a challenge: tomorrow, a hat will be placed on each of their heads. There are n different colors of hats, and colors can be repeated (or not used at all). Everyone will be able to see the hats on everyone else’s head but not their own. No one is allowed to communicate in any way while looking at each others’ hats. Then everyone is lead away into separate rooms and each person is asked the color of their own hat. If at least one person answers correctly, the group as a whole wins (unlike the unsolved hat problem mentioned above, no one is penalized for an incorrect guess). The people can discuss strategy amongst themselves before the challenge starts, but cannot communicate in any way once anyone gets a hat.

What strategy can they use to guarantee that the group wins?

and for the pedants out there: all participants are told all possible hat colors before the challenge starts (no need to guess what the unseen colors might be), and n is small enough that all colors can be distinguished on sight (it uses less than a million different shades of blue, for instance).

I got this one from Alasdair months ago, and it’s a doozy. However, it’s really only intended for the mathematically minded, so feel free to skip if you’re not comfortable with introductory probability. It’s a multi-part question, but the first parts are intended to be easy, so don’t second-guess yourself too much on those.

1. A guy is repeatedly rolling an unbiased six-sided die in a room when you enter the room and start watching him. How many rolls do you expect to watch before he rolls a 1?
2. On further inspection, you notice that he has written down his previous rolls in a list. How far back in the list do you expect to have to look before seeing the previous 1? You can assume that the guy has been doing this for long enough that he rolled a 1 at some point in the past.
3. Define a “drought of 1’s” as the die rolls between successive 1’s (including the bounding 1’s). For instance, the rolls 1-4-2-1-5-1 would constitute a drought of length 4 followed by a drought of length 3. What is the expected length of a drought of 1’s?

The typical answers to the above questions are six, six, and seven (since we’re including both the starting 1 and the ending 1). However, this implies that on average droughts will have length seven, but when you walk into the room the average drought will have length twelve: you’d expect to be six rolls into the drought already, and you’d expect six more once you start watching. What’s going on here? How should this discrepancy be resolved?

Also courtesy of Steamboat Steven. That guy has all kinds of neat puzzles!

There are n prisoners on a train being taken to a prison. Once they arrive there, they will each be put in separate sensory deprivation chambers. They will have no conception of how long they have been in there. However, sometimes a guard will take one of them into a room with two switches on the wall, make the prisoner flip one of the switches, and send him back to his sensory deprivation chamber. If you wait long enough, every prisoner will go to the switch room an arbitrarily large number of times (i.e., none of them will be “starved” of visits to the switch room). At any time, any prisoner may make the claim that all prisoners have been in the switch room at least once. If he is right when making this claim, they will all be set free. If he is wrong, they will all be killed.

The prisoners can discuss and agree on a strategy for the switches right now, but once they reach the prison they won’t see each other again. They don’t know the initial configuration of the switches. No prisoner will know how many other prisoners have visited the switch room before him; the person who goes to the switch room first won’t know he’s the first. They won’t know how often the guards take people to the switch room, and even if they did they wouldn’t know how much time has passed between their own visits.

How can they be guaranteed to eventually go free?

Steamboat Steven gave me this gem. Unlike my previous discussion of a hat problem, this one can be solved in a reasonably short amount of time.

There are n people on a staircase facing downstairs when a hat is placed on each person’s head. There are c different hat colors, and each hat has a 1/c chance of being each color (that is to say, the color of each hat is independent; some of the c colors might not be used anywhere, while others may be very common). Each person can see the color of every hat downstairs from her, but not the color of her own hat or any hat upstairs. Starting at the top of the stairs and working down to the bottom, each person guesses the color of her own hat. Each person can hear all previous guesses.

The group as a whole gets 1 point for every correct guess, and nothing for incorrect guesses. If the group is allowed to discuss and to agree upon a strategy ahead of time, how many correct guesses can they guarantee?

One naïve strategy would be to have people 1, 3, 5, &c simply say the color of the hat in front of them, and have people 2, 4, 6, &c repeat that color, guaranteeing n/2 correct guesses. It turns out you can do a lot better. How?

Today at work we bandied about an interesting logic puzzle, and understanding the answer totally blew my mind. It goes like this:

All dragons have either red eyes or green eyes. If a dragon ever knows its own eye color, it will die on the next stroke of midnight. Moreover, dragons, like all mythical beasts, are perfect logicians. That is to say, if it is possible to infer a fact from what is already known, dragons cannot help but make this deduction.

There is a town in which n dragons live, where n is small enough that every day, every dragon interacts with every other dragon. One day, an oracle, renowned for always speaking the truth, comes to the town. She gathers together all the dragons, looks at each one, and then loudly proclaims, “At least one dragon here has red eyes!”

1. What happens in the town?
2. Suppose that at least three dragons have red eyes. Now, not only does every dragon already know that at least one dragon has red eyes, they also know that every other dragon knows this, too. What information does the oracle add that the dragons didn’t have already?