Waste less time on Facebook — follow Brilliant.
×

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
2 years, 3 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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 · 2 years, 3 months ago

Log in to reply

@Calvin Lin 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 · 2 years, 3 months ago

Log in to reply

@Nathan Ramesh 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 · 2 years, 3 months ago

Log in to reply

The probability would be d(n-1)/d(n) where d(n) represents the derrangement of n objects. Stewart S. · 2 years, 3 months ago

Log in to reply

@Stewart S. Close, but not quite. Calvin Lin Staff · 2 years, 2 months ago

Log in to reply

@Calvin Lin Ohh yeah i just noticed i forgot to add the derrangement of (n-1) objects to the total possibilities lol Stewart S. · 2 years, 2 months ago

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. Daniel Liu · 2 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...