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.

#Combinatorics

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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 }$ .

Calvin Lin Staff - 6 years, 5 months 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}$ ?

Nathan Ramesh - 6 years, 5 months 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}$ .

Calvin Lin Staff - 6 years, 5 months 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.

Daniel Liu - 6 years, 5 months ago

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

Stewart S. - 6 years, 5 months ago

Close, but not quite.

Calvin Lin Staff - 6 years, 5 months ago

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

Stewart S. - 6 years, 5 months ago

Math	Appears 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}$