## Poll

1 vote (14.28%) | |||

1 vote (14.28%) | |||

No votes (0%) | |||

3 votes (42.85%) | |||

3 votes (42.85%) | |||

1 vote (14.28%) | |||

2 votes (28.57%) | |||

No votes (0%) | |||

No votes (0%) | |||

3 votes (42.85%) |

**7 members have voted**

The question is, how many closed loops will there be, on average? For example of a closed loop, Gordon gives to Don, who gives to Jon, who gives to Nathan, who gives to Gordon. Or drawing your own name.

For extra credit, what is an expression of the answer, or a very close estimate, for large numbers of workers, n, as a function of n.

I would like to request that anyone who has won a beer in the last year not submit an answer for 24 hours. You may still explain to others why their answers are wrong or generally help out.

Quote:mipletIf you do it the right way, just 1. https://youtu.be/GhnCj7Fvqt0 .

Darn. That was going to be my answer. Really well explained there, though. We used to do it that way. So I can't really take credit for figuring it out myself anyway.

Hint: There is a very intuitive way to solve this problem that requires no advanced math, although a spreadsheet would be helpful.

In order to analyze this process, make the guests draw in a particular order following these two rules. The ordering should be without loss of generality (*hands wave*). On drawing i: Rule 1: If Person P was on the card drawn, but has not picked a card already, P draws next. Rule 2: If the card had P who was picked before, a uniformly random person who has not selected a card goes next. Note that the person picked in Rule 2 must be at the back of the last loop, as everyone else in the loop has already been picked, and the random person starts a new loop. So, cases where Rule 2 apply are the only times our number of loops increases (by one) (we would formally track this by a random variable). We can calculate the probability of Rule 2 occurring. Since there's only one person at the back of the loop, it's 1 out of the remaining people = 1/(n-i+1). So, we have a sum from 1/n to 1. This makes sense as the first person has 1/n chance of picking himself, and the last person is guaranteed to complete a loop (since everyone else has already been picked before).

So, the answer for 100 should be the 100th harmonic number, and the answer for n should be the nth harmonic number which is on the order of logarithmic.

All of the above could be further formalized, but I think it is a good first pass?

EDIT: changed "chain" to "number of loops"

What if the 100'th person picks their own name?

Do-over in both cases, I assume?

Almost certainly wrong, but yolo. 5.16

Quote:WizardThere are no do-overs. Everybody picks a random name. I'm not looking for a better way to do a Secret Santa, although that is a worthy discussion.

So someone can pick their own name, is that correct (according to this math problem)?

Edit: Nevermind I’m retarded. I never learned to read. Thanks djtech

Quote:RSSo someone can pick their own name, is that correct (according to this math problem)?

Yes, that's in the problem statement:

Quote:Wizard... Or drawing your own name...

E(1) = 1 and

E(N) = (N + E(N) + E(N-1) + . . . + E(1))/N

After playing around with it for awhile I noticed it was the harmonic function.

So E(100) = 1 + 1/2 + 1/3 + . . . + 1/100

And E(N) for a large enough N is approximated by ln(N) plus Euler’s constant. (I googled last bit as I couldn’t recall it.)

Quote:WizardunJon has the right answer, but I'd prefer to see an explanation for why it is right. The explanation is very intuitive.

Order the pickers where #1 goes first, if he picks himself, you’ve just reduced it to an N-1 game plus 1 loop (of #1 picking himself). If #1 picks someone else, then that person goes next and has an N-1 chance of picking #1, which reduces it to an N-2 game plus 1 loop (of #1 to second picker). So it nests all the way down to smaller games.

This is the same as saying that a game of N players is the same as a game of N-1 players plus the 1/N chance of the first person picking himself.

Since a 1 player game always has one loop, a two player game has 1 + 1/2 loops and a 3 player game has that plus 1/3, etc.

Quote:netzerThere are several Secret Santa problems, but I managed to find a published scholarly paper on this particular one. It is The Secret Santa Problem by Michael J. Reske in the Pi Mu Epsilon Journal v. 10 No. 1 (1994) I have this volume and would be glad to send it as an ordinary e-mail attachment. In my opinion unJon's solution is much simpler than Reske's and could be a significant contribution to the theory of the problem.

Thanks, netzer. Though now Crystalmath will think I’m one of your socks. :-)

Quote:unJonThanks, netzer. Though now Crystalmath will think I’m one of your socks. :-)

Don't worry about that! He's been very nice to me and went to considerable trouble to check my algebra in the Biased Coin Problem. If you want the paper just send me your e-mail address in a private message and it's on it's way. That goes for CrystalMath too!

I would like to know more about you. I took my degree at Cambridge and teach Physics at the Durban University of Technology. One of my greatest experiences was reading the original papers of Sir Isaac Newton, which recently have been translated into English. Albert Einstein read them too but belittled them. Nevertheless, Newtonian physics still is accurate if you don't approach the speed of light.

Let E(n) be the expected number of "loops" in a group of n people

1/n of the time, the first person will choose himself, forming a 1-person loop; this is 1/n x (1 + E(n-1))

(n-1)/n x 1/(n-1) = 1/n of the time, the first person will choose, say, P2, and P2 chooses the first person;, forming a 2-person loop; this is 1/n x (1 + E(n-2))

(n-1)/n x (n-2)/(n-1) x 1/(n-2) = 1/n of the time, the first person will choose P2, P2 chooses P3, and P3 chooses the first person;, forming a 3-person loop; this is 1/n x (1 + E(n-3))

And so on

The total is 1/n x ((1 + E(n-1)) + (1 + E(n-2)) + (1 + E(n-3)) + ... + (1 + E(2)) + (1 + E(1)) + (1 + E(0))), where E(0) is zero

E(n) = 1/n x ((1 + E(n-1)) + (1 + E(n-2)) + (1 + E(n-3)) + ... + (1 + E(2)) + (1 + E(1)) + (1 + E(0)))

= 1/n x (1 + E(n-1)) + (n-1)/n x 1/(n-1) x ((1 + E(n-2)) + (1 + E(n-3)) + ... + (1 + E(2)) + (1 + E(1)) + (1 + E(0)))

= 1/n + E(n-1) / n + (n-1)/n x E(n-1)

= 1/n + E(n-1)

Thus, the value is recursive; E(100) = 1/100 + E(99) = 1/100 + 1/99 + E(98) = 1/100 + 1/99 + 1/98 + E(97) = ...

= 1/100 + 1/99 + 1/98 + ... + 1/3 + 1/2 + E(1)

E(1) = 1, since there is always one loop in a set of one person

The answer is 1 + 1/2 + 1/3 + ... + 1/99 + 1/100, or about 5.18738.

Quote:unJonI’m not sure it’s intuitive, but here’s how I got there...

Suppose there are n people and look at the first one A.

(i) If A has picked himself then the answer is 1 + f(n-1); as has been explained the chance of this is 1/n.

(ii) If A has picked someone else, then let that person be B and, as above, put them as the second person; the chance of this is (n-1)/n.

The loop that starts with A B ... ... eventually finishes when someone picks A. It also means noone else in this layout can pick B, but someone somewhere has picked A.

Now consider the situation of the remaining (n-1) people (i.e. excluding A) but whoever picked A above now picks B instead. This layout forms the same number of loops as the one above. The loop that includes B is the same except above it goes A B ... and here it goes B ... . All the other loops are identical.

Therefore the expected number of loops once it is known that A picks B, is the same as for (n-1) people, i.e. f(n-1).

Thus f(n) = the sum of the above = 1/n * ( 1+f(n-1) ) + (n-1)/n * f(n-1) = 1/n + f(n-1).

As f(1)=1, f(n)=1+1/2+1/3....+1/n.

Suppose there is just one employee who comes to the Secret Santa party. Obviously he will pick himself, so one closed loop.

Then a second employee arrives late and asks to join. They give her a list of the now two employees. There is a 1/2 chance she picks employee 1 and 1/2 herself. If she picks employee 1, then she can be squeezed into his loop, where she buys for employee 1 and he buys for her. So, now we're at 1 + 0.5*1 = 1.5

Then a third employee arrives late and asks to join. They give her a list of the now 3 employees. There is a 2/3 chance she picks employee 1 or 2 and 1/3 herself. If she picks employee 1 or 2, then she can be squeezed into their loop, where she buys for employee she picks and the one who formally was supposed to buy for that employee now buys for 3. So, now we're at 1.5 + (1/3) = 11/6.

Then a fourth employee arrives late and asks to join. They give her a list of the now 4 employees. There is a 3/4 chance she picks employee 1 to 3 and 1/4 herself. If she picks employee 1 to 3, then she can be squeezed into their loop, where she buys for employee she picks and the one who formally was supposed to buy for that employee now buys for 4. So, now we're at 11/6 + (1/4) = 25/12.

Keep doing this and the final answer is 1/1 + 1/2 + 1/3 + ... + 1/100 =~ 5.187377518.

Suppose you have 100 shoelaces. They are all in a box with only the ends protruding. You tie the ends to each other randomly. When you're done, how many closed loops will there be?

To convert this to the Secret Santa problem, if there are 20 people in the exchange, what is the probability any given number from 0 to 20 (except 19) draw their own prize?

I haven't thought about this for a while. Can anyone who recalls the method of the calculating the answer better than I provide the combinations? Otherwise, I'll go with estimates using the Poisson distribution, which I'm sure are very close. However, it's always so unsatisfying to go with estimates.

It's obvious with 1 Santa there is a 100% chance at a match.

With 2 Santas, there is a 50/50 chance of 0 and 2 matches.

3 Santas

With 3, or any number, there is always 1 way that everybody matches.

There are always 0 ways to have s-1 matches with s Santas. This is because if the s-1 people match, the last person has only his name left, so he must match too. So, 0 ways to have 2 matches.

For one match, there are 3 Santas that can be that one match. Then there is 1 way the other two people can be assigned each other. So 3*1 = 3 ways to have one match.

For zero matches, there are 6! - 1 - 3 = 2 ways. I will get to a more logical formula later in this post.

4 Santas

As always, there is one way everybody (4) matches.

By the logic for 3 Santas, it's impossible to have 3 matches with 4 Santas, so 0 combinations.

For 2 matches, there are combin(4,2)=6 ways to choose the two matching Santas out of four. Then there is one way the other two do not match (from 2 Santas). So 6 ways 2 match.

For 1 match, there are 4 ways to choose the one Santa who does match. We saw from 3 Santas there are 2 ways the other 3 Santas do not match. So 4*2=8 ways there is one match.

Out of 4!=24 possible orders, the number of combinations for zero matches is 24-1-6-8=9 ways zero match.

5 Santas

As always, there is one way everybody (5) matches.

By the logic for 3 Santas, it's impossible to have 4 matches with 5 Santas, so 0 combinations for 4 matches.

For 3 matches, there are combin(5,3)=10 ways to choose the 3 matching Santas out of 5. Then there is one way the other two do not match (from 2 Santas). So 10 ways 2 match.

For 2 matches, there are combin(5,3)=10 ways to choose the 2 matching Santas out of 5. Then there are 2 ways the other two do not match (from 3 Santas). So 10*2=20 ways 2 match out of 5.

For 1 match, there are 5 ways to choose the one Santa who does match. We saw from 4 Santas there are 9 ways the other 5 Santas do not match. So 5*9=45 ways there is one match.

Out of 5!=120 possible orders, the number of combinations for zero matches is 120-1-10-20-45=44 ways zero match zero.

Just keep following this logic.

The following table shows the combinations up to 10 Santas.

Matches | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
---|---|---|---|---|---|---|---|---|---|---|

10 | 1 | |||||||||

9 | 0 | 1 | ||||||||

8 | 45 | 0 | 1 | |||||||

7 | 240 | 36 | 0 | 1 | ||||||

6 | 1890 | 168 | 28 | 0 | 1 | |||||

5 | 11088 | 1134 | 112 | 21 | 0 | 1 | ||||

4 | 55650 | 5544 | 630 | 70 | 15 | 0 | 1 | |||

3 | 222480 | 22260 | 2464 | 315 | 40 | 10 | 0 | 1 | ||

2 | 667485 | 66744 | 7420 | 924 | 135 | 20 | 6 | 0 | 1 | |

1 | 1334960 | 133497 | 14832 | 1855 | 264 | 45 | 8 | 3 | 0 | 1 |

0 | 1334961 | 133496 | 14833 | 1854 | 265 | 44 | 9 | 2 | 1 | 0 |

Total | 3628800 | 362880 | 40320 | 5040 | 720 | 120 | 24 | 6 | 2 | 1 |

Notice how the combinations for zero matches are always one more or less than for one match. It's one more for an even number of Santas and one less for odd. Very interesting!

You can use that formula for the case of zero matches, although I know it is so unsatisfying when you can't prove why it works, other than observing that it always does.

I may write later on my logic in C++ to count use a looping program to do this the hard way, if there is any interest.

Hours of work went this this post, which will probably explain why it gets no replies.

n!*(1/2! - 1/3! + 1/4! - 1/5! + ... ) alternating + and - up to 1/n!.

Questions on notation:

1. Where is factorial in the order of operations? Do you think it's clear in this case to do the factorial before division?

2. How should I express this formula. I'm unsure of the notation when the signs alternate and it's unclear if the last operation is + or -. By the way, the last operation is positive if n is even and negative if odd.

No extra parenthesis should be necessary.