wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Marriage Matchings
        
(Message started by: william wu on Nov 22^nd, 2002, 3:37pm)

Title: Marriage Matchings
Post by william wu on Nov 22^nd, 2002, 3:37pm

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.

Title: Re: Marriage Matchings
Post by Speaker on Nov 25^th, 2002, 1:20am

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.

Title: Re: Marriage Matchings
Post by Icarus on Nov 25^th, 2002, 6:58pm

My count is 80 possible pairings.

Title: Re: Marriage Matchings
Post by James Fingas on Nov 26^th, 2002, 5:19pm

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

Title: Re: Marriage Matchings
Post by SWF on Nov 26^th, 2002, 7:57pm

When M is 3, I think the solution for any N is (N!)³*sum(i=0 to infinity) (N!/i!/(N-i)!)³. If there is not a good way to further simplify this, a general expression for any value of M could be quite messy.

Title: Re: Marriage Matchings
Post by Icarus on Nov 26^th, 2002, 8:40pm

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)