Browse Teasers
Search Teasers

## Secret Santas I

Probability puzzles require you to weigh all the possibilities and pick the most likely outcome.

 Puzzle ID: #43847 Fun: (2.21) Difficulty: (2.93) Category: Probability Submitted By: javaguru

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 Next?

See another brain teaser just like this one...

Or, just get a random 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.

 tpg76 Jan 05, 2009 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. javaguru Jan 06, 2009 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. kp52 Jan 08, 2009 It was hard for me becuase I'm not good with math. krishnan Aug 20, 2010 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. masutra95 May 27, 2015 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. javaguru May 27, 2015 masutra, you are calculating the odds that a given individual draws their own name, not the odds that at least one person does. javaguru May 27, 2015 masutra, look at my long comment above to understand why your approach is wrong.