6 ms·
>... if the room has at least six people, you can say something about them with absolute mathematical certainty... [that it contains] either a group of three wh
by karaterobot 6y ago
>... if the room has at least six people, you can say something about them with absolute mathematical certainty... [that it contains] either a group of three who all know each other, or a group of three who have never met.
Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
- hoseja 6y agoOne could know the Two, Two know Three but Three not know One. That's neither all knowing each other nor them not meeting.
- enkid 6y agoWhat he's saying is that there is at least one set where they all know each other or they all don't know each other, not that any set of three will be that way.
- strgcmc 6y agoMaybe you're not dense, maybe you're just such a genius that pigeonhole principle proofs seem naturally obvious and tautologically true to you? :-) I found this enlightening (particularly "Sketch of a Proof"), though I also admit that it seemed fairly straightforward, with elegance borne of simplicity rather than of brilliance or cleverness: https://en.m.wikipedia.org/wiki/Theorem_on_friends_and_strangers https://en.m.wikipedia.org/wiki/Theorem_on_friends_and_stran...
- karaterobot 6y agoI keep insisting so despite mounting evidence to the contrary! Thank you for the link, this is a very good explanation.
- karmakaze 6y agoThe 'who have never met' isn't the opposite of 'all know each other', it's no two people of these three know each other. The opposite would be don't all know each other. If you imagine a six vertices arranged around a point and make any number of edges connecting them to represent knows each other. For any choice of edges, you can either find 3 vertices that are fully connected or you can find three vertices that have no connections.
- bloat 6y agoI would describe it as follows, maybe a little easier to visualize. Draw six dots, draw either a red or a blue line from every dot to every other dot. You must draw either a completely red triangle or a completely blue triangle. Personally I don't think it sounds intuitive when stated like that!
- austinjp 6y agoThanks, personally I found this the easiest way to think about it!
- karaterobot 6y agoThanks, that clarifies it!
- q-big 6y ago> Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing? If this seems so trivial to you, simply write down the proof. If you are not really mathematically gifted, you will soon see where the problem is ... ;-)
- dooglius 6y agoIt's not true for 5 people if the "has met" graph is a pentagon, does your intuition here still work?
- alanbernstein 6y agoTo a robot, all mathematical truths are tautologies, right? Perhaps you could imagine reading that statement with both occurrences of "three" replaced with blanks. Do you think you could confidently fill them in without more than a moment's thought?
- Moodles 6y agoI can’t get in your head to know what you’re thinking so maybe it is obvious to you, but just in case you don’t fully understand: it may not be obvious that its impossible to have a configuration where in the 20 possible groups of 3, someone always knows someone else but not everyone knows everyone? The theorem isn’t really saying “it’s A or not A”. It’s saying: “it has to be A or B and not anything else”.
- 8note 6y agoIf you pair everyone off, either all three groups are disjoint, or some of the groups are connected. If you don't pair people, you end up with 2 completely disconnected people and also at least one more person that's not connected to either Obviously if you make a group bigger than a pair, you also end up with 3 connected people