2005 PMWC Problems/Problem I11

From AoPSWiki

Problem

There are 4 men: A, B, C and D. Each has a son. The four sons are asked to enter a dark room. Then A, B, C and D enter the dark room, and each of them walks out with just one child. If none of them comes out with his own son, in how many ways can this happen?

Solution

This is just a derangement problem (sending the set $\{1,2,3,4\}$ to another set such that none of the original elements are in the same place). The formula is:

$n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$

When $n = 4$ , we get:

$4! \left(\frac{1}{1} - \frac{1}{1} + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right) = 9$

2005 PMWC (Problems)
Preceded by Problem I10	Followed by Problem I12
I: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 T: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10

Personal tools

Navigation

Search

Toolbox

2005 PMWC Problems/Problem I11

From AoPSWiki

Problem

Solution

See also