3 ms·

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 combination

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

bongodongobob 2y ago
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.
- kevinwang 2y ago
  No, each edge in the graph has 2 states. There are 15 edges between the 6 people.
  - bongodongobob 2y ago
    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?
    - 01HNNWZ0MV43FF 2y ago
      2 groups of 3 mutual friends is a different graph than 3 pairs of friends
    - lmm 2y ago
      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.
      - bongodongobob 2y ago
        I understand that. That's the encoding of being "connected".
        lmm 2y ago
        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".
    - sixfiveotwo 2y ago
      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.
Izkata 2y ago
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.

bongodongobob 2y ago

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.

kevinwang 2y ago
No, each edge in the graph has 2 states. There are 15 edges between the 6 people.
- bongodongobob 2y ago
  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?
  - 01HNNWZ0MV43FF 2y ago
    2 groups of 3 mutual friends is a different graph than 3 pairs of friends
  - lmm 2y ago
    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.
    - bongodongobob 2y ago
      I understand that. That's the encoding of being "connected".
      - lmm 2y ago
        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".
  - sixfiveotwo 2y ago
    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.

Izkata 2y ago

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.