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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

$</code> ... <code>$</code>...<code>."> Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

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

Log in to reply

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

Log in to reply

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

Log in to reply

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.

Log in to reply

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

Log in to reply

Close, but not quite.

Log in to reply

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

Log in to reply