IMC 2011 · Day 2 · P7

(a) Let $M$ be the set of males, $F$ the set of females, and $E$ the set of emales. Consider the (tripartite) graph $G$ with vertices $M \cup F \cup E$ and edges for likes. A 3-cycle is then a possible family. We'll call $G$ the graph of likes.

First, let $k = \frac{n}{2}$. Then $n$ has to be even and we need to construct a graph of likes with no 3-cycles. We'll do the following: divide each of the sets $M$, $F$, and $E$ into two equal parts and draw all edges between two parts as shown below:

Clearly, there is no 3-cycle.

(b) First divide the the expedition into male-emale-female triples arbitrarily. Let the unhappiness of such a subdivision be the number of pairs of aliens that belong to the same triple but don't like each other. We shall show that if unhappiness is positive, then the unhappiness can be decreased by a simple operation. It will follow that after several steps the unhappiness will be reduced to zero, which will lead to the happy marriage of everybody.

Assume that we have an emale which doesn't like at least one member of its triple (the other cases are similar). We perform the following operation: we swap this emale with another emale, so that each of these two emales will like the members of their new triples. Thus the unhappiness related to this emales will decrease, and the other pairs that contribute to the unhappiness remain unchanged, therefore the unhappiness will be decreased.

So, it remains to prove that such an operation is always possible. Enumerate the triples with $1, 2, \dots, n$ and denote by $E_i, F_i, M_i$ the emale, female, and male members of the $i$th triple, respectively. Without loss of generality we may assume that $E_1$ doesn't like either $F_1$ or $M_1$ or both. We have to find an index $i > 1$ such that $E_1$ likes the couple $F_i$, $M_i$ and $E_i$ likes the couple $F_1$, $M_1$; then we can swap $E_1$ and $E_i$.

There are at most $n/4$ indices $i$ for which $E_1$ dislikes $F_i$ and at most $n/4$ indices for which $E_1$ dislikes $M_i$, so there are no more than $n/2$ indices $i$ for which $E_1$ dislikes someone from the couple $M_i, F_i$, and the set of these undesirable indexes includes 1. Similarly, there are no more than $n/2$ indices such that either $M_1$ or $F_1$ dislikes $E_i$. Since both undesirable sets of indices have at most $n/2$ elements and both contain 1, their union doesn't cover all indices, so we have some $i$ which satisfies all conditions. Therefore we can always perform the operation that decreases unhappiness.

(for part b) Suppose that $k \ge \frac{3n}{4}$ and let's show that it's possible to marry all of the colonists. First, we'll prove that there exists a perfect matching between $M$ and $F$. We need to check the condition of Hall's marriage theorem. In other words, for $A \subset M$, let $B \subset F$ be the set of all vertices of $F$ adjacent to at least one vertex of $A$. Then we need to show that $|A| \le |B|$. Let us assume the contrary, that is $|A| > |B|$. Clearly, $|B| \ge k$ if $A$ is not empty. Let's consider any $f \in F \setminus B$. Then $f$ is not adjacent to any vertex in $A$, therefore, $f$ has degree in $M$ not more than $n - |A| < n - |B| \le n - k \le \frac{n}{4}$, a contradiction.

Let's now construct a new bipartite graph, say $H$. The set of its vertices is $P \cup E$, where $P$ is the set of pairs male–female from the perfect matching we just found. We will have an edge from $(m, f) = p \in P$ to $e \in E$ for each 3-cycle $(m, f, e)$ of the graph $G$, where $(m, f) \in P$ and $e \in E$. Notice that the degree of each vertex of $P$ in $H$ is then at least $2k - n$.

What remains is to show that $H$ satisfies the condition of Hall's marriage theorem and hence has a perfect matching. Assume, on the contrary, that the following happens. There is $A \subset P$ and $B \subset E$ such that $|A| = l$, $|B| < l$, and $B$ is the set of all vertices of $E$ adjacent to at least one vertex of $A$. Since the degree of each vertex of $P$ is at least $2k - n$, we have $2k - n \le |B| < l$. On the other hand, let $e \in E \setminus B$. Then for each pair $(m, f) = p \in P$, at most one of the pairs $(e, m)$ and $(e, f)$ is joined by an edge and hence the degree of $e$ in $G$ is at most $|M \setminus A| + |F \setminus A| + |A| = 2(n - l) + l = 2n - l$. But the degree of any vertex of $G$ is $2k$

and thus we get $2k \le 2n - l$, that is, $l \le 2n - 2k$.

Finally, $2k - n < l \le 2n - 2k$ implies that $k < \frac{3n}{4}$. This contradiction concludes the solution.