3
$\begingroup$

This question is influenced by the book Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh.

You are the bodyguard of a bar in a small town, and every friday night the bar is very busy. Since the town is small, you know almost everyone, and all the conflicts among people.

The conflicts are mutual. If one wants to fight another, then you cannot assume the other will stop.

Your aim is to let in as many people as you can. But the problem is, if you let a pair conflicting people in, then they will probably fight, causing a trouble.

  1. Alice and Bob are dating. Therefore, if one fights to someone, the other will also fight.

  2. Charlie and Daniel are nemeses. Thus, if one dislikes another person, the other will not fight with that person, and vice versa.

  3. Charlie is a womanizer who does not like single men to be around him while he's drinking in a friday night.

  4. Erik has no problems except Charlie. He plain doesn't like Charlie.

  5. Fred and Jennifer are a couple, and hate Bob because Bob cheated on his former girlfriend.

  6. Hillary is Bob's ex-girlfriend, and does not like Alice at all, because Bob left her for Alice.

  7. Gerald is very angry at Hillary because she is getting involved into another couple's relationship.

  8. Larry is a very good friend of Bob, but he doesn't like Alice since Alice does not let Bob to go out with Larry.

Question: Who should you let in, and who should you prevent from entering the bar in order to prevent a potential fight? Remember that you want to let in as many people as you can.

$\endgroup$
  • $\begingroup$ I take it Charlie and Daniel would not fight each other despite being nemeses? $\endgroup$ – F1Krazy Jan 18 '18 at 16:36
  • $\begingroup$ Clarification needed on this sentence: "The conflicts are mutual. If one wants to fight another, then you cannot assume the other will take it." So are the conflicts bi-directional or not? It seems to say both. $\endgroup$ – PopularIsn'tRight Jan 18 '18 at 16:51
  • $\begingroup$ I guess Charlie and Daniel would fight to death if they cross in that bar. it is better to separate them to my humble view. $\endgroup$ – Untitpoi Jan 18 '18 at 16:53
  • $\begingroup$ @Bachrach44 "other will not take it" meaning that "stand there and take it." fixed. $\endgroup$ – padawan Jan 18 '18 at 16:53
  • $\begingroup$ @padawan No names beginning with I and K? $\endgroup$ – ngn Jan 18 '18 at 17:06
4
$\begingroup$

Visual Representation

1]

It's obvious at a glance that all of the conflict is coming from

Alice/Bob and Charlie, and Hillary's and Gerald's little tiff

For obvious reasons, I'll be restricting

Alice/Bob and Charlie from entering.

Buuuut

I will allow both Hilary and Gerald to enter, based off the fact of:
Gerald is very angry at Hillary because she is getting involved into another couple's relationship.

If the couple that Hilary is getting involved with isn't there, she can't get involved, which should remove the source of conflict (if only temporarily) between H & G, thus allowing them both to enter

Final answer

D E F/J H G and L can all come into my bar, for a total of 7 ...though if H & G still decide to fight without a source of conflict being present, then I suppose it has to go down to 6, making my answer basically the same as @Untitpoi

$\endgroup$
2
$\begingroup$

My answer

There can be at most 6 person in the bar tonight and I will prevent the couple Alice and Bob from entering as they are causing a lot of trouble, I will also prevent Charlie which is a pain in the ass and finally Hillary (I could also have choosen Gerald but I think he is a good guy)

Higher number impossible

if you choose to let in 7 people then there is only three person out, as there is at least 4 pair of possible fights: Gerald and Hillary can't stand each other, Charlie and Daniel too, Bob and Jennifer and finally Alice and Larry. It is impossible to solve (At least one pair will be there to cause trouble)

In short people I will not let in

So we have A/B/C/H or A/B/C/G or B/C/H/L

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.