Q7 Matemática  (IMC 2011)

Uma raça alienígena tem três gêneros: masculino, feminino e masculino. Um triplo casado consiste em três pessoas, uma de cada gênero, que gostam uma da outra. Qualquer pessoa pode pertencer a no máximo um triplo casado. Os sentimentos são sempre mútuos (se $x$ gosta de $y$ então $y$ gosta de $x$). A raça quer colonizar um planeta e envia $n$ machos, $n$ fêmeas e $n$ machos. Cada membro da expedição gosta de pelo menos $k$ pessoas de cada um dos outros dois gêneros. O problema é criar o máximo de triplos casados para que a colônia possa crescer. a) Prove que se $n$ é par e $k\ge 1/2$ então pode não haver triplo casado. b) Prove que se $k\ge 3n/4$ então pode ser formado $n$ triplo casado (isto é, todos estão em um triplo).