Problem

Source: 2017 Saudi Arabia IMO Training Test p2

Tags: combinatorics



There are $4950$ ants. Assume that, for any three ants $A, B$ and $C$, if the ant $A$ is the boss of the ant $B$, and the ant $B$ is the boss of the ant $C$ then the ant $A$ is also the boss of the ant $C$. We want to divide the ants into $n$ groups so that in any group, either any two ants have the boss relationship or any two ants do not have the boss relationship. Find the smallest of $n$ we can always do in any case.