Secret Santas II
Probability puzzles require you to weigh all the possibilities and pick the most likely outcome.
A group of ten friends decide to exchange gifts as secret Santas. Each person writes his or her name on a piece of paper and puts it in a hat. Then each person randomly draws a name from the hat to determine who has him as his or her secret Santa. The secret Santa then makes a gift for the person whose name he drew.
When it's time to exchange presents, each person walks over to the person he made the gift for and holds his or her left hand in his right hand.
What is the probability that the 10 friends holding hands form a single continuous circle?
HintIt's not as difficult as it seems.
It's the number of ways the friends can form a circle divided by the number of ways the names can be drawn out of the hat.
For a group of n friends, there are n! (n factorial) ways to draw the names out of the hat. Since a circle does not have a beginning and end, choose one person as the beginning and end of the circle. There are now (n-1)! ways to distribute the remaining people around the circle. Thus the probability of forming a single circle is
(n-1)! / n!
Since n! = (n-1)! * n (for n > 1), this can be rewritten as
(n-1)! / (n*(n-1)!)
Factoring out the (n-1)! from the numerator and denominator leaves
as the probability.
Jan 12, 2009
|I think I understand, but I'm not sure. Are you assuming that the person can't draw his/her own name? I wonder if you get the same answer by taking 1/9 + 1/8 + 1/7 + ...|
Jan 12, 2009
|Nevermind about that 1/9 + 1/8 + ... stuff. That wasn't well thought out. |
Mar 22, 2009
|Very nice, elegant probability problem. While it was fairly easy to solve, I liked the way it turned out to be unexpectedly easier than it first seemed.|
Jun 23, 2010
|Easy and nice|
Jun 30, 2011
|But what if the friends formed a triangle or a square or other polygon formations while holding hands instead? Wouldn't you have to calculate for the probability that they are actually forming a circle against other shapes while holding hands?|
Jul 28, 2013
|Am I confused or...is this incorrect?|
The way I see it, your calculations imply that one can be his own secret Santa, because you say there are n! ways to draw the names out of the hat. I believe it should be (n-1)! ways to draw the names out of the hat.
For example, with 2 people, there is only 1! (=1) order to draw the names out, without each being his own secret Santa. With 3 people, there are 2! (=2) ways, not 3! (=6) ways.
Here's how I did it:
Pick one person, designated A, who you already know is giving a gift to another, designated B. So far, this is 1/1 (100%) probability: you're merely setting aside one arbitrary, guaranteed transaction to begin with.
Now there are 9 who still need to receive (everyone but B) and 9 who still need to give (everyone but A). So, there are 9 possible people to receive the gift from B (anyone but himself), but to form the full circle, it has to be one of the other 8 people besides A. 8/9 probability for this to be true.
Assuming that the 8/9 chance is met (designating that third person as C), there are 8 left who need to receive (all but B and C). As long as C gives to one of the 7 who have not yet been involved, rather than the 8th option (A), then we are still good. That is a 7/8 probability. Now we are at (8*7)/(9*.
Continue in this exact way until we have: A -> B -> C -> D -> E -> F -> G -> H -> I. So now, the probability is (8*7*6*5*4*3*2)/(9*8*7*6*5*4*3). Now there are just two people who need to receive (A, and the 1 player not yet involved), and 2 who need to give (the 1 player not yet involved, and I). It would follow that (1/2) should be multipled for the final transactions, as we have successively subtracted 1 from the numerator and the denoimator to find the new factor with each step. HOWEVER, person I cannot give to person A, as this would complete a 9-man loop, leaving the 10th to give to himself, which is not allowed. So, person I can only give to the one who is not yet involved (designated J), leaving only one option, for J to give to A. So the last two transactions are 1/1 probability, having no effect on the overall probability.
SO...our final probability is (8*7*6*5*4*3*2)/(9*8*7*6*5*4*3). The factors 8, 7, 6, 5, 4, 3 are in the numerator and denominator, so they can all cancel out, leaving 2/9 = appx. 22.2%.
Sorry for the long explanation, but with length comes clarity!
Mar 09, 2015
| should be honest because this problem took me so long to answer. Nevertheless I got it right...|
I obtained a product which represents the answer, it was,
To my surprise, the diagonals cancel out and the product is simply 1/10.
Mar 09, 2015
|That smiley with shades on my last comment was a typo. That should have been 8.|
Mar 09, 2015
|eighsse: The problem as stated allows for a person to be their own secret santa. In this case, they hold their left hand in their right hand. A lamentably sad situation.|
I should have added the bonus question to ask what the probability is if a person is not allowed to be their own secret santa. I'll give you a hint: it's not 2/9.
I'll give the answer in my next comment. If you want to work it out for yourself, don't read it yet.
Mar 09, 2015
|If we add the restriction that someone is not allowed to be their own secret santa, then what are the odds of the friends forming a circle?|
The answer is similarly elegant to the original problem.
If anyone selects their own name, there are (n-1)! ways to select the remaining names. Since it doesn't matter who selects their own name, nor does it matter if more than one person selects their own name, there are (n-1)! cases where at least one person has selected their own name.
Plugging this into the original solution we get:
(n-1)! / (n! - (n-1)!)
= (n-1)! / (n*(n-1)! - (n-1)!)
= (n-1)! / ((n-1)*(n-1)!)
dividing enumerator and denominator by (n-1)! gives 1/(n-1) = 1/9.
Back to Top