[Prof. Templeton]

Dave walked into Sue’s office. “So, I’ve collected all the secret Santa gifts for the office party, how do you plan on distributing them?”, he asked.

Sue replied, “We’ll just have every one of the nine people in the office reach in randomly and take a gift. Simple.”

“Um, won’t there be a chance that someone will get their original gift? I mean they all look about the same size and everyone used the same wrapping paper that was in the break-room. You can’t tell one gift from another.”

“Come on, Dave. I think there is a high probability that no one will receive their original gift”

What is the probability that no one receives their own gift?

A little while later Dave came back into Sue’s office. “The two guys from the mail-room want to come to the party also. They heard about the secret Santa thing, so they wrapped their gifts and I took them and put them with all the others. Now there are eleven gifts that all look the same. Does that change the probability of someone not getting their own gift?

What is the probability that no one receives their own gift now that two additional people are added?

[Guest]

1/9

1/11

[Guest]

Now there are eleven gifts that all look the same. Does that change the probability of someone not getting their own gift?

yes. But not by very much.

[Prof. Templeton]

1/11

1/9

The actual chance of someone not getting their own is a bit higher then those.

yes. But not by very much.

Quite true.

[Guest]

The probability that someone will receive their own gift is P(A)=1/9=11%

The probability that this will not happen (as the question asks) is 1-P(A)=89%

However since each person has an 11% chance to pick their own gift, the probability that no one will get their own gift is a joint probability like:

P(Z)=(1-0.11)^9=0.35

35% chance that no one will receive their own gift.

..and I'm not sure enough about that to bother doing the math for the second part ;-)

can't wait to find out the correct answer.

Edited February 24, 2009 by mpapineau

[Pickett]

So, the way I see it:

The first guy to pick a present has a 9/9 chance that his has NOT been picked yet, and a 1/9 chance that he will pick his (if it hasn't already been picked).

The second guy has an 8/9 chance that his has NOT been picked yet, and a 1/8 chance that he will pick his (if it hasn't already been picked).

The third guy has a 7/9 chance that his has NOT been picked yet, and a 1/7 chance that he will pick his (if it hasn't already been picked...

...etc...

So, it seems (although I MUST be doing something wrong) that the chances of a person to pick their own would be the probability that theres hasn't been picked times the probability that they will pick theirs if it hasn't...

So for guy

#1: (9/9) * (1/9) = 1/9

#2: (8/9) * (1/8) = 1/9

#3: (7/9) * (1/7) = 1/9

...

#9: (1/9) * (1/1) = 1/9

And so then the total probability that at least one person would pick their own would be the sum of all of their probabilities which is 1/9 * 9 = 1...so it seems like there is a 100% probability that at least one person would pick their own gift...but that seems wrong to me, because I can definitely think of scenarios where no one gets theirs...hmmm...I must have missed something...

Using that answer, the probability would not change if there were 11 gifts (probability would still be 1)

[Guest]

So, the way I see it:

The first guy to pick a present has a 9/9 chance that his has NOT been picked yet, and a 1/9 chance that he will pick his (if it hasn't already been picked).

The second guy has an 8/9 chance that his has NOT been picked yet, and a 1/8 chance that he will pick his (if it hasn't already been picked).

The third guy has a 7/9 chance that his has NOT been picked yet, and a 1/7 chance that he will pick his (if it hasn't already been picked...

...etc...

So, it seems (although I MUST be doing something wrong) that the chances of a person to pick their own would be the probability that theres hasn't been picked times the probability that they will pick theirs if it hasn't...

So for guy

#1: (9/9) * (1/9) = 1/9

#2: (8/9) * (1/8) = 1/9

#3: (7/9) * (1/7) = 1/9

...

#9: (1/9) * (1/1) = 1/9

And so then the total probability that at least one person would pick their own would be the sum of all of their probabilities which is 1/9 * 9 = 1...so it seems like there is a 100% probability that at least one person would pick their own gift...but that seems wrong to me, because I can definitely think of scenarios where no one gets theirs...hmmm...I must have missed something...

Using that answer, the probability would not change if there were 11 gifts (probability would still be 1)

You don't add up the probabilities.

Great justification for why each individual choice is 1/9. That means that each person has an 8/9 chance that they will NOT pick their own. What is the chance that all of them will not pick their own? Multiply, don't add: (8/9)^9= about 34.6% that no one will pick their own. (pretty slim)

With 11 presents, it becomes (10/11)^11 = 35.0%

[Guest]

How about the odds that everyone picks the gift they submitted?

Edited February 24, 2009 by Theonexus

[Guest]

So, the way I see it:

The first guy to pick a present has a 9/9 chance that his has NOT been picked yet, and a 1/9 chance that he will pick his (if it hasn't already been picked).

The second guy has an 8/9 chance that his has NOT been picked yet, and a 1/8 chance that he will pick his (if it hasn't already been picked).

The third guy has a 7/9 chance that his has NOT been picked yet, and a 1/7 chance that he will pick his (if it hasn't already been picked...

...etc...

So, it seems (although I MUST be doing something wrong) that the chances of a person to pick their own would be the probability that theres hasn't been picked times the probability that they will pick theirs if it hasn't...

So for guy

#1: (9/9) * (1/9) = 1/9

#2: (8/9) * (1/8) = 1/9

#3: (7/9) * (1/7) = 1/9

...

#9: (1/9) * (1/1) = 1/9

And so then the total probability that at least one person would pick their own would be the sum of all of their probabilities which is 1/9 * 9 = 1...so it seems like there is a 100% probability that at least one person would pick their own gift...but that seems wrong to me, because I can definitely think of scenarios where no one gets theirs...hmmm...I must have missed something...

Using that answer, the probability would not change if there were 11 gifts (probability would still be 1)

That's close, each person has a 1/n chance, where n is the amount of people in the pool, to pick their own gift. However, they are not directly cumulative.

0 + (1/9 * 1 ) = 1/9

1/9 + (1/9 * 8/9) = 17/81

17/81 + (1/9 * 7/9) = 24/81

24/81 + (1/9 * 6/9) = 30/81

30/81 + (1/9 * 5/9) = 35/81

35/81 + (1/9 * 4/9) = 39/81

39/81 + (1/9 * 3/9) = 42/81

42/81 + (1/9 * 2/9) = 44/81

44/81 + (1/9 * 1/9) = 45/81 <-- 36/81 or 44.44% nobody picks their own.

Here is the formula to calculate the chance that someone DOES pick their own:

f(n,m) = IF m > 0 THEN (1/n * m/n) + f(n,m-1) ELSE 0

In these cases the answers are:

1 - f(9, 9)

1 - f(11, 11)

The initial values of n and m being the amount of participants.

Inversely, the function to find the chance that someone DOES NOT pick their own is much simpler:

f(n) = ((n-1)/n)^n

Edited February 24, 2009 by Llam4

[Guest]

How about the odds that everyone picks the gift they submitted?

(1/9)*(1/8)*(1/7)*(1/6)*(1/5)*(1/4)*(1/3)*(1/2)*(1/1)= 0.00002756%

[Guest]

(1/9)*(1/8)*(1/7)*(1/6)*(1/5)*(1/4)*(1/3)*(1/2)*(1/1)= 0.00002756%

Thats what I came up with -about 3 in a million

[Guest]

That's close, each person has a 1/n chance, where n is the amount of people in the pool, to pick their own gift. However, they are not directly cumulative.

0 + (1/9 * 1 ) = 1/9

1/9 + (1/9 * 8/9) = 17/81

17/81 + (1/9 * 7/9) = 24/81

24/81 + (1/9 * 6/9) = 30/81

30/81 + (1/9 * 5/9) = 35/81

35/81 + (1/9 * 4/9) = 39/81

39/81 + (1/9 * 3/9) = 42/81

42/81 + (1/9 * 2/9) = 44/81

44/81 + (1/9 * 1/9) = 45/81 <-- 36/81 or 44.44% nobody picks their own.

Here is the formula to calculate the chance that someone DOES pick their own:

f(n,m) = IF m > 0 THEN (1/n * m/n) + f(n,m-1) ELSE 0

In these cases the answers are:

1 - f(9, 9)

1 - f(11, 11)

The initial values of n and m being the amount of participants.

Inversely, the function to find the chance that someone DOES NOT pick their own is much simpler:

f(n) = ((n-1)/n)^n

My original function is wrong. Where I'm multiplying by 9/9, 8/9, 7/9, 6/9, etc I should be multiplying by one minus the current total.

[Guest]

Voltage and Theonexus

You are the only participant and you have a choice of 1 in 9 presents. One is yours. There is a 1/9 chance that you will pick your own.

Now you have one friend, who will also choose a present. Does the probability that one of you will choose one of the presents you donated go up, or down?

The answer is quite obviously up. You now have two chances for a person to choose their own present.

Multiplying 1/9 * 1/8 * 1/7 * 1/6 * 1/5 * 1/4 * 1/3 * 1/2 would mean the probability goes down.

I believe the answer you're finding is the chance that EVERYBODY picks their own present.

[Pickett]

Alright, so, I solved this one the way I solve almost any problem now...I just wrote a program to do it...

Here are the results:

If there are 9 people/presents, then there is a 36.79% chance that no one will get one of their own presents...and if there are 11, then there is a 40.13% chance that no one will get one of their own presents...here's a break down of n = 1 through 11:

1: 0/1 = 0%

2: 1/2 = 50%

3: 2 / 6 = 33.33%

4: 9 / 24 = 37.5%

5: 44 / 120 = 36.67%

6: 265 / 720 = 36.81%

7: 1854 / 5040 = 36.79%

8: 14833 / 40320 = 36.79%

9: 133496 / 362880 = 36.79%

10: 1468457 / 3628800 = 40.47%

11: 16019531 / 39916800 = 40.13%

Basically the program just gets all permutations possible (that's the denominator, and then checks all of them to find any that don't have any of the original values in the original positions (aka...gifts to the person who gave them)...and that's the numerator...so any that don't have any of the original, are valid, divide by the number of possible, and you get the percent chance that no one will get their own gift...

[Guest]

Voltage and Theonexus

I believe the answer you're finding is the chance that EVERYBODY picks their own present.

Yes we are! see here:

How about the odds that everyone picks the gift they submitted?

[Guest]

OK, probability is one of my weakest areas and I started figuring wrong at first

1/9^9 = 1/387420489 or a little better than one in 400million chance

(8/9)^9 or about 34.6% chance

(10/11)^11 or about 35% chance, so not much change from the original 9 person pool.

[Prof. Templeton]

Alright, so, I solved this one the way I solve almost any problem now...I just wrote a program to do it...

Here are the results:

If there are 9 people/presents, then there is a 36.79% chance that no one will get one of their own presents...and if there are 11, then there is a 40.13% chance that no one will get one of their own presents...here's a break down of n = 1 through 11:

1: 0/1 = 0%

2: 1/2 = 50%

3: 2 / 6 = 33.33%

4: 9 / 24 = 37.5%

5: 44 / 120 = 36.67%

6: 265 / 720 = 36.81%

7: 1854 / 5040 = 36.79%

8: 14833 / 40320 = 36.79%

9: 133496 / 362880 = 36.79%

10: 1468457 / 3628800 = 40.47%

11: 16019531 / 39916800 = 40.13%

Basically the program just gets all permutations possible (that's the denominator, and then checks all of them to find any that don't have any of the original values in the original positions (aka...gifts to the person who gave them)...and that's the numerator...so any that don't have any of the original, are valid, divide by the number of possible, and you get the percent chance that no one will get their own gift...

Looks good up through 9, but 10 and 11 seem to be off.

[Pickett]

Looks good up through 9, but 10 and 11 seem to be off.

yep, I was wondering why they didn't follow the pattern...here's an update for 10: 1334961 / 3628800 = 36.79%...so, it definitely seems like it will stay at 36.79% now. Wrote the code in about 5 minutes, so, missed one little thing, that's why the numbers were off...

[Guest]

Thats what I came up with -about 3 in a million

I think the odds are actually much lower than this for EVERYONE to pick their own gift...

1/9*1/8*1/7... calculation ignores the possibility that a person's gift was already pulled from the bag before their turn. This calculation is the chance ONLY assuming their gift remains in the bag which is...

person 1- 9/9 chance in bag*1/9 chance he pulls (=1/9)

person 2- 8/9 chance in bag*1/8 chance he pulls = 1/9

person 3- 7/9 chance in bag*1/7 chance he pulls = 1/9

so I get 1/9^9= 1 in 387million chance everybody gets their own.

my last 2 agree with voltage's answers so I'm feeling better!!!

Edited February 24, 2009 by Archimedes

[Guest]

Statistics equation for probability event will not occur: 1 - (1 / number of gifts)

[Prof. Templeton]

You got it. This series appears to converge at

1/e

Spoiler for here's a simple way to calculate:

Let's say your trying to find out the number of ways n people with n things can all get the wrong thing (like we are). Take the sum of the total number of ways for n-1 and n-2 and multiply by n-1. For example, lets take 7. It would be 6(6! + 5!)=5040 or 6 x (720+120) = 5040.

[Pickett]

You got it. This series appears to converge at

1/e

Spoiler for here's a simple way to calculate:

Let's say your trying to find out the number of ways n people with n things can all get the wrong thing (like we are). Take the sum of the total number of ways for n-1 and n-2 and multiply by n-1. For example, lets take 7. It would be 6(6! + 5!)=5040 or 6 x (720+120) = 5040.

that's awesome...I love "e"...it's great. This was a great puzzle. Thanks!

[Guest]

The probabilities of people not picking thier own gift should be multiplied. However this trend stops after the majority of the people have picked up a gift.

eg.

1) 8/9

2) 7/8

3) 6/7

4) 5/6

5) 4/5

After this point it would be impossible for any of the remaining people to recieve thier own gift since it has already been taken, 100%.

Thus the probability of 9 people not getting the gift they gave is 8/9*7/8*6/7*5/6*4/5=4/9 approx 44.44%

Best ASCII diagram i can draw to help people understand my train of thought:

X X X X X X X X X<gift

/ / / / <abritrary choice of a present not thiers

0 0 0 0 0 0 0 0 0 < people

%1% 1%1 %1 % < chance of getting a present no thiers for % see above numbers

Same logic would apply to the 11 person case. giving a probability of 5/11 or 45.45%

[Prof. Templeton]

The probabilities of people not picking thier own gift should be multiplied. However this trend stops after the majority of the people have picked up a gift.

eg.

1) 8/9

2) 7/8

3) 6/7

4) 5/6

5) 4/5

After this point it would be impossible for any of the remaining people to recieve thier own gift since it has already been taken, 100%.

Thus the probability of 9 people not getting the gift they gave is 8/9*7/8*6/7*5/6*4/5=4/9 approx 44.44%

Best ASCII diagram i can draw to help people understand my train of thought:

X X X X X X X X X<gift

/ / / / <abritrary choice of a present not thiers

0 0 0 0 0 0 0 0 0 < people

%1% 1%1 %1 % < chance of getting a present no thiers for % see above numbers

Same logic would apply to the 11 person case. giving a probability of 5/11 or 45.45%

I'm not sure I see where you're coming from.

The very last person could be the only one who receives his own gift.

For nine people

1 takes 8's

2 takes 1's

3 takes 2's

4 takes 3's

5 takes 4's

6 takes 5's

7 takes 6's

8 takes 7's

and

9 takes 9's

There are many ways this could happen.

[Guest]

I'm not sure I see where you're coming from.

The very last person could be the only one who receives his own gift.

For nine people

1 takes 8's

2 takes 1's

3 takes 2's

4 takes 3's

5 takes 4's

6 takes 5's

7 takes 6's

8 takes 7's

and

9 takes 9's

There are many ways this could happen.

Ahh, I now see the error in my ways and I agree the equation below is the way to solve

X_n=[(X_n-2 + X_n-1)*(n-1)]

X₁=0

X₂=1

[Guest]

sounds right

Edited February 24, 2009 by zippzom