Hacker News Reader

Comment by 01HNNWZ0MV43FF | Hacker News Reader

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

View on HN

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.

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.

Reply on news.ycombinator.com