I am trying to solve the following problem:
There are 51 senators in a senate. The senate needs to be divided into $n$ committees such that each senator is on exactly one committee. Each senator hates exactly three other senators. (If senator A hates senator B, then senator B does 'not' necessarily hate senator A.) Find the smallest $n$ such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee.
The provided solution is as follows:
In the worst case, consider that senator $S$ hates a set of 3 senators, while he himself is hated by a completely different set of 3 other senators. Thus, given one senator, there may be a maximum of 6 other senators whom he cannot work with. If we have a minimum of 7 committees, there should be at least one committee suitable for the senator $S$ after the assignment of the 6 conflicting senators.
I don't understand why the worse case involves 3 other senators hating the original senator. I don't get how they derive the value 3. Could anyone please advise me?
The solution is not very clear, but it has the right ideas! There are $51$ senators, and each hates $3$ people. By the pigeonhole principle, there must be at least one senator who is hated by at most 3 other senators. However, the rest of the proof isn't exactly very clear either.
Let us work by induction, stating that $7$ committees are enough. For $n \leq 7$ senators that obviously is the case.
Now suppose we can put any $n$ senators in $7$ committees (induction hypothesis). We prove that we can do the same for $n+1$ senators. Let us call the set of senators $S$. By the pigeonhole principle, we have a senator $s$ hated by at most $3$ other senators. Now consider the set $S \setminus \{s\}$ of the $n$ other senators. Each of them hates (at most*) $3$ other senators, so we may apply the induction hypothesis and divide the senators in $S \setminus \{s\}$ over $7$ committees.
Now, senator $s$ is hated by at most $3$ other senators, and himself hates $3$ senators. So there are $6$ people he cannot be in a committee with, but there are $7$ available committees to put him in.
(*) Because some of them perhaps hate senator $s$, who is excluded in this situation.