Author 
Message 
Pavel314 science forum addict
Joined: 29 Apr 2005
Posts: 78

Posted: Mon Jan 02, 2006 2:59 pm Post subject:
Update: Probability of collision free name draw for gift exchange



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
Quote: 
"Bill" <billandopus@yahoo.com> wrote in message
news:35Btf.22$bd.4@tornado.tampabay.rr.com...
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:
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



Back to top 


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

Posted: Sun Jan 01, 2006 6:40 am Post subject:
Re: Probability of collision free name draw for gift exchange



Bill <billandopus@yahoo.com> wrote in news:35Btf.22$bd.4
@tornado.tampabay.rr.com:
Quote:  Out of 40320 (8!) selection possibilities, only 1265 meet your criteria,
for a 3.137 % probability.

This makes more sense to me, but I'm still puzzled. I kept thinking of this
as A's pick affecting B, and so on and so forth. How did you figure out
that 1265 was the number of correct sequences? I couldn't come up with a
formula, and hence couldn't know that 1265 was the right number.
Jason 

Back to top 


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

Posted: Sat Dec 31, 2005 9:56 pm Post subject:
Re: Probability of collision free name draw for gift exchange



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...
Quote:  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:
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 


Back to top 


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

Posted: Sat Dec 31, 2005 7:36 pm Post subject:
Re: Probability of collision free name draw for gift exchange



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:
Quote:  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 


Back to top 


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

Posted: Thu Dec 29, 2005 5:06 pm Post subject:
Probability of collision free name draw for gift exchange



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 

Back to top 


Google


Back to top 



The time now is Tue Sep 01, 2015 6:08 pm  All times are GMT

