4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ You're right -- the proposed solution seems to be confused. Even though each senator hates only three others, it might still be that there's somebody who everybody hates. $\endgroup$
    – hmakholm left over Monica
    Commented Nov 12, 2016 at 14:00
  • $\begingroup$ This appears to be a graph coloring problem. Is there a better way to find the answer other than enumerating all the vertices and trying all possible colors? $\endgroup$
    – Donald
    Commented Nov 12, 2016 at 14:07
  • $\begingroup$ Brute-force enumeration of all possible hating patterns doesn't even sound feasible to me. $\endgroup$
    – hmakholm left over Monica
    Commented Nov 12, 2016 at 14:25

1 Answer 1

Reset to default
7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Sorry. I am unable to understand how you deduced that there is at least one senator that is hated by at most 3 others $\endgroup$
    – Donald
    Commented Nov 12, 2016 at 14:53
  • 1
    $\begingroup$ Consider the set $C$ of all "senator $x$ is hated by senator $y$" couples $(x,y)$. If there are $n$ senators, there are $3n$ such couples. If every senator $y$ appeared in $4$ or more couples of the form $(x,y)$, then $C$ would contain $4n$ or more couples! $\endgroup$
    – sTertooy
    Commented Nov 12, 2016 at 15:00
  • 1
    $\begingroup$ +1 Nice proof! But let's say that you didn't know that 7 was the optimal answer, how would you go about solving the question then? $\endgroup$
    – Donald
    Commented Nov 12, 2016 at 15:38
  • $\begingroup$ Good question! In some problems, this is very hard to determine. My way of solving would be to just try to prove it for some answer (not necessarily optimal), and once I have that done, thinking: is there some (obvious?) way to improve the proof, or does it seem unlikely? And if it seems unlikely, can I create an example where it doesn't work with less committees? In this problem here, I find that the $7$ pops up somewhat naturally when you think about the whole "$s$ hates $3$ senators and is hated by $3$ other senators" situation - it makes you suspect you need at least $7$. $\endgroup$
    – sTertooy
    Commented Nov 12, 2016 at 15:48
  • 1
    $\begingroup$ Hence you could try to prove it for $7$, find out that it works. This doesn't mean that the solution is optimal, yet. But since we suspect it is, we try to find an example where $6$ sommittees doesn't make the cut. So draw $7$ points (each representing a senator), and draw $3$ arrows from each point $x$ to another point $y$ (meaning $x$ hates $y$). Note that you can do this in a way such that there is an arrow between EVERY couple of points - meaning no two can be in the same committee. This shows that $6$ is not a possible solution, so $7$ is optimal. $\endgroup$
    – sTertooy
    Commented Nov 12, 2016 at 15:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .