Hacker News Reader

Comment by karaterobot | Hacker News Reader

>... 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?

View on HN

The '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.

I 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!

Thanks, personally I found this the easiest way to think about it!

Thanks, that clarifies it!

Maybe 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_stran...

I keep insisting so despite mounting evidence to the contrary!

Thank you for the link, this is a very good explanation.

I 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”.

If 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

One could know the Two, Two know Three but Three not know One. That's neither all knowing each other nor them not meeting.

What 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.

It's not true for 5 people if the "has met" graph is a pentagon, does your intuition here still work?

To 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?

> 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 ... ;-)

Reply on news.ycombinator.com