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

1. August 4, 2011 at 6:20 pm

I think this problem is not the case in question a), may be k> = n / 2 rather than k> = 1 / 2. Be sure to check back and see more here http://www.mathdoi.com/2011/07/de-thi-olympic-toan-sinh-vien-quoc-te-nam-2011-imc-2011-problems-of-2st-day/

• August 4, 2011 at 10:16 pm

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