> Ramsey theory tells us, for instance, that among any six users of Facebook there will always be either a trio of mutual friends or a trio in which none are friends.
AKA Ramsey's Theory of the Bleedin' Obvious.
AKA Ramsey's Theory of the Bleedin' Obvious.
Pick one of the six users. Split the other 5 users into friends and non-friends of the chosen user. There will either be at least 3 friends or at least 3 non-friends of the chosen user. If you can pick 3 friends of the chosen user then if any two of them are friends they plus the original user form a trio of mutual friends. If none of the 3 are friends then you have a trio in which none are friends. Similarly, if you can pick 3 non-friends of the original user then either two of them are non friends and you have a trio of non friends or all three are friends, forming a trio of mutual friends.
It's easy to prove but I don't think I'd quite call it "bleedin' obvious". Ramsey's theorem [1], of course, is more general than that and isn't at all obvious (although it's still not very hard to prove).
(Maybe it's not "obvious" but it's easy to arrive at that conclusion after some thought.)
This comment from the other linked discussion describes what was actually proved; the narrow case of facebook friends is just a given example. https://news.ycombinator.com/item?id=23028299
6 people have 6 * (6 - 1) / 2 = 15 possible connections. If you toggle those off and on you have about 2 ^ 15 = 32,768 combinations.
Some of those are surely redundant but I don't know stats well enough to de-dupe them.
Either way I feel like it's higher than I can count in my head while also doing anything else mathematical
The crucial property here is the symmetry between connected and disconnected edges: for any given configuration, if it's difficult to check it on one hand, then it should be easy to do it on the other.
So either you have enough sub-groups to create a trio of non-friends, or there's a sub-group large enough to create a trio of friends.
For example, 6 friends in a loop can be divided into even and odd trios, where each trio has no direct friend connections within it.
But six people in two separate triangles fall into the other category, with two trios of mutual friends.
Notice how both of these cases give each person 2 friends. It's not nearly as simple as assigning everyone a color at the start.
Another thing to think about: If you have a triangle of 3, and a line of 3, then you can find 3 mutual friends and three mutual non-friends. How would you use colors to differentiate this situation from the two-triangles situation?
It's not "you have a group of 3 or you don't".
You can have all six people tangled up in lots of different combinations, so how do you prove there's a way to pick three that only connect indirectly?
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
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...
But with 6 nodes you must have a triangle that is all the same color. It is the edges that are colored, not the nodes.