Brain Teasers
Secret Santas I
Probability
Probability puzzles require you to weigh all the possibilities and pick the most likely outcome.Probability
A group of about twenty friends decide to exchange gifts as secret Santas. Each person writes their name on a piece of paper and puts it in a hat and then each person randomly draws a name from the hat to determine who has them as their secret Santa.
What is the probability that at least one person draws their own name?
What is the probability that at least one person draws their own name?
Hint
The probability converges on a single value as the number of people approaches infinity. At ten people the probability is accurate to better than 1 millionth for any number more than ten people.Answer
1 - 1/eor approximately 0.63212
where e is the mathematical constant (e ~ 2.71828).
This comes from the number of derangements (permutations in which no element appears in its original position). There are n! ways to draw n names out of the hat. There are [n!/e + .5] derangements of n elements (where [x] is floor x--the integer portion of x). This gives:
[n!/e + .5] / n!
as the probability of nobody drawing their name.
Ignoring the .5 added for rounding (which becomes increasingly insignificant as n increases) this gives
(n!/e) / n!
= n!/e * (1/n!)
= 1/e
Subtract this from 1 to get the probability that somebody draws their own name.
Hide Hint Show Hint Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
OK, javaguru - I got the right answer for high n, but I got more than the stated deviation for the cases n=10 and n=20 (base case).
Here's how I approached it: for 20 to NOT draw their own name, the probability is (19/20)^20, or approx. 0.3585. The complementary probability of "at least one" would of course be 1-.3585 = .6415. More generally, p = 1 - [(n-1)/n]^n, which for large n, converges on the value you indicated. But by this method I do not get the "within a millionth" for moderate n, such as n=10 (or even somewhat higher). More precisely, I get for p(n): p(10) = .6513; p(20) = .6415; p(100) = .6340; p(10,000) = .6321. Do you agree? Or - what am I missing in my approach?
Thanks for another fun math teaser.
Here's how I approached it: for 20 to NOT draw their own name, the probability is (19/20)^20, or approx. 0.3585. The complementary probability of "at least one" would of course be 1-.3585 = .6415. More generally, p = 1 - [(n-1)/n]^n, which for large n, converges on the value you indicated. But by this method I do not get the "within a millionth" for moderate n, such as n=10 (or even somewhat higher). More precisely, I get for p(n): p(10) = .6513; p(20) = .6415; p(100) = .6340; p(10,000) = .6321. Do you agree? Or - what am I missing in my approach?
Thanks for another fun math teaser.
You can't use the "19/20" of not picking their name exponentially to get the true probability. It is an approximation that is quite poor at low n, but improves as n increases. The reason is because the piece of paper that is removed from the hat carries information--it must NOT be the name of the person who drew it. This information has to be accounted for when calculating the odds for the next person. Because you know that all the people drawing names before have not drawn their own name, the probability that the next person will draw their name is reduced because the probability that their name has already been drawn is increased.
This is easily demonstated at low values of n. With two people, the probability of each one drawing their own name is 50%, so the probability of not drawing their name is also 50%. (1/2)^2 is 1/4 or .25, but the actual probability is 1/2 because if the first person doesn't draw their own name, the second person can't either.
At three people (2/3)^3 is 8/27 or .296 but the actual probability is 1/3. (There are 3! = 6 permutations of ABC and only two--CAB and BCA--have none of the elements in their original position.) Instead of (2/3)^3 for not picking your own name the conditional probability is actually:
(2/3) for the first person (A) not picking their own name;
this leaves either AB or AC; this means that the second person to draw a name (B) has a
(1/2)*(1/2) + (1/2)*1 = 3/4
probability of not picking their name, which is greater than the 2/3;
for the last person if the first two have not picked their name then one of three cases has occurred:
A picked C and B picked A, leaving B
A picked B and B picked A, leaving C
A picked B and B picked C, leaving A
that leaves a 2/3 chance that the last person C won't pick a C.
(2/3)*(3/4)*(2/3) = 1/3
probability that none of them pick their own name.
As n increases, the impact of each person not picking their own name decreases, improving the approximation, but the error will always be much higher than the error introduced by eliminating the integer rounding in 1 - 1/e.
This is easily demonstated at low values of n. With two people, the probability of each one drawing their own name is 50%, so the probability of not drawing their name is also 50%. (1/2)^2 is 1/4 or .25, but the actual probability is 1/2 because if the first person doesn't draw their own name, the second person can't either.
At three people (2/3)^3 is 8/27 or .296 but the actual probability is 1/3. (There are 3! = 6 permutations of ABC and only two--CAB and BCA--have none of the elements in their original position.) Instead of (2/3)^3 for not picking your own name the conditional probability is actually:
(2/3) for the first person (A) not picking their own name;
this leaves either AB or AC; this means that the second person to draw a name (B) has a
(1/2)*(1/2) + (1/2)*1 = 3/4
probability of not picking their name, which is greater than the 2/3;
for the last person if the first two have not picked their name then one of three cases has occurred:
A picked C and B picked A, leaving B
A picked B and B picked A, leaving C
A picked B and B picked C, leaving A
that leaves a 2/3 chance that the last person C won't pick a C.
(2/3)*(3/4)*(2/3) = 1/3
probability that none of them pick their own name.
As n increases, the impact of each person not picking their own name decreases, improving the approximation, but the error will always be much higher than the error introduced by eliminating the integer rounding in 1 - 1/e.
It was hard for me becuase I'm not good with math.
The exact answer I got (for n people) is 1/1! - 1/2! + 1/3! - 1/4! ... 1/n! which converges to 1 - 1/e for large n.
Stated solution seems wrong.
First person has 19/20 chance not to pick own name, next person 18/19... 3/4 2/3 1/2. Multiply 1/20 or 1/n in general. So solution is 1-1/n = (n-1)/n, which is 19/20 or 95% for n=20.
First person has 19/20 chance not to pick own name, next person 18/19... 3/4 2/3 1/2. Multiply 1/20 or 1/n in general. So solution is 1-1/n = (n-1)/n, which is 19/20 or 95% for n=20.
masutra, you are calculating the odds that a given individual draws their own name, not the odds that at least one person does.
masutra, look at my long comment above to understand why your approach is wrong.
All of you are dropping hard facts and I'm just sitting here wondering how in the heck you came up with e for an answer
To post a comment, please create an account and sign in.
Follow Braingle!