Pigeon groupings Question:There are $51$ pigeons in a flock. The flock is divided into $n$ groups so that each pigeon is in exactly $1$ group. However, every pigeon dislikes exactly $3$ pigeons and thus does not want to be in the same group as the $3$. Find the smallest number $n$ such that it is always possible to arrange the groups so that no pigeon is uncomfortable with the groupings.
Note: Even if, for example, pigeon $A$ dislikes pigeon $B$, pigeon $B$ does not necessarily dislike pigeon $A$.
I just want to check my answer, is it 5? thanks Edit: 5 is wrong and my new solution is listed at the end of my proof.
My solution:
Let the pigeons that pigeon $a_i$ hates be $a_{i+1}, a_{i+2}, a_{i+3}$ and let $a_{i+51} = a_{i}.$
Now we can make the groups. With group 1, we can let $a_1$ be in it. The next pigeon that can be in the group is $a_5.$ In general we can put the pigeons in the form $a_{1+4n}$ except $a_{49}$ since $a_{49}$ hates $a_1.$ Therefore, group 1 has 11 members.
Moving on to group 2, we put $a_2$ in it. Like the first group the pigeons in the form $a_{2+4n}$ can be in group 2 except for the last pigeon which hates $a_2.$
We can redo these procedures for groups 3 and 4. We cannot do it for group 5.However we still have $a_{49}, a_{50}, a_{51}$ left over. The dislike each other however, so we need to put them in separate groups.
Therefore the minimum groups is $\boxed{7}.$
 A: The minimum number of groups is $7$.
Proof: We first show that we need no more than $7$ groups, by induction. Let $p$ denote the number of pigeons; clearly the claim hold for $p=7$. Now, suppose it holds for some $p=k$. When we have $k+1$ pigeons, there must be at least one pigeon which is disliked by at most $3$ pigeons. Remove this pigeon, and group the remaining $k$ pigeons into $7$ groups. Reintroducing the removed pigeon, we see that it dislikes $3$ others, and is disliked by at most $3$, hence there must be at least $7-(3+3)=1$ group into which this pigeon can fit. This concludes the argument, by induction.
To see why we need at least $7$ groups, consider a graph with vertices $a_0,\dots, a_6$ and a directed edge between $a_i$ and $a_{i+1},a_{i+2},a_{i+3}$, with the indices taken$\mod 7$. This arrangement would clearly require at least $7$ groups (draw it!), and could certainly appear as a subgraph of any pigeon setup, regardless of the number of pigeons.
Still curious? Look into graph colorings, you'll find many more similar problems!
