Brain Teasers Optical Illusions Puzzle Hunts Codes & Ciphers Mechanical Puzzles
Personal Links
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.19)
Difficulty:*** (2.94)
Submitted By:javaguru*us**




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.



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.
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.
Jan 08, 2009

It was hard for me becuase I'm not good with math.
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.
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.
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.
May 27, 2015

masutra, look at my long comment above to understand why your approach is wrong.

Back to Top

Online Now
6 users and 524 guests

Users In Chat
Follow Braingle!
Fold 'N Fly Paper Airplanes
Easy to follow folding instructions and videos.
Copyright © 1999-2017 | FAQ | Widgets | Links | Green | Subscribe | Contact | Privacy | Conditions | Advertise | Braingle Time: 2:16 am
Sign In Create a free account