Author |
Topic: Marriage Matchings (Read 996 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Marriage Matchings
« on: Nov 22nd, 2002, 3:37pm » |
 Quote  Modify
|
There are three families, each with two sons and two daughters. In how many ways can the sons all be monogamously matched with the daughters?
(Assume you can't marry within your own family, and all persons are heterosexual. Also, no one has undergone a sex change.)
Generalize to M families, each with N sons and N daughters.
|
| « Last Edit: Nov 22nd, 2002, 3:37pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Speaker
Uberpuzzler
Gender:
Posts: 1118
|
|
Re: Marriage Matchings
« Reply #1 on: Nov 25th, 2002, 1:20am » |
Quote Modify
|
I do not have a formula, per se, but I figure that each pair of brothers can wed in 12 unique matchings. Since we have to take into consideration that one's sibling must wed also. And thus with three pairs of brothers that would give us a total of 36 possible unique combinations of weddings. Rather than generalize M and N, I just drew some lines and circles on a piece of paper.
As this puzzle is in the hard section, I have my reservations. But, here it is.
|
|
IP Logged |
They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. <Ben Franklin>
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Marriage Matchings
« Reply #2 on: Nov 25th, 2002, 6:58pm » |
Quote Modify
|
My count is 80 possible pairings.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Marriage Matchings
« Reply #3 on: Nov 26th, 2002, 5:19pm » |
Quote Modify
|
Icarus, I must agree with you.
I will use the following terminology: Family 1 has brothers AA and sisters BB. Family 2 has brothers CC and sisters DD. Family 3 has brothers EE and sisters FF.
I split up the problem into two possibilities:
1) in the first case, brothers AA pick brides from the same family. There are four different ways to do this (once brother A picks his bride, his brother has no choice). If they picked sisters DD, then brothers EE can only wed sisters BB. There are two ways of doing this. There are then two ways for brothers CC to wed brothers FF.
2) in the second case, brothers AA pick brides from different families. They pick brides DF. There are 8 ways of doing this. After that, brothers CC must wed BF, and brothers EE must wed BD (this is the only way that we can wed the remaining sisters D and F). There are 4 ways for CC to pick, and two ways for EE to pick.
Now to generalize ... Hmm. This may be substantially harder...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Marriage Matchings
« Reply #4 on: Nov 26th, 2002, 7:57pm » |
Quote Modify
|
When M is 3, I think the solution for any N is (N!)3*sum(i=0 to infinity) (N!/i!/(N-i)!)3. If there is not a good way to further simplify this, a general expression for any value of M could be quite messy.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Marriage Matchings
« Reply #5 on: Nov 26th, 2002, 8:40pm » |
Quote Modify
|
I believe there is a formula for the sum of (N | i)^3 (where (N | i) represents "N choose i"). But I can't remember it, and the best I have been able to find is that the sum of (N | i)^2 is (2N | N). Perhaps the formula can be obtained using the following product result. I haven't thought it out yet:
(M | 0)(N | p) + (M | 1)(N | p-1) + ... + (M | p)(N | 0) = (M + N | p)
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print