Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following is a variation (something like it) of a marriage problem that I found interesting but couldn't quite get my head around on finding the conditions for this to work.

Let $B = \{b_1, . . . , b_k\}$ be a set of men and $G = \{g_1, . . . , g_n\}$ be a set of women, and suppose that each men wants to marry up to four of the women whom he fancies and who fancy him back (i.e. polygamy up to four wives is allowed, and man $b_i$ wants $0 \le n_i \le 4$ wives).

Find necessary and sufficient conditions for this problem to be solvable.

Of course the condition that every set of k men must fancy at least k women is needed for this problem to be solvable (ie: the case where every men can marry only 1 women). I'm guessing we can extend this to $ik$ women where $2 \le i \le 4$ for cases where every men can marry 2 women, 3 women, 4 women. However these do not seem like sufficient conditions for this problem to be solvable.

Are there other conditions that I am missing that seems needed?

share|improve this question

1 Answer 1

Hint: You can solve this problem easely the following way:

"Clone" the boys: replace each boy $b_i$ by 4 copies of $b_i$.

Now you need to solve the standard marriage problem for the following set:

$$B=\{b_{11}, b_{12}, b_{13}, b_{14}, b_{21}, b_{22}, b_{23}, b_{24}, ...., b_{k1}, b_{k2}, b_{k3}, b_{k4} \} $$

$$G = \{g_1, . . . , g_n\}$$

Can you show that your problem is equivalent to this? Can you use this to solve your problem?

share|improve this answer
    
I'm sorry if I'm understanding this incorrectly but if we're looking at that problem in the standard marriage problem trying to match all the boys with the girls, wouldn't that be solely the case where all boys get all 4 girls strictly? –  Room Nov 15 '11 at 3:09
    
Well yes that would be the case... BUT, if you want to make sure that for example each man can marry lets say at least 2 women, then this is the same as saying that it should be possible for every man to marry exactly 2 women... And so on... –  N. S. Nov 15 '11 at 3:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.