USA IMO

The smallest such number is $7$. Assume that there are $7$ senators $A_1,\dots ,A_7$ such that each $A_i$ hates $A_{i+1}$, $A_{i+2}$, and $A_{i+3}$ (where indices are taken modulo $7$). In this situation, for any different $A_i,A_j$, either $A_i$ hates $A_j$ or vice versa. The senators $A_1,\dots ,A_7$ must be placed on seven different committees. Thus, $n\ge 7$.

In order to show that $n\le 7$, we will prove the following stronger statement by induction on $k\ge 1$: for $k$ senators, each of whom hates at most $3$ others, it is possible to arrange the senators into $7$ committees so that no senator hates another senator on his or her committee.

For the base case $k=1$, note that we can have $7$ committees, $6$ of which are empty and $1$ of which contains the sole senator.

Now assume the claim is true for all $k\le m-1$. Suppose we are given $m$ senators, each of whom hates at most $3$ others. If each of those $m$ senators is hated by more than $3$ others, then the total number of acts of hating must be greater than $3m$, but this is not possible since each senator hates at most $3$ others. Therefore, there must be at least one senator $A$ who is hated by at most $3$ others. By the induction hypothesis, we can split the $m-1$ other senators into $7$ committees satisfying the property that no senator hates another senator on the same committee. By the Pigeonhole Principle, one of those committees contains neither a person whom $A$ hates nor a person who hates $A$. We can therefore place $A$ in that committee. The induction is complete.