I'm a social person with lots of friends![citation needed]

Unfortunately, my friends don't really like each other. In fact, each of my friends only likes one other friend, and dislikes two others. Likes are reciprocal; if Foo likes Bar, Bar likes Foo. This poses a problem in social situations, to say the least. Each friend can be happy as long as the number of people they dislike in the current group doesn't exceed the number of people they like.

I have twenty-two friends with fixed likes and dislikes, and I want to throw a party with them, but I have to be very choosy about who I invite because if I invite everyone, nobody will be happy. I want to figure out how large the largest happy group I can invite is, and which people to invite to reach that size.

How should I go about finding that group(s)?

(I intend to turn the answer into a program and use it to search for the optimal groups.)

  • $\begingroup$ An important side note: the likes are evenly distributed (each person is liked once), but the dislikes are slightly uneven (some people are disliked three times). $\endgroup$ – Elia Apr 4 '17 at 22:05
  • $\begingroup$ Bonus: Don't tell anyone, but I like some of my friends more than others. It would be handy to be able to weight some people higher than others. (looking at you, Bob!) $\endgroup$ – Elia Apr 4 '17 at 22:05
  • $\begingroup$ Is it assumed that for each person, whoever they like as a friend does not dislike them? $\endgroup$ – Nap D. Lover Apr 4 '17 at 22:07
  • $\begingroup$ Ooh, good question. I should note that likes are reciprocal; if Jim likes Bob, Bob likes Jim. (This is purely an example. Nobody likes Bob.) $\endgroup$ – Elia Apr 4 '17 at 22:58
  • 1
    $\begingroup$ @CameronBuie No, dislikes are not commutative in any way. Alice and Bob don't need to have any dislikes in common. $\endgroup$ – Elia Apr 4 '17 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.