There are $30$ 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 $6$ other senators and is hated by exactly $6$ senators. (If senator A hates senator B, then senator B does not necessarily hate senator A). Find the smallest value of $n$ such that it is always possible to arrange the committees in a way that no senator hates another senator on his or her committee.
Yes, I know, there is already a question asked like this, but what I REALLY want is to clarify the answer of the other similar question on the site: Pigeonhole: Committee of senators who hate one another
Do you always start with $7$ when guessing the number of possible committees? Or is there a formula, or rule that states what number to start on when doing this guessing? The answer refers to something called the "induction hypothesis", but I'm not familiar about it, so it could really help if anyone explain these questions.
This question is not about finding the answer to the question in the first paragraph, but to go into detail about the method, and solution to solving this question. Any help would be wonderfully appreciated.
🙂
Best Answer
Induction is the idea that for natural numbers $\Bbb N$ (so $1,2,3 \cdots$), if we can prove a statement is true for any natural number and also for the generic number $n + 1$, then it is true for all natural numbers. The induction hypothesis, specifically, means that we prove for some minimum case (in this problem, $7$) then assume (aka, hypothesise) that it is true for some generic natural number $n$. If we can then prove that if it's true for $n$, it is always true for $n + 1$, then it is true for all natural numbers (because we proved it is true for $7$, so if we let $n = 7$ then we've proven it's also true for $8$, so for $9$, and so on.)
Your other question, on why 7, is discussed in the comments of the answer for your linked question - the answer uses 7 because the solution given in the question says 7, and then there is further discussion into how one would find that it is 7 without already knowing that - sTertooy's answer gives a very intuitive approach of why 6 or fewer would not work.