2
$\begingroup$

There are 5 people in a party and there will be exchanging gifts.

Now, they conducted a lottery writing their names.

What is the probability that they will get the paper with their names?

Initial Analysis:

Suppose we fix the order of draw, say $P_1 , P_2, ..., P_5$ letting $P_1$ be the first person to draw.

If the question would be what is the probability of $P_1$ to get the paper with his name, then the answer would be $20$%.

What about $P_2$?

The probability depends on the outcome of $P_1$.

If $P_1$ got the paper except of $P_2$'s, then the probability is $25$%.

If $P_1$ got $P_2$'s name, then the probability will be $0$%.

I can't go any further.

It seems complicated to me or I am just complicating the problem.

  • 1
    Permutations where no element stays in position are called derangements: http://en.wikipedia.org/wiki/Derangement2011-12-22

1 Answers 1

3

The probability that the first person gets his own name is, as you say, $1/5$.

The same is true for each of the others:

It doesn't matter where a person comes in the order of drawing.

There are $5!=120$ possible orders in which the $5$ slips can be drawn. I claim that exactly one-fifth of those orders have $P_2$’s slip in the second position.

To see this, consider the $4!=24$ possible orders for the slips for $P_1,P_3,P_4$, and $P_5$.

You can insert $P_2$’s slip into one of these orders in $5$ possible places. For instance, starting with $P_3,P_1,P_5,P_4$ you can get any of these:

$\begin{align*} &\color{red}{P_2},P_3,P_1,P_5,P_4\\ &P_3,\color{red}{P_2},P_1,P_5,P_4\\ &P_3,P_1,\color{red}{P_2},P_5,P_4\\ &P_3,P_1,P_5,\color{red}{P_2},P_4\\ &P_3,P_1,P_5,P_4,\color{red}{P_2} \end{align*}$

Thus, each of the $24$ possible orders for the slips for $P_1,P_3,P_4$, and $P_5$ gives you one order of all five slips in which $P_2$’s slip is first, one in which it’s second, one in which it’s third, one in which it’s fourth, and one in which it’s last.

Consequently, $P_2$’s slip is equally likely to appear in any one of the five possible positions: for any position, there are $24$ orders in which it appears in that position.

In particular, it appears in the second position $24$ times out of $120$, or one time in five.

Similarly, $P_3$’s slip is equally likely to appear in each position, so the probability that it’s in the third position (so that $P_3$ gets it) is $1/5$, and $P_4$ and $P_5$ also have probability $1/5$ of drawing their own slips.

Added: The probability that at least one person gets his own slip is $1-\mathbb{P}(\text{no one gets his own slip})\;.$ Calculating the probability that no one gets his own slip is the classic problem of derangements.

It turns out that $44$ of the $120$ possible orders of drawing are derangements, i.e., orders in which no one gets his own slip, so the probability that you want is $\frac{120-44}{120}=\frac{76}{120}=\frac{19}{30}=0.63$

As the number of participants increases, the probability that at least one of them gets his own slip approaches $1-\frac1e\approx 0.63212\;.$

As you can see, the approximation is quite good already when $n=5$.

  • 1
    @Ken Dee: My guess is that whoever asked you the question was intending you to find the probability that at least one person gets his/her own name. So the person probably wanted you to find the number of non-derangements. But the person who posed the problem may not quite have stated it precisely enough. For $n=5$, you can find the answer with little theory, just careful listing. There are even a few shortcuts. For $n=6$ this already gets unpleasant, and by the time you hit $7$ or $8$, "general" theory becomes a practical necessity.2011-12-22