## Name picking

Posted by Chris on July 16, 2013 – 8:57 pm

Here’s a couple of picking problems.

1. If ten people randomly select their names from a hat, what is the probability that the last one will pick his own name?

2. If ten people randomly select their names from a hat, what is the probability that only the last one will pick his own name?

July 17th, 2013 at 6:15 am

1. 10%

2. 3.68%

July 17th, 2013 at 7:47 am

For #1:

There are 10! (ten factorial) ways of the people selecting their names. If we know the last person gets their own name, there are 9! ways the rest could have picked.

9!/10! = [9*8*7*6*5*4*3*2*1]/[10*9*8*7*6*5*4*3*2*1] = 1/10 = 10%

This is also the probability that people 1-9 did NOT pick #10’s name. This may prove useful for the second question.

For #2:

There are still 10! (that’s 3 628 800) ways of picking names from the hat. We need to know the probability of ONLY the last person picking their own name. This is equivalent to the probability of people 1-9 NOT picking #10’s name (see above) AND NOT picking their own name.

I won’t spell out the details of my calculations at this point, because I’m not so sure I have it correct. I came up with a 2.083333% chance of ONLY person #10 picking their own name.

~~~~~~~~~~~~

Later: I am confident that my calculations were off, but I fear they are even less correct this time around. I now come up with a 1.8889% chance…July 17th, 2013 at 3:41 pm

Hi DP. As you suspected, your calcs (for part 2) are wrong. Jan got it right.

The core maths (for part 2) has been mentioned in quite a few problems on this site – it’s about derangements.

No matter how many times or how many ways that I prove (to myself) that you’ll get the same answer regardless of which of the ten is the special one, my intuition still rebels against it. It’s very strange.

July 18th, 2013 at 7:38 am

Ok, I think I am a little closer (in process, not value).

As I said before, we need to find out the probability of no one picking the last person’s name AND not picking their own name. In other words, ONLY ONE person gets to pick their own name (as stated in the problem). I first tried to use the inclusion-exclusion by brute force to look for the patterns, but it’s a little mind numbing going that route. There are a few functions we are able to use to get us to the correct answer.

let

g(n) = n*g(n-1) + (-1)^n, whereg(1)=0. You can also useg(n) = n!/e (round to nearest digit) for a spot-check.Solutions up to

g(10):g(1)=0 =>g(2)=1,g(3)=2,g(4)=9,g(5)=44,g(6)=265,g(7)=1854,g(8)=14833,g(9)=133496, andg(10)=1334961.Let

f(n,m) = C(n,m)*g(n-m)And C(n,m) = n!/[(n-m)!*m!]

Where n=number of people, and m=number of correct names drawn

We are looking for

f(10,1) = 10!/[(10-1)!*1!] * g(10-1)= 10!/9! * g(9) = 10 * 133496 = 1334960.

Divide this by the total possibilities: 1334960/10! = 1334960 / 3628800

= 36.8% ….which is off by a factor of 10…perhaps this is a case where you don’t use C(n,m) ? I still don’t have a complete grasp of the concept.

July 18th, 2013 at 5:06 pm

Hi DP. You’re right – this is a case where you don’t use C(n,m).

July 19th, 2013 at 11:51 am

I’ll close this one. Let d(n) be the number of ways that n people fail to pick their own name. It turns out that for n :ge; 6 (say), that as near as heck, d(n) = n!/e ≈ 0.368 n!. As there are n! possible ways of picking the names, the probability of no-one picking their own name is 0.368.

If exactly one particular person (out of n people) picks his own name, then the number of ways that the remaining n-1 people fail to pick their own name is d(n-1) and for n sufficiently large, d(n-1) ≈ (n-1)! / e and the probability of that ≈ 0.368 also. There are n possible choices for the particular person, so the probability of it being a given one of them is 1/n – in particular, the probability of the last person picking his own name is 1/n. So the probability that only the last person picks his own name is d(n-1)/(n-1)! * (1/n) ≈ 0.368 / n.

In the posted problem n = 10, so we get the result 0.368/10 = 0.0368 = 3.68%

July 19th, 2013 at 11:55 am

If exactly a particular m of the n people pick their own name, then the number of ways that the remaining n-m people fail to pick their own name is d(n-m). There are C(n,m) ways of selecting m people from n, and so the number of ways that exactly m people pick their own name is C(n,m) d(n-m)

July 19th, 2013 at 1:53 pm

Which is what I did….only I forgot the part where: when m=1 each person has a 1/n chance of being that 1. So my solution should have been

f(n,m) = C(n,m)*g(n-m)/n which would result in only person #10 picking their own name with a 3.68% chance.