tag:blogger.com,1999:blog-4115025577315673827.post922081657628584709..comments2020-05-25T13:34:36.365+05:30Comments on CSE Blog - quant, math, computer science puzzles: Senators and Graph TheoryPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-4115025577315673827.post-68104605675640957832012-07-26T12:56:30.571+05:302012-07-26T12:56:30.571+05:30I think the answer is 7. Now that we have the cond...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:<br /><br />1 - 2,3,4<br />2 - 7,6,5<br />3 - 2,7,6<br />4 - 3,2,7<br />5 - 1,4,3<br />6 - 1,4,5<br />7 - 1,5,6<br /><br />For the above arrangement n<7 fails. So n = 7.Anonymoushttps://www.blogger.com/profile/06503740596277603928noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-12404142980247408842010-11-12T05:10:37.000+05:302010-11-12T05:10:37.000+05:30@sai tej pratap:
I know. I realized that later but...@sai tej pratap:<br />I know. I realized that later but I wasn't able to delete my comments :DKrish reddyhttps://www.blogger.com/profile/14544861965015449705noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-35334751367672395562010-11-10T23:44:53.735+05:302010-11-10T23:44:53.735+05:30@krish
"Each senator can be atmost surrounded...@krish<br />"Each senator can be atmost surrounded by 6 other colors (i.e. senators he hates and is hated by)<br />ANSWER: 7 (6+1 i.e. his color)"<br /><br />A senator can be hated by any number of senators.There is no restriction on that.stphttps://www.blogger.com/profile/08966664548209965371noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-3057825730872546602010-10-23T05:33:48.430+05:302010-10-23T05:33:48.430+05:30This comment has been removed by the author.Krish reddyhttps://www.blogger.com/profile/14544861965015449705noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-9212937300773512892010-10-23T04:22:43.309+05:302010-10-23T04:22:43.309+05:30@chera you're right.
Looks like a typical &quo...@chera you're right.<br />Looks like a typical "graph coloring problem"<br />I didn't look at your solution but after I solved it I read your comments and realized you described the same approach.<br />It's basically we have 51 vertices and each vertex will be connected to 45 other ones in the worst case. <br />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.<br />Consider we divided senators into n groups and give each group a color and then mix them all together. <br /><br />Each senator can be atmost surrounded by 6 other colors (i.e. senators he hates and is hated by)<br />ANSWER: 7 (6+1 i.e. his color)<br /><br />Another perspective:<br />After coloring and mixing them, how many senators should you pick to have two of them from the same group?<br />atleast 8 i.e. 7 different colors<br /><br />CAUTION: surrounding senators with different colors will be a disaster :DKrish reddyhttps://www.blogger.com/profile/14544861965015449705noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-25223676176285526892010-10-14T14:41:26.134+05:302010-10-14T14:41:26.134+05:30the guess came after a lot of trial and error. The...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.cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-88595948255993477422010-10-14T13:52:54.838+05:302010-10-14T13:52:54.838+05:30@chera
hw did you guess that 7 can be the answer@chera<br /><br />hw did you guess that 7 can be the answerstphttps://www.blogger.com/profile/08966664548209965371noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-9385865557829184352010-10-14T06:47:53.911+05:302010-10-14T06:47:53.911+05:30Sorry my bad for the previous solution.Actually n=...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.Ankushhttps://www.blogger.com/profile/09691343611737045503noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-88263476112190185422010-10-14T06:38:59.929+05:302010-10-14T06:38:59.929+05:30Narrowed the solution down to 4,5,6.
1)n>=4.Si...Narrowed the solution down to 4,5,6.<br /><br />1)n>=4.Simple case where 4 people mutually hate each other.<br /><br />2)n<=6<br />Consider the senators to be nodes with an undirected edge between two nodes if either<br />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.<br /><br />I have a strong reason to believe that it is 4,although there is no proof :(Ankushhttps://www.blogger.com/profile/09691343611737045503noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-41236847173671194702010-10-12T20:22:17.494+05:302010-10-12T20:22:17.494+05:30nikhil,
ur example is right. It shows that in cer...nikhil,<br /><br />ur example is right. It shows that in certain cases (but not all), it is possible to make do with 2 committees.<br /><br />But in most cases 2 committees will not suffice. I had given an example of a case where even six committees will not suffice .<br /><br /> <br />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.<br /><br />If we take n=7, i have shown that seven committees can be always arranged in all the cases.cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-5806731903667728952010-10-12T19:47:24.647+05:302010-10-12T19:47:24.647+05:30CHERA whats wrong with this -
1,2 and 3.Each of t...CHERA whats wrong with this -<br /> 1,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?Nikhilhttps://www.blogger.com/profile/17696469472623001962noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-35767725142200436772010-10-12T18:37:12.995+05:302010-10-12T18:37:12.995+05:30in my previous post, it was proved that 7 committ...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.<br /><br />Proof: Label the senators 1,2,.....51. <br /><br />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. <br /><br />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.cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-42514904631856311922010-10-12T16:30:53.506+05:302010-10-12T16:30:53.506+05:30I think I have a proof that n <=7.
The proof ...I think I have a proof that n <=7.<br /><br />The proof is by induction on the number of senators N. <br /><br />Label the senators as 1,2,3.....N.<br /><br /> if N=7, then it is clear that 7 committees, consisting of one senator each will do. <br /><br />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. <br /><br />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). <br /><br />Consequently, by pigeonhole principle, he can be placed in one of the 7 committees. Which completes the proof.cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-46042329478594097852010-10-12T16:07:51.170+05:302010-10-12T16:07:51.170+05:30I don't have a solution. Could not solve it.I don't have a solution. Could not solve it.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-69575518221428154312010-10-12T15:58:40.671+05:302010-10-12T15:58:40.671+05:30Is it 4 ?Is it 4 ?Nikhilhttps://www.blogger.com/profile/17696469472623001962noreply@blogger.com