Plane teasers

The magazine on my flight to Vegas had a brain teaser section with the instructions "See if you can solve these problems in five minutes or less!"

Here was the first problem:
"Twelve balls are identical in all ways except one has a different weight than the others, which all have the same weight. Three weighings on a balance scale will not only identify the odd ball, but also tell whether it is heavier or lighter. How many balls must be put on the scale in the first weighing?"

It seemed pretty obvious that you need to put four balls on each side (the correct answer), but when I tried a few obvious algorithms for identifying the odd ball (and telling if it's lighter or heavier), none of them worked. For example, you can try weighing the first four balls against the next four: if they are equal then you can weigh 2 of the remaining balls against each other. But you can't solve the problem in one more weighing ... It quickly became clear that either the solution was pretty complicated, or more than 3 weighings were needed.

It turns out that you can actually solve the problem with three weighings. Obviously I would've solved it if I weren't so busy :), but a little googling gave me the following solution:

"I have lifted this practically verbatim from the book "Games for the Super-
intelligent" by the late Jim Fixx. (I would never have figured this out.)
Number the balls 1 to 12. Weigh 1, 2, 3, and 4 against 5, 6, 7, and 8.
If (1, 2, 3, 4) and (5, 6, 7, 8) balance:
Weigh 9 and 10 against 11 and 8 (we know 8 is not the odd ball).
If (9, 10) and (11, 8) balance: then 12 is the odd one.

Weigh 12 against any other to find out if it is heavy or light.

If (9, 10) and (11, 8) do not balance: suppose 11 and 8 are heavier,
than 9 and 10; then either 11 is heavy, or 9 is light, or 10 is light.

Weigh 9 against 10; if they balance, 11 is heavy; if they do not,
the lighter of 9 and 10 is the odd ball.

(Similar argument if 11 and 8 are lighter than 9 and 10).

If (1, 2, 3, 4) and (5, 6, 7, 8) do not balance:
Suppose 5, 6, 7, and 8 are heavier than 1, 2, 3, & 4. Then: one of
(1, 2, 3, or 4) is light, or else one of (5, 6, 7, or 8) is heavy.
Weigh 1, 2, and 5 against 3, 6, and 9.
If they balance: then either 7 is heavy, or 8 is heavy, or 4 is light.
Weigh 7 against 8; if they balance, 4 is the odd ball, otherwise the
heavier of 7 and 8 is the odd ball.

If (1, 2, 5) and (3, 6, 9) do not balance: suppose 1, 2, and 5 are lighter
than 3, 6, and 9; then either 6 is heavy, or 1 is light, or 2 is light.
Weigh 1 against 2 to find out which one of the three choices is true.
Otherwise, suppose 1, 2, and 5 are heavier than 3, 6, and 9; then either 3
is light, or 5 is heavy.

Weigh 3 against (say) 2 to find out which of the two choices is true.

(Similar argument if 1, 2, and 5 are lighter than 3, 6, and 9)."

I found it kind of funny that this problem was actually pretty tough, given how silly the other two problems were:

2) Is it possible for a man in St. Louis to marry his widow's sister?

3) Out of 3 females and 3 males, 3 people at random enter an empty room. What is the probability that there are two males and one female in the room now?