FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Probability
Probability of collision free name draw for gift exchange
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
Author Message
Pavel314
science forum addict


Joined: 29 Apr 2005
Posts: 78

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

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

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

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

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

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

PostPosted: Sat Dec 31, 2005 7:36 pm    Post subject: Re: Probability of collision free name draw for gift exchange Reply with 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:
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

PostPosted: Thu Dec 29, 2005 5:06 pm    Post subject: Probability of collision free name draw for gift exchange Reply with 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
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
The time now is Wed Jun 29, 2011 6:58 pm | All times are GMT
Forum index » Science and Technology » Math » Probability
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Probability Question dumont Probability 0 Mon Oct 23, 2006 3:38 pm
No new posts probability gorbag Probability 0 Mon Aug 14, 2006 11:06 pm
No new posts "Free" electricity The Real Chris Fusion 0 Wed Jul 19, 2006 8:42 pm
No new posts What are the obstacles to building a pen-sized free-elect... Radium Research 0 Tue Jul 18, 2006 5:48 pm
No new posts Probability of attaining a minimum value when rolling dice nick@blackmarble.co.uk Math 16 Tue Jul 18, 2006 2:57 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 5.9503s ][ Queries: 20 (5.3358s) ][ GZIP on - Debug on ]