Challenge 18: Happily Married

[micromass]

Happily Married

QUESTION:

Let $B$ be a set of boys (possibly infinite). Each boy $b\in B$ knows a finite set of girls $G_b$. We want to marry each boy with some girl (legally: thus no girl can be married with more than one boy).

A necessary condition for this is of course that each finite subset of $n$ boys knows at least $n$ girls.

Prove that this is a sufficient condition as well!

Please list any sources that you have used to solve this question. Using google or other search engines is forbidden. Wikipedia is allowed but not its search engine. Wolfram alpha and other mathematical software is allowed.

Points will be given as follows:
1) First person to post a correct solution to one of the above points will receive 3 points (So if you solved 3 and 4, you will receive 6 points).

2) Anybody to post a (original) correct solution to one of the above points will receive 1 point.

3) Anybody posting a (nontrivial) generalization of some of the above questions will receive 2 points

4) The person who posts a solution with the least advanced mathematical machinery will receive 1 extra point for his solution (for example, somebody solving this with basic calculus will have an "easier" solution than somebody using singular homology), if two people use the same mathematical machinery, then we will look at how complicated the proof is.

5) The person with the most elegant solution will receive 1 extra point for his solution (I decide whose solution is most elegant)

Private messages with questions, problem suggestions, feedback, etc. are always welcome!

 

[jbunniii]

Define $G = \cup_{b\in B} G_b$. We need to show that there exists a choice function $f : B \rightarrow G$ with the following properties:

1. $f(b) \in G_b$ for every $b\in B$
2. $f$ is injective

If $B$ is finite, say containing $n$ boys, then there is no problem since they collectively know at least $n$ girls, and there always exists an injection from a set into a set of greater cardinality, by definition.

So we assume that $B$ is infinite (perhaps even uncountable). The axiom of choice ensures that (1) is possible. Let $F$ be the set of all functions satisfying (1). For any $n \in \mathbb{N}$, let $B_n$ denote a subset of $B$ containing $n$ elements. Let $G_n = \cup_{b\in B_n}G_b$ denote the girls known collectively by the boys in $B_n$. Since the cardinality of $G_n$ is at least $n$, there exists an injection $f_n : B_n \rightarrow G_n$. We can extend this to a function $\hat{f}_n \in F$ using the axiom of choice. In this way, we obtain a sequence $(\hat{f}_n)$ of functions in $F$, with the property that for each $n$, there is a set $B_n \subset B$ of size $n$ such that the restriction $\hat{f}_n|_{B_n}$ is injective. If the $B_n$'s are a nested increasing sequence of sets, we could even arrange it so that if $n < m$, then $\hat{f}_n$ and $\hat{f}_m$ agree on $B_n$.

I fear that I don't know enough set theory to push this the rest of the way. It might be possible to make some limiting argument that works if $B$ is countable (I think the $\hat{f}_n$ will converge pointwise to an injective function $B \rightarrow G$ in that case), but otherwise I think some other method is required.

 

[micromass]

D
If $B$ is finite, say containing $n$ boys, then there is no problem since they collectively know at least $n$ girls, and there always exists an injection from a set into a set of greater cardinality, by definition.

I would like a rigorous proof of the situation where $B$ is finite. I don't find it that obvious...

 

[jbunniii]

I would like a rigorous proof of the situation where $B$ is finite. I don't find it that obvious...

OK, I'll work on that. I'm also having second thoughts about this remark:

If the $B_n$'s are a nested increasing sequence of sets, we could even arrange it so that if $n < m$, then $\hat{f}_n$ and $\hat{f}_m$ agree on $B_n$.

I don't think it's correct as stated. Let me give it some more thought.

 

[D H]

Each boy b∈B knows a finite set of girls G_b.

Does a boy need to marry a girl he knows, or are arranged marriages OK?

If they aren't, there's a problem. Suppose some boy b in B has been stranded on a desert isle and the set of girls G_b that he knows is the empty set.

 

[Matterwave]

Does a boy need to marry a girl he knows, or are arranged marriages OK?

If they aren't, there's a problem. Suppose some boy b in B has been stranded on a desert isle and the set of girls G_b that he knows is the empty set.

Each finite set of n boys knows at least n girls though. So a set of 1 boy must at least know 1 girl.

 

[D H]

Each finite set of n boys knows at least n girls though. So a set of 1 boy must at least know 1 girl.

No. Suppose you're the unlucky boy on a desert isle, some lucky guy on the mainland knows hundreds of girls. Even though collectively the two of you know hundreds of girls, you still don't know a single one.

 

[Matterwave]

No. Suppose you're the unlucky boy on a desert isle, some lucky guy on the mainland knows hundreds of girls. Even though collectively the two of you know hundreds of girls, you still don't know a single one.

But the assumption that we have to prove is sufficient is "each finite set of n boys knows at least n girls". n=1 should be valid in that statement as well in which that statement reads "a finite set of 1 boy knows at least 1 girl".

 

[D H]

If that's the interpretation, I would argue that correct word there is subset rather than set.

 

[micromass]

No. Suppose you're the unlucky boy on a desert isle, some lucky guy on the mainland knows hundreds of girls. Even though collectively the two of you know hundreds of girls, you still don't know a single one.

I think you misinterpreted the question, so let me put it in mathematical terms to be unambiguous.

So let's say we have a set $B$ of boys and $G$ of girls. Let's say you have a function $G:B\rightarrow \mathcal{P}(G)$ which associates with every boy $b$ a set $G_b$ of girls he knows.
The assumption is that for every subset $A\subseteq B$ which is finite, we have that
$$|A|\leq \left|\bigcup_{b\in A} G_b\right|$$
The conclusion is that there exists a injective function $f:B\rightarrow G$ such that $f(b)\in G_b$.

 

[micromass]

If that's the interpretation, I would argue that correct word there is subset rather than set.

Yes, I am sorry for any misinterpretations! I'll correct it.

 

[verty]

The contrary statement is this: suppose we can marry every boy to a girl he knows, then every finite set of n boys knows at least n girls. This is plainly true: every set of n boys knows the corresponding set of n wives.

Now the suppose the original claim fails, then there is no assignment of boys to girls such that every boy marries a girl he knows. Either there are not enough girls or for an optimal allocation of girls to boys, there are boys married to girls they don't know. By optimal, I mean the following: there is no finite set S of boys such that each boy in S is married to a girl he doesn't know but the wives of S are known only by the boys in S.

Case 1: Suppose there are insufficiently many girls. The set of girls must have cardinality strictly less than the set of boys in this case, as I'll now prove. If B is finite, it is impossible to have too few girls. If B is countably infinite, we have a sequence of boys and we can generate a sequence of girls by the following process. For each n≥0, choose a boy n and marry him to an unmarried girl in G_n. This gives a sequence of girls, so there are sufficiently many if B is countably infinite.

If B is uncountable, by the previous argument any countably infinite subset of B can generate a sequence of known wives. Now choose any boy b_0 (axiom of choice) who is yet unmarried, the girls he knows are married. Choose any girl he knows and marry them, this leaves that husband b_1 now divorced. B_0 and b_1 together know another girl, she is married. Marry them, this leaves husband b_2 divorced. Continue in this manner and upon reaching infinite speed in this task, we have a sequence of known wives. Apply the same procedure (axiom of choice / well-ordering theorem) to each unmarried boy. Therefore there are sufficiently many girls.

Case 2: We have an optimal allocation with boys married to unknown wives. B cannot be finite in this case. If B is countably infinite, reorder the wives in the expected way, so this is excluded. B must be uncountable. Now, in a similar way to case 1, apply that limiting procedure to each boy who has an unknown wife: he knows a married girl, marry them, that leaves a divorced husband, they together know a married girl, etc, etc. Doing this to infinity (*) to each undesirable eliminates all the difficulty, so this case is also impossible.

Therefore, the supposition is absurd, the original claim must be true.

------------------------------------------------------------------------------------------------------

The only thing I don't like about this is the "upon reaching infinite speed" remark. It's either wrong or a cop out. But, this is the best I can come up with.

(*): I should have shown why the optimality criterion is necessary. It means that it can't happen that after n steps, we have married n girls to n boys without leaving a divorced husband in addition. If after n steps, no divorced husband remains, it means the n girls married by this procedure were the original wives of the n boys, but the optimality criterion outlaws this. I decided to edit this in because no one has replied yet.

 

[verty]

I see some problems with my proof attempt:

1) I said that the cardinality of the set of girls must be strictly less than the cardinality of the set of boys for there to be insufficiently many girls, but this comment should probably have been omitted altogether, it isn't relevant.

2.1) I said that any countably infinite subset of B can generate a sequence of known wives but it isn't clear that this happens simultaneously. Suppose two groups of n boys know the same n girls. I failed to make it clear that this can't happen. The reason is: the two groups together know 2n girls, so it's not possible for them to know the same n only.

2.2) This doesn't quite fix the problem. Perhaps there is a countably infinite subset of boys such that there is no way to marry them to known girls. The reason would be that at some stage, all the known girls are married. This proof is pretty broken actually.

 

[Joffan]

Focusing more on the finite side, here is a process for pairing off a set that meets the conditions:

First note that we will track the set of unmarried boys (bachelors) who know each know a number of unmarried girls (spinsters) in accordance with the initial necessary condition; viz. that any subset of n bachelors knows at least n spinsters. I'll refer to this as the critical property.

We will be looking for subsets of n bachelors who know exactly n spinsters between them. These are equality sets.

Lemma 1
If a set with the critical property, A, has a proper subset B that is an equality set, we can create a set C removing B from A by removing the bachelors in B and all the spinsters they know from the lists of bachelors not in B. This set C also has the critical property.
Proof: Consider any set D of k bachelors within C. Then combined with the n bachelors in B, we know that these men know at least n+k spinsters. Since B is an equality set they know only n spinsters. Therefore the bachelors in D must know at least k other spinsters.

Lemma 2
If a set with the critical property, A, has no proper subset that is an equality set, we can create a set C by removing one bachelor and anyone spinster he knows from the lists of other bachelors from A, and C will still have the critical property.
Proof: Since there is no equality subset in A, any group of n bachelors knows at least n+1 spinsters. Therefore removing anyone spinster will not break the critical property.

Process:

Iterative step:
===========
Find the smallest equality subset (proper subset) in the set under consideration.

If no such set exists, marry bachelors to spinsters they know arbitrarily (Lemma 2) until such a set does exist (or until the set is empty), each time removing the married man from the set of bachelors and the married woman from the lists of spinsters known to bachelors in the set.

Pick an equality subset of the smallest size, and separate this set from the containing set (Lemma 1) in order to marry those m bachelors to the m spinsters.
If m=1 for the subset, the bachelor marries the spinster he knows.
If m>1, apply the iterative step to the removed subset - this will start with at least one arbitrary marriage because this was the smallest subset with the equality condition.

Continue finding the smallest equality subset in the remaining set or making arbitrary marriages if none exist, until the set is empty.

=====

Extension to an infinite set might take more consideration, perhaps, but certainly this process will work for an arbitrarily large set.

 

[micromass]

Looks pretty good! Extra points for somebody who can make a computer program that implements such a procedure in the finite case.

 

[Joffan]

It's finding the equality subsets that would be the hold up in a program. I would do all sorts of data tracking to make that more reasonable, and certainly I'd track everything from the girls' side as well. It's always safe (in terms of process completion) for a spinster to marry the only bachelor she knows, as well as vice versa.

 

[mfb]

I'll ignore uncountable sets (as we learned, those cannot be present at the surface of Earth if boys have at least the shape of a "T") and focus on finite and countable infinite sets.

Every boy knows at least one girl (necessary condition with n=1).

Step 1:
Take all boys that know just exactly one girl, marry them to it. This is possible as no girl gets married more than once (would violate the necessary condition for the partners of this girl). The process maintains the necessary condition for every subset:
(A) for every subset containing this boy, we reduce the bachelors by 1 and the known girls by 1 -> fine
(B) for every subset of n boys not containing this boy, there have to be at least n girls known (not including the married one), otherwise this subset together with the married boy would violate the necessary condition for n+1.

Repeat this step, if the now reduced set of boys and girls has boys with just one connection left. In the finite case this has to halt, in the infinite case: every boy that eventually gets a girl after a finite number of steps is assigned to this girl.

Remove the now married boys and girls from the set. In both cases, we are now left with a set of boys that know at least 2 girls (or an empty set).

Step 2:
Assign a positive integer to every boy.

Take the boy B with the smallest integer. Marry him to a girl in such a way that the necessary condition holds. This is possible based on the following: Imaging marrying him to any girl he knows would violate the necessary condition. As the marriage takes out exactly one girl, this would mean that for every possible marriage G, there is a set of n boys (not including B) that know exactly n girls (including G). There would have to be one such set for every possible marriage. Take the union of those sets, and you get N boys knowing N girls. Include B, and you have N+1 boys knowing N girls. Contradiction.Repeat steps 1 and 2. Each time, the boy with the smallest number gets married (regardless of how many girls he knows), so we can assign a girl to every boy, always preserving the necessary condition to continue steps 1 and 2.

 

[micromass]

I'll ignore uncountable sets (as we learned, those cannot be present at the surface of Earth if boys have at least the shape of a "T") and focus on finite and countable infinite sets.

I do note that nobody has yet proved the case where it merely has the shape of a T.

Step 2:
Assign a positive integer to every boy.

Ok, take
Boy 1 Knows Girl A,B,C
Boy 2 Knows Girl B,C
Boy 3 Knows Girl B,C

Take the boy B with the smallest integer.

So we take Boy 1.

Marry him to a girl in such a way that the necessary condition holds. This is possible based on the following: Imaging marrying him to any girl he knows would violate the necessary condition. As the marriage takes out exactly one girl, this would mean that for every possible marriage G, there is a set of n boys (not including B) that know exactly n girls (including G).

There are 3 possible marriages: (1,A), (1,B), (1,C)
But for the first marriage, there is no set of n boys (not including 1) that know exactly n girls (including A). Indeed, the possible sets are {2} who knows {B,C}, {3} who knows {B,C} and {2,3} who knows {B,C}. So neither og the girls includes A. I am not sure how crucial this is to your argument though.

Also, where exactly do you use in Step 2 that every boy knows at least 2 girls? Is Step 1 really necessary?

 

[mfb]

Yeah I guess step 1 is not necessary. Step 2 does the same anyway.

In your example, the marriage with A leads to the empty set of 0 boys knowing 0 girls.
For the other marriages, the critical sets are {2,3} in both cases, as {2} alone knows more than one girl, so taking away one would be unproblematic.

 

[micromass]

Yeah I guess step 1 is not necessary. Step 2 does the same anyway.

In your example, the marriage with A leads to the empty set of 0 boys knowing 0 girls.
For the other marriages, the critical sets are {2,3} in both cases, as {2} alone knows more than one girl, so taking away one would be unproblematic.

I'm not saying it would be problematic. But you said that you obtained a set of n boys (not including 1) who knows a set of n girls (including A). It is the bold part that I am talking about. It means that the set of girls do not necessary need to include A. You claimed otherwise in your post, does this cause a problem?

 

[mfb]

A girl that is just known by B is a special case I did not consider explicitly, but I don't have to:

Imaging marrying him to any girl he knows would violate the necessary condition.

Marrying B to this girl does not violate the necessary condition for any set of boys, so if we have this case there is no problem to marry B.

 

[lpetrich]

Necessity: (all marriages possible) -> (every set of n boys knows at least n girls)
Sufficiency: (every set of n boys knows at least n girls) -> (all marriages possible)
Sufficiency: (Some marriages not possible) -> (some sets of n boys know fewer than n girls)

Let's consider the whole set, and divide the nb boys into nm boys who can get married and nu who cannot; nb = nm + nu. There must be nm girls, one for each of the nm married boys. More than that, and there would be one available for one of the nu boys who can't be married, which violates the condition. Since nm < nb, there is thus at least one set where n boys know fewer than n girls.

 

[Joffan]

I don't think "Some marriages not possible" is well-defined, and nor is that set division picking out "nu boys who cannot get married".

Consider
Andy: {Karen,Nora,Tanya}
Brian: {Olive,Qamra,Ruth}
Chad: {Lisa,Sue,Tanya}
Dave: {Molly,Olive,Sue}
Edgar: {Lisa,Olive,Pat}
Frank: {Lisa,Nora,Ruth}
Geoff: {Molly,Pat,Tanya}
Hank: {Karen,Ruth,Sue}
Ivan: {Karen,Molly,Qamra}
James: {Nora,Pat,Qamra}

Marrying each bachelor to the first available spinster in order:
(Andy, Karen), (Brian, Olive), (Chad,Lisa), (Dave, Molly), (Edgar, Pat), (Frank, Nora), (Geoff, Tanya), (Hank, Ruth), (Ivan, Qamra)...
and James is left without a bride (and Sue without a groom). But they do not know each other so cannot marry.

This set CAN be married off though. But "boys who cannot get married" is not a simple concept.