IMC 2011 · Problem 2

An alien race has three genders: male, female, and emale. A married triple consists of three persons, one from each gender, who all like each other. Any person is allowed to belong to at most one married triple. A special feature of this race is that feelings are always mutual – if $x$ likes $y$, then $y$ likes $x$.

The race is sending an expedition to colonize a planet. The expedition has $n$ males, $n$ females, and $n$ emales. It is known that every expedition member likes at least $k$ persons of each of the two other genders. The problem is to create as many married triples as possible to produce healthy offspring so the colony could grow and prosper.

a) Show that if $n$ is even and $k = \dfrac{n}{2}$, then it might be impossible to create even one married triple.

b) Show that if $k \ge \dfrac{3n}{4}$, then it is always possible to create $n$ disjoint married triples, thus marrying all of the expedition members.