THE WRONG HATS.
(
Combination and Group Problems)
"One of the most perplexing things I have come across lately," said Mr.
Wilson, "is this. Eight men had been dining not wisely but too well at a
certain London restaurant. They were the last to leave, but not one man
was in a condition to identify his own hat. Now, considering that they
took their hats at random, what are the chances that every man took a
hat that did not belong to him?"
"The first thing," said Mr. Waterson, "is to see in how many different
ways the eight hats could be taken."
"That is quite easy," Mr. Stubbs explained. "Multiply together the
numbers, 1, 2, 3, 4, 5, 6, 7, and 8. Let me see--half a minute--yes;
there are 40,320 different ways."
"Now all you've got to do is to see in how many of these cases no man
has his own hat," said Mr. Waterson.
"Thank you, I'm not taking any," said Mr. Packhurst. "I don't envy the
man who attempts the task of writing out all those forty-thousand-odd
cases and then picking out the ones he wants."
They all agreed that life is not long enough for that sort of amusement;
and as nobody saw any other way of getting at the answer, the matter was
postponed indefinitely. Can you solve the puzzle?
Answer:
The number of different ways in which eight persons, with eight hats,
can each take the wrong hat, is 14,833.
Here are the successive solutions for any number of persons from one to
eight:--
1 = 0
2 = 1
3 = 2
4 = 9
5 = 44
6 = 265
7 = 1,854
8 = 14,833
To get these numbers, multiply successively by 2, 3, 4, 5, etc. When the
multiplier is even, add 1; when odd, deduct 1. Thus, 3 x 1 - 1 = 2; 4 x
2 + 1 = 9; 5 x 9 - 1 = 44; and so on. Or you can multiply the sum of the
number of ways for n - 1 and n - 2 persons by n - 1, and so get the
solution for n persons. Thus, 4(2 + 9) = 44; 5(9 + 44) = 265; and so on.
Informational
