Marriage problem says { b 1 , b 2 , … , b n } and { g 1 , g 2 , … , g n } are n boys and n girls respectively. Let G i =set of girls b i likes. Then a necessary and sufficient condition for a monogamous marriage to happen such that each b i gets married to a girl in G i (a compatible matching) is that for any 1 ≤ k ≤ n, and any 1 ≤ i 1 &lt; i 2 &lt; ⋯ &lt; i k ≤ n, cardinality of G i 1 ∪ ⋯ ∪ G i k should be bigger than k that is, take any k boys then the total number of girls that these k boys together like should be at least k.There is apparently a version of marriage problem in which one considers both the sets- the set of girls whom each boy likes and set of the boys whom each girl likes. In that case the condition reduces to considering any k boys out of ⌈ n / 2 ⌉ instead of n above.

Question

Marriage problem says   {      b    1    ,      b    2    ,  …  ,      b    n    } and   {      g    1    ,      g    2    ,  …  ,      g    n    } are   n boys and   n girls respectively. Let       G    i  =set of girls       b    i   likes. Then a necessary and sufficient condition for a monogamous marriage to happen such that each       b    i   gets married to a girl in       G    i   (a compatible matching) is that for any   1  ≤  k  ≤  n, and any   1  ≤      i    1    &amp;lt;      i    2    &amp;lt;  ⋯  &amp;lt;      i    k    ≤  n, cardinality of       G                  i        1              ∪  ⋯  ∪      G                  i        k             should be bigger than   k that is, take any   k boys then the total number of girls that these   k boys together like should be at least   k.There is apparently a version of marriage problem in which one considers both the sets- the set of girls whom each boy likes and set of the boys whom each girl likes. In that case the condition reduces to considering any k boys out of   ⌈  n      /    2  ⌉ instead of   n above.

embutiridsl · Accepted Answer

If   B and   G are the sets of boys and girls, respectively, for each   b  ∈  B let       G    ¯    (  b  ) be the set of girls whom 𝑏 does not like, and for each   g  ∈  G let       B    ¯    (  g  ) be the set of boys whom   g does not like. (It’s more convenient here to use these rather than   G  (  b  ) and   B  (  g  ), the sets of boys or girls liked by an individual, but the two are obviously interchangeable.) Then the boys and girls can be married off iff there do not exist       B    0    ⊆  B and       G    0    ⊆  G such that       |        B    0        |    +      |        G    0        |    &amp;gt;  n,       G    0    ⊆      ⋂          b      ∈              B        0                  G    ¯    (  b  ), and       B    0    ⊆      ⋂          g      ∈              G        0                  B    ¯    (  g  ). Clearly if such       B    0   and       G    0   did exist, one of them would have to have cardinality at most   ⌈  n      /    2  ⌉.Suppose that for each       B    1    ⊆  B and       G    1    ⊆  G of cardinality at most   ⌈  n      /    2  ⌉,       |          ⋂              b        ∈                  B          1                            G      ¯        (    b    )    |    &amp;lt;  n  −      |        B    1        |   and       |          ⋂              g        ∈                  G          1                            B      ¯        (    b    )    |    &amp;lt;  n  −      |        G    1        |  . Suppose, to get a contradiction, that       B    0    ⊆  B and       G    0    ⊆  G are such that       |        B    0        |    +      |        G    0        |    &amp;gt;  n,       G    0    ⊆      ⋂          b      ∈              B        0                  G    ¯    (  b  ), and       B    0    ⊆      ⋂          g      ∈              G        0                  B    ¯    (  g  ); without loss of generality       |        B    0    ≤  ⌈  n      /    2  ⌉. But then       |          ⋂              b        ∈                  B          0                            G      ¯        (    b    )    |    &amp;lt;  n  −      |        B    0        |    &amp;lt;      |        G    0        |  , so       G    0    ⊈      ⋂          b      ∈              B        0                  G    ¯    (  b  ).It only remains to check that the nonexistence of sets       B    0    ⊆  B and       G    0    ⊆  G such that,       G    0    ⊆      ⋂          b      ∈              B        0                  G    ¯    (  b  ), and       B    0    ⊆      ⋂          g      ∈              G        0                  B    ¯    (  g  ) is equivalent to the usual formulation of the marriage condition, but this is pretty straightforward if one thinks in terms of the adjacency matrix of the obvious bipartite graph.

Marriage problem says {b_1,b_2,…,b_n} and {g_1,g_2,…,g_n} are n boys and n girls respectively. Let G_i=set of girls b_i likes.

Answered question

Answer & Explanation

New Questions in Precalculus