Home > Olympiad > IMC 2011 Day 2 Problem 2

## IMC 2011 Day 2 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. The feelings are always mutual ( if $x$ likes $y$ then $y$ likes $x$).

The race wants to colonize a planet and sends $n$ males, $n$ females and $n$ emales. Every expedition member likes at least $k$ persons of each of the two other genders. The problem is to create as many married triples so that the colony could grow.

a) Prove that if $n$ is even and $k\geq n/2$ then there might be no married triple.

b) Prove that if $k \geq 3n/4$ then there can be formed $n$ married triple ( i.e. everybody is in a triple).

Yes, you are right. There was $k/2$ instead of $1/2$. Thank you for your correction.