Hacker News new | ask | show | jobs
by lcnPylGDnU4H9OF 702 days ago
In that case, would you mind writing a more enlightening comment?
3 comments

It's probably most clearly stated in the original post, but the point is you would either be able to find three people who are all friends with the other two, or you would be able to find three friends who are not friends with any of the others. The non-obviousness is due to the fact that someone may have only one friend, or someone may have two friends but those two would not be friends with each other, so I wouldn't call it blindingly obvious that there would always be a subset with one of these properties (I think the main intuition that is useful is that if you have a sparsely connected graph of friends, it's easy to find a group that aren't friends at all, and if you have a densely connected graph then you can find a group that are mutual friends. The theorem is then proving that there's no middle ground: it's either dense enough a mutual group must exist or sparse enough a non-friend group must exist.)
Does this formulation work?

You have 6 wooden blocks, each can be 1 of 6 colors. There will always be either (A) 3 blocks of the same color, or (B) 3 blocks of different colors.

Iterating through all possibilities:

6 of 1 color - case A

5 of 1 color, 1 of another - case A

4 of 1 color, 2 of another - case A

4 of 1 color, 1 of another, 1 of yet another - case A and B

3 of 1 color, 3 of another - case A

3 of 1 color, 2 of another, 1 of yet another - case A and B

3 of 1 color, 1 of another, 1 of yet another, 1 of another another - case A and B

2 of 1 color, 2 of another, 2 of yet another - case B

2 of 1 color, 2 of another, 1 of yet another, 1 of another another - case B

2 of 1 color, 1 of another, 1 of yet another, 1 of another another, 1 of another another another - case B

all colors different - case B

Your formulation is not equivalent. The actual Ramsey theory formulation is something more like...you need to color, either red or blue, all of the edges of a fully connected graph of 6 elements (there are 15 such edges). No matter which coloring you choose (there are 2^15 of these), there will always be a "triangle" between three nodes where the entire triangle is either fully red, or fully blue. If you were to instead restrict yourself to a graph with 5 elements instead of 6, it's possible[1] to color the edges so there's no triangle where all the elements are the same.

As an exercise, try repeating your same argument for 5 colors/blocks, and note that it still works, when it shouldn't.

[1] - https://commons.wikimedia.org/wiki/File:RamseyTheory_K5_no_m...

In your version, the color of a vertex is independent of other vertices. The real problem is about entirely about connections to other vertices. The latter cannot be reduced to the former.