Brain Teasers
Brain Teasers Trivia Mentalrobics Games Community
Personal Links
Submit a Teaser
Your Favorites
Your Watchlist
Browse Teasers
All

Cryptography
Group
Language
Letter-Equations
Logic
Logic-Grid
Math
Mystery
Optical-Illusions
Other
Probability
Rebus
Riddle
Science
Series
Situation
Trick
Trivia

Random
Daily Teasers
Search Teasers

Advanced Search
Add to Google Add to del.icio.us

More ways to get Braingle...

Secret Santas I

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

 

Puzzle ID:#43847
Fun:*** (2.23)
Difficulty:*** (2.96)
Category:Probability
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.

 



Comments

tpg76us**
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*us*
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.
kp52Aus*
Jan 08, 2009

It was hard for me becuase I'm not good with math.
krishnanAin*
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.



Back to Top
   



Users in Chat : Katherine24 

Online Now: 3 users and 420 guests

Copyright © 1999-2014 | Updates | FAQ | RSS | Widgets | Links | Green | Subscribe | Contact | Privacy | Conditions | Advertise

Custom Search





Sign In A Create a free account