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 n1n-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 n = 2 , the probability is 0.
For n=3 n = 3 , the cases are 213,231,312 213, 231, 312 , and so the probability is 13 \frac{1}{3} .
As nn gets larger, the probability should be about 1n \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
4 years, 5 months ago

No vote yet
1 vote

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

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Here's Nathan's simplification of my approach:

Let ana_n represent the number of sequences where the first n1n-1 people don't get their gift, and the nth person gets his gift. This is the positive cases in our probability.
Let bnb_n represent the number of seqeuences where the first n1n-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 anan+bn \frac{ a_n}{a_n+b_n} .

Clearly, bnb_n represent a derangement on n objects, and so there are DnD_n of them.

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

Hence, the probability that we are after is Dn1Dn+Dn1 \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 ana_n ? This can be hard to count directly, so let's play around with it.
Given any sequence in ana_n , we can swap any of the first n1n-1 people with the nth person, and we clearly get a sequence in which no one gets their gift. This shows us that (n1)anbn (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 (n1)an (n-1) a_n into bn b_ n , but we don't know that we have hit all possible objects in bn b_n .

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

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

Given any sequence in ana_n, we can swap any of the first n1n-1 people, with the last, to get a sequence in bn b_n . However, given any sequence in bn b_n , we may not be able to reverse this procedure to get something in bn 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 n2n-2 people, and hence the number is Dn2 D_{n-2} . Multiplied by n1n-1 for any of the first n1n-1 people, we see that the cases that we are missing out on are (n1)Dn2 (n-1) D_{n-2} . Hence, an=Dn(n1)Dn2n1 a_n = \frac{ D_n - (n-1) D_{n-2} } { n-1 } .

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

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

Nathan Ramesh - 4 years, 5 months ago

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 1n \frac{1}{n} ), we didn't know what form it had to take.

I had a nice argument that an=dn(n1)dn2n1 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 dn1 d_{n-1} .

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

There are !n+!(n1)!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 !(n1)!(n-1) ways to order the names so the last person gets his own name.

Thus, the answer is !(n1)!n+!(n1)\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 - 4 years, 5 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. - 4 years, 5 months ago

Log in to reply

Close, but not quite.

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

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

Stewart S. - 4 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...