This one came up on the problem widget (lower right) a while ago. I've been struggling with it.
A town creates a committee of six people to solve a new math problem. In the town, everyone is either a friend or an enemy. Prove that there are at least three friends or three enemies on the committee.pic by Alana
Posts
5 comments:
That is non-trivial! You need to draw some 2-color graphs and use the pigeon-hole principle.
No kidding! It's been fun. Tell you the truth it has been a while since I worked on it. (School/life got in the way) I forgot exactly where I am. I think I'm down to the toughest case or two.
Another way to think of it is that you are proving the Ramsey number for 3 is 6. The Ramsey number for 4 is known (I forget what it is), but for 5 it is unknown! We just have it narrowed down to a range of values. There is a funny story about Paul Erdos, he said, if aliens visited Earth and demanded we tell them the Ramsey number for 5 or else they would blow us up, we should get all the greatest minds on the planet together and figure it out. However if they made the same ultimatum demanding the Ramsey number for 6, we should get all the greatest minds together to figure out how to blow them up first.
Great story, Kate. I'm sure I wouldn't make the short-list of the save the world summit. I am planning to look up what a Ramsey Number is. Thanks for making me smarter. I'll stay away from aliens in the mean time.
I think that for a man about whom whole books of charming stories have been written, that that story is my favorite.
Post a Comment