Senators and Graph Theory
Source: Asked to me by Sai Teja Pratap (Sophomore Undergraduate, CSE, IITB)
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.
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.
Is it 4 ?
ReplyDeleteI don't have a solution. Could not solve it.
ReplyDeleteI think I have a proof that n <=7.
ReplyDeleteThe proof is by induction on the number of senators N.
Label the senators as 1,2,3.....N.
if N=7, then it is clear that 7 committees, consisting of one senator each will do.
Now suppose that 7 committees can be arranged for N-1 senators. We need to show that 7 committees can be arranged for N senators.
Let ai = number of persons who hate senator i. Then a1+a2+....+aN=3N. Hence there is a senator k, such that ak<=3. Now consider the N-1 senators excluding senator k. By induction hypothesis, 7 committees can be arranged for these (N-1) senators. As ak<=3, this senator k is incompatible with atmost 6 senators (note that he hates 3 senators and he is hated by at most 3 senators, as ak<=3).
Consequently, by pigeonhole principle, he can be placed in one of the 7 committees. Which completes the proof.
in my previous post, it was proved that 7 committees are sufficient. Below an example is created to show that at least 7 committees are needed. Proving that n=7.
ReplyDeleteProof: Label the senators 1,2,.....51.
Consider the first seven senators 1,2,3,.....7. Suppose senator a hates senator a+1,a+2 and a+3 [mod7], i.e. senator 1 hates senator 2,3, & 4, senator 2 hates senator 3,4&5,….senator 6 hates senator 7,1&2, and senator 7 hates senator 1,2&3.
Then it is easy to see that all the seven senators 1,2,….7 are pairwise incompatible. Thus no two of these 7 senators can be in same committee. Therefore, irrespective of preference of other 44 senators, at least 7 committees are needed.
CHERA whats wrong with this -
ReplyDelete1,2 and 3.Each of them hates say 4,5 and 6(or any 3 from 4 to 51).From 4 to 51..each hates 1,2 and 3.so can we club them in two comm. just A and B?
nikhil,
ReplyDeleteur example is right. It shows that in certain cases (but not all), it is possible to make do with 2 committees.
But in most cases 2 committees will not suffice. I had given an example of a case where even six committees will not suffice .
if we take n=47, then it is clearly true that in all cases we can form n=47 committees consisting of one member each. We are trying to find the smallest n such that n committeess can always be arranged.
If we take n=7, i have shown that seven committees can be always arranged in all the cases.
Narrowed the solution down to 4,5,6.
ReplyDelete1)n>=4.Simple case where 4 people mutually hate each other.
2)n<=6
Consider the senators to be nodes with an undirected edge between two nodes if either
of them hates each other. The maximum degree of this graph is 6 and hence by Brooks theorem(http://en.wikipedia.org/wiki/Brooks%E2%80%99_theorem) the chromatic number(n in this case)<=6.
I have a strong reason to believe that it is 4,although there is no proof :(
Sorry my bad for the previous solution.Actually n=7 is correct.(In Brooks theorem the graph has to be connected and in this case the graph need not be). Totally agree with chera for the n=7 case.
ReplyDelete@chera
ReplyDeletehw did you guess that 7 can be the answer
the guess came after a lot of trial and error. The basic idea is that if we can create a maximal set of senators who are all pairwise incompatible, then we will need to put them in different committees. I considered a symmetric pattern of n senators around a circle in which each senator hates next 3 and is hated by previous 3. if we choose n=7,then all the seven senators are pairwise incompatible. but if we choose more than 7 senators in a circle then they will not be all pairwise incompatible.
ReplyDelete@chera you're right.
ReplyDeleteLooks like a typical "graph coloring problem"
I didn't look at your solution but after I solved it I read your comments and realized you described the same approach.
It's basically we have 51 vertices and each vertex will be connected to 45 other ones in the worst case.
Now we want to partition this graph into subgraphs such that all vertices in the a subgraph are connected to all others in the same subgraph.
Consider we divided senators into n groups and give each group a color and then mix them all together.
Each senator can be atmost surrounded by 6 other colors (i.e. senators he hates and is hated by)
ANSWER: 7 (6+1 i.e. his color)
Another perspective:
After coloring and mixing them, how many senators should you pick to have two of them from the same group?
atleast 8 i.e. 7 different colors
CAUTION: surrounding senators with different colors will be a disaster :D
This comment has been removed by the author.
ReplyDelete@krish
ReplyDelete"Each senator can be atmost surrounded by 6 other colors (i.e. senators he hates and is hated by)
ANSWER: 7 (6+1 i.e. his color)"
A senator can be hated by any number of senators.There is no restriction on that.
@sai tej pratap:
ReplyDeleteI know. I realized that later but I wasn't able to delete my comments :D
I think the answer is 7. Now that we have the condition n<=7, there is one case where n<7 fails. so n = 7. The arrangement is:
ReplyDelete1 - 2,3,4
2 - 7,6,5
3 - 2,7,6
4 - 3,2,7
5 - 1,4,3
6 - 1,4,5
7 - 1,5,6
For the above arrangement n<7 fails. So n = 7.