Search   Memberlist   Usergroups
 Page 1 of 1 [5 Posts]
Author Message
Pavel314

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" 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
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

 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
Pavel314

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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [5 Posts]
 The time now is Sat Aug 27, 2016 6:24 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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