Probability of collision free name draw for gift exchange

Pavel314 · science forum addict Joined: 29 Apr 2005 Posts: 78

I wrote a UBasic program to simulate the gift exchange situation with the
restrictions as stated in the original post; the program runs 100,000 random
draws and reports how many of those met the restrictions. The results for
six runs average a bit higher than Bill's probability of 3.137% but are in
the range:

3.166%
3.189%
3.263%
3.280%
3.298%
3.331%

I then modified the program to run 100,000,000 tests. After running for
close to two hours, it reported 3,255,472 successful draws or 3.255%. Still
hitting a bit high of the theoretical probability.

Paul

Jason Simons · science forum beginner Joined: 03 Feb 2005 Posts: 8

Bill <billandopus@yahoo.com> wrote in news:35Btf.22$bd.4
@tornado.tampabay.rr.com:

Pavel314 · science forum addict Joined: 29 Apr 2005 Posts: 78

Bill,

Could you post how you got 1,265? Each person has 5 possible matches,
excluding self, spouse and last year's recipient from the 8 in the group.
But when the first person "A" chooses legitimate recipient "B", that removes
"B" from the legitimate recipient pool for the participants who aren't "B",
the spouse of "B" or the person who gave "B" a present last year. There must
be a logical way to arrive at 1,265 without drawing a very complex
probability tree, but I can't figure it out at the moment.

Thanks,

Paul

"Bill" <billandopus@yahoo.com> wrote in message
news:35Btf.22$bd.4@tornado.tampabay.rr.com...

Bill1173 · science forum beginner Joined: 02 Oct 2005 Posts: 19

Out of 40320 (8!) selection possibilities, only 1265 meet your criteria,
for a 3.137 % probability. Therefore it is no surprise you had such bad
luck.

For a similar situation with only 3 couples, 17 out of 720 possibilities
exist. (slightly more than 2%)

For only 2 couples, only one solution is possible out of 24 chances
(over 4%)

Paul

Jason Simons wrote:

Jason Simons · science forum beginner Joined: 03 Feb 2005 Posts: 8

This Christmas my siblings and their spouses each gave gifts to eachother
from a name we drew out of a hat. We could not select ourself or our
spouse. There are 8 people in the exchange. This year we had all kinds of
trouble getting a successful draw because we didn't want a repeat either.

So I was wondering. What is the probability that every person
successfully draws a name that is not their own, their spouse, or last
years gift recipient.

I found this to be more difficult than I thought. I still don't have an
answer, but I estimate it to be less than 25%.

A is married to B

C is married to D

E is married to F

G is married to H

A selected C this year

B selected D this year

C selected E this year

D selected F this year

E selected G this year

F selected H this year

G selected A this year

H selected B this year

A can select D through H

B can select C or E through H

C can select A, B or F through H

D can select A, B, E, G, H

E can select A through D, H

F can select A through D, G

G can select B through F

H can select A or C through F

I'd like to see this one explained.

Thanks,

Jason

Google