Challenge 18: Happily Married

1. Jun 11, 2014

micromass

Staff Emeritus
Happily Married

QUESTION:
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!

Last edited: Jun 11, 2014
2. Jun 11, 2014

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.

3. Jun 11, 2014

micromass

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

4. Jun 11, 2014

jbunniii

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

5. Jun 11, 2014

D H

Staff Emeritus
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 Gb that he knows is the empty set.

6. Jun 11, 2014

Matterwave

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

7. Jun 11, 2014

D H

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

8. Jun 11, 2014

Matterwave

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

9. Jun 11, 2014

D H

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

10. Jun 11, 2014

micromass

Staff Emeritus
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$.

11. Jun 11, 2014

micromass

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

12. Jun 11, 2014

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.

Last edited: Jun 12, 2014
13. Jun 12, 2014

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.

14. Jun 15, 2014

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

15. Jun 15, 2014

micromass

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

16. Jun 15, 2014

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.

17. Jun 16, 2014

Staff: Mentor

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.

Last edited: Jun 16, 2014
18. Jun 16, 2014

micromass

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

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

So we take Boy 1.

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?

19. Jun 16, 2014

Staff: Mentor

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.

20. Jun 16, 2014

micromass

Staff Emeritus
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?