Another puzzle...
There are six people in a group. If you consider any two people in the group, they are either friends to each other, or strangers to each other. Prove that there must exist three people in the group who are mutual friends or mutual strangers.
And now for the challenge puzzle.
There are seventeen people in a much unfriendlier group. If you consider any two people in the group, they are either friends, strangers, or rivals to each other. Prove that there must exist three people in the group who are mutual friends, mutual strangers, or mutual rivals.
(See the solution)
Monday, April 6, 2009
Subscribe to:
Post Comments (Atom)
5 comments:
Yay, Ramsey theory! These are good puzzles, but I'll leave their solutions to someone who has not seen them before.
Ok, the first was easy to show graphically (once I realised that A being friendly with B didn't imply that A was friendly with B's friends) but I was looking for a less clumsy way of proving it. Then I saw that, like any good drama, it was all about triangles.
With 6 people, person A (or any other) will have a relationship with 5 others (though that might be "stranger"). With two possible choices for the relationship, there must be at least three that are the same. Let's say that A is friendly with 3 others - B, C, D. We can draw lines joining A to each of the
three.
If any of B-C, B-D, or C-D are friendly, they will be mutually friendly with A (shown by drawing the line and closing the triangle). Therefore, if not friendly, they must all be strangers to each other and thus a group of three mutual strangers. The reasoning is mirrored if we assume that A is a stranger to B, C, and D.
The case of 17 people and 3 types of relationship can follow on from this reasoning by adding another level.
This time each person has a relationship with 16 others. Let's pick one and call him Z. There must be one type of relationship that he has with at least 6 others. Let's call them A, B, C, D, E, and F and say that Z is a rival to each of them (and them to him).
If we're going to draw this graphically, it might be easier to use colours so we could draw red lines from Z to each of A-F. We need colours for the other two relationships - green is nice and friendly, and sinople not only sounds strange but can also be either red(dish) or green depending on the context. (Perhaps red and green are in superposition and it only resolves to friendship or rivalry after you try and establish (measure) the relationship ;-)
We have already shown that for any group of six people (A-F), there must exist at least one mutual group of three if we're restricted to two types of relationship (friends and strangers); so if we are to try and avoid this, one of the relationships between at least one pair of A-F must be that of rivalry. However, this would then make them mutually rivalrous with Z.
It follows that if a 4th type of relationship is introduced, the minimum number of people required to ensure at least one mutual group of three, is 66 (and 327 for 5, etc).
Hm, I've thought about this some more (well, my subconscious started to) and I think my proposals for the 4 relationship and 5-R scenarios are merely upper bounds. In fact, I'm sure of it but have no proof.
I neglected to consider relationships between members of different "subnets" when I was levelling up. For 4-R, I'm pretty sure a mutual triangle must exist with only 64 people, maybe less but I'm not motivated to check it out. It follows that the same will occur for 5-R with a lot less than 327 people but I'm not even going to hazard a guess.
Oh, all right, under 200.
Secret Squirrel, don't feel bad that you've only got upper bounds for the 5 version. As one of my math professors used to quote Erdös (if I'm not misquoting or misattributing him), "If an alien were to come down to Earth and tell us we had one year to find the Ramsey number for 5 [the number of guests needed in order to guarantee a group of five mutual friends or five mutual non-acquaintances] or else he would destroy the planet, then we should spend the year devoting every computer on the planet to the task. If the alien gives us one year to find the Ramsey number for 6, then we should spend the year trying to figure out how to kill the alien."
In other words, nobody has anything better than a huge upper bound for those cases. The whole field of Ramsey theory is notorious for posing very simple questions involving small numbers, for which the best know solutions are impossibly large.
Thanks, intrinsically knotted. I hadn't heard of Ramsey or his Theory before but that's a great quote - helps put things in perspective.
You mentioned the Ramsey number for 5 (and implied that it hasn't been determined yet) and then clarified that it's for 5 mutual relationships with (presumably) "friends" and "strangers" as the only two types. I was extending miller's puzzle to 5 relationship types but still requiring only 3 mutuals. I'm assuming that these would not be the same numbers.
I hadn't even thought about increasing the number of required mutual relationships while keeping the number of relationship types constant. I might think about the case for 4 mutuals with only 2 types (presumably this would be the "Ramsey number for 4").
Post a Comment