4 ms·
> 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 fr
by fallinditch 2y ago
> 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.
- deleted 2y ago[deleted]
- Animats 2y agoAlso see Ramsey Pricing.[1] "Ramsey pricing (for a monopolist) says to mark up most the goods with the least elastic (that is, least price-sensitive) demand or supply." That's kind of obvious. [1] https://en.wikipedia.org/wiki/Ramsey_problem https://en.wikipedia.org/wiki/Ramsey_problem
- valicord 2y agoWhy is that obvious?
- lcnPylGDnU4H9OF 2y agoIf you try, you'll find that you can't think of a configuration for which neither is true. (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 https://news.ycombinator.com/item?id=23028299
- 01HNNWZ0MV43FF 2y agoCorrect my math if I'm wrong 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
- bongodongobob 2y agoAll that is completely irrelevant, you're overcomplicating it. Each person has 1 of 2 states, connected or not. If 4 are connected, 2 aren't, if 4 aren't 2 are, etc.
- kevinwang 2y agoNo, each edge in the graph has 2 states. There are 15 edges between the 6 people.
- bongodongobob 2y agoBut the edge states don't matter, the node states do. They're either connected friends or they aren't. What's the third state?
- 01HNNWZ0MV43FF 2y ago2 groups of 3 mutual friends is a different graph than 3 pairs of friends
- lmm 2y agoNo, the connections are what matters. A may be friends with both B and C, but that doesn't mean that B is necessarily friends with C.
- bongodongobob 2y agoI understand that. That's the encoding of being "connected".
- lmm 2y agoWhere did you get "connected" from? We're talking about whether they are "a trio of mutual friends" or not; that requires them all to be friends with each other, not merely "connected".
- bongodongobob 2y agoThink about it and try to come up with a counterexample.
- valicord 2y agoJust because you can't come up with a counterexample easily doesn't make it obvious or even true. Of course in this case it is indeed true, but I'm asking what makes it obvious
- deleted 2y ago[deleted]
- deleted 2y ago[deleted]
- bongodongobob 2y agoBecause it's saying "you have 6 blocks, they can be either green or blue. No matter what colors they are, you'll always have either 3 blue or 3 green."
- yongjik 2y agoYou misunderstood the problem. That's not what it's saying at all.
- bongodongobob 2y agoHow isn't it? There's no way to have 3 connected friends and 4 unconnected friends.
- Dylan16807 2y agoYou can have all 6 connected and still be in either category. 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?
- bee_rider 2y agoWell it’s written down right there, isn’t it? Who’d have written it down if it wasn’t true? Obviously nobody would do such a thing!
- omnicognate 2y agoThe proof of that particular case goes like this: 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). [1] https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem
- deleted 2y ago[deleted]