Hacker News Reader

Comment by lcnPylGDnU4H9OF | Hacker News Reader

If 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

View on HN

Correct 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

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

No, each edge in the graph has 2 states. There are 15 edges between the 6 people.

But the edge states don't matter, the node states do. They're either connected friends or they aren't. What's the third state?

2 groups of 3 mutual friends is a different graph than 3 pairs of friends

No, 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.

I understand that. That's the encoding of being "connected".

Where 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".

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

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

Reply on news.ycombinator.com