brain teasers

I love brain teasers. Not all brain teasers. There are different kinds. Some just require churning through lots of possibilities. These generally require paper. I'm bad at that, and I hate it. I like brain teasers that are simple -- that I can hold completely in my mind.

Here are the best one's I've heard:

My dad told me this one. He said he heard it on Car Talk. I don't remember the exact story, but I believe I have the same puzzle:

There is a prison with twenty prisoners. The warden calls them into a room. He says he's going to play a game with them. It goes like this. They can talk to each other for an hour strategizing. After that, they will all go into solitary confinement, and they'll never be able to talk to each other again. Each day, the warden will bring a random prisoner into a special room with two switches. Each switch can be up or down -- not anywhere in between. The prisoner may put the switches into whatever configuration they chose, and then they'll be taken back to their cell. Now, if a prisoner ever asserts to the warden that all the prisoners have been to the switch room, he'll let everyone free if this is true, and kill everyone if it is false. How can the prisoners ensure eventual freedom, with no chance of death?

A friend in grad school told me this one. Again, I don't remember the exact story, but I believe the puzzle is the same:

There are 100 quarters on a table. You happen to know that 20 of them are heads-up. Unfortunately, you are blind, and you cannot feel the difference between heads-up and tails-up. Your task is to sort the quarters into two groups with one requirement: each group must contain the same number of heads-up quarters.

I think I've heard this one from multiple sources, but it's still good:

You have 9 identical looking balls. One of them is a little heavier, but you can't tell which one. Fortunately you have a balance-scale. What is the fewest number of weighings required to identify the heavier ball?

Here is an upgrade to the 9-ball puzzle, though I failed to solve it in my head. I thought I had the answer, but wasn't sure, so I wrote a program to solve it, and the program showed a way to solve it with one fewer weighing than I thought:

You have 12 identical looking balls. One of them weighs a little different than the others, either heavier or lighter, you don't know which. You have the same trusty balance-scale. What is the fewest number of weighings required to identify the different ball, and know whether it is heavier or lighter?

I heard this one just today from a professor doing a sabbatical at my place of work:

You have three independent random variables X, Y and Z. Is it possible to define the distribution of each variable such that there is more than a 50% chance of X > Y, a more than 50% chance of Y > Z, and a more than 50% chance of Z > X?

update: I should include the Monty Hall problem here, though I failed to solve it in my head. In fact, after I was told the solution, I didn't believe it, and I wrote a program on my TI-83 to prove the solution wrong -- but it proved the solution right. Here's the problem from wikipedia:

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1 [but the door is not opened], and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

NOTE: I think it is important to the puzzle to further state that the host would not have opened the door with the car. Wikipedia's version says that the host knows what's behind the doors, but we need to know that the host is actually using this information to find a door with a goat. I discuss this issue in this post (note that it gives away the answer, but I suspect anyone reading to this point already knows the answer).

update: Here's another puzzle I like. I'm not sure where I heard it. It goes something like this:

The teacher lines up 3 students, one behind the other, all facing the whiteboard. Each student can see the students in front of them. Now the teachers says, "I have 2 red hats and 3 white hats. I'm going to place a hat on each of your heads. You won't be able to see your own hat, but if you can deduce the color of your own hat, then say so." All the students are logical and smart. There is silence for a bit. Eventually the student in the front says, "I know what color my hat is!" What color is their hat?