# Inspired by Edmund Zhou

Here is a question that my friend shared:

n people put their name in a hat.
Each person picks a name out of the hat to buy a gift for.
If any of the first $n-1$ people pick out themselves they put the name back into the hat.
What is the probability of the last person has his name in the hat?

Some observations.
For $n = 2$, the probability is 0.
For $n = 3$, the cases are $213, 231, 312$, and so the probability is $\frac{1}{3}$.
As $n$ gets larger, the probability should be about $\frac{1}{n}$, since any name "should" be equally likely. However, this is not a rigorous argument, and the probability could differ.

Note by Calvin Lin
6 years ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Here's Nathan's simplification of my approach:

Let $a_n$ represent the number of sequences where the first $n-1$ people don't get their gift, and the nth person gets his gift. This is the positive cases in our probability.
Let $b_n$ represent the number of seqeuences where the first $n-1$ people don't get their gift, and the nth person does not get his gift. This is the negative cases in our probability.

We seek the value of $\frac{ a_n}{a_n+b_n}$.

Clearly, $b_n$ represent a derangement on n objects, and so there are $D_n$ of them.

Clearly, $a_n$ represents a derangement on n-1 objects, so there are $D_{n-1}$ of them.

Hence, the probability that we are after is $\frac{ D_{n-1} } { D_n + D_{n-1} }$.

Here's my original convoluted approach:

How do we get a hold of the value of $a_n$? This can be hard to count directly, so let's play around with it.
Given any sequence in $a_n$, we can swap any of the first $n-1$ people with the nth person, and we clearly get a sequence in which no one gets their gift. This shows us that $(n-1) a_n \leq b_ n$. Why do we have a $\leq$ sign? This is because we have only given an injective mapping from $(n-1) a_n$ into $b_ n$, but we don't know that we have hit all possible objects in $b_n$.

How do we continue from here? We have $a_n \leq \frac{ D_n} { n-1 }$. Can we get the exact value?

We will show that $a_n = \frac{ D_n - (n-1) D_{n-2} } { n-1}$. Note that by the derangement recurrence relation, this is equal to $D_{n-1}$ as pointed out above.

Given any sequence in $a_n$, we can swap any of the first $n-1$ people, with the last, to get a sequence in $b_n$. However, given any sequence in $b_n$, we may not be able to reverse this procedure to get something in $b_n$ (IE this map is not surjective). The cases that we miss out, are exactly the ones where person n gets gift i, and person i gets gift n. In this case, swapping gifts results in person i getting gift i. For each person i, we have a derangement on the other $n-2$ people, and hence the number is $D_{n-2}$. Multiplied by $n-1$ for any of the first $n-1$ people, we see that the cases that we are missing out on are $(n-1) D_{n-2}$. Hence, $a_n = \frac{ D_n - (n-1) D_{n-2} } { n-1 }$.

Staff - 6 years ago

Why can't you just say that for $a_n$ one fixed person gets their gift and the other $n-1$ are deranged hence $a_n=D_{n-1}$?

- 6 years ago

Oh that's so true! How could I have missed that! This makes the argument much simpler. Thanks!!

The conversation that I was involved in got complicated quickly, with people running monte carlo simulations to attempt to arrive at the answer. However, because the probability wasn't something immediately recognizable, (i.e. not $\frac{1}{n}$ ), we didn't know what form it had to take.

I had a nice argument that $a_n = \frac{ d_n - (n-1) d_{n-2} } { n-1}$, but I forgot that by the recurrence relation that is exactly equal to $d_{n-1}$.

Staff - 6 years ago

There are $!n+!(n-1)$ ways to order the names, because they can either all have different peoples' names or the last person gets his own name. There are $!(n-1)$ ways to order the names so the last person gets his own name.

Thus, the answer is $\boxed{\dfrac{!(n-1)}{!n+!(n-1)}}$

It's funny, I proposed this problem on the Proofathon contest a while back. It didn't get chosen to be on the test, though. Interesting how a lot of people come up with the same ideas completely independently.

- 6 years ago

The probability would be d(n-1)/d(n) where d(n) represents the derrangement of n objects.

- 6 years ago

Close, but not quite.

Staff - 6 years ago

Ohh yeah i just noticed i forgot to add the derrangement of (n-1) objects to the total possibilities lol

- 6 years ago