12 ms·
Why is that obvious?
by valicord 2y ago
Why 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".
- sixfiveotwo 2y agoIn this encoding of the problem, the graph is fully connected, the edges indicate the state of a connection (ie. friendship) between 2 users, and the goal is to check that there is either a chain of 2 "connected" edges (A to B and B to C for any A,B,C in the nodes) or 2 "disconnected" edges, which indeed isn't easy to do the tedious way. 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.
- Izkata 2y agoThe simple version: Among 6 people, to avoid a trio of friends, no sub-group can be 3 or more. Maximize the size of the sub-groups to minimize the number of non-friends: 2 + 2 + 2. One from each sub-group is a trio of non friends. 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.
- 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!