27
$\begingroup$

You have invited $2017$ of your acquaintances to a party. But after they all arrive, you come to know from a reliable source that each of your guests is either a troll or a true friend. You don't know who is what, but you do know the following:

  1. A true friend always tells the truth in answer to any yes/no question.

  2. A troll gives a random response, which may be true, false, or neither.

  3. Each of your guests know which of the guests are trolls and which are not.

Now obviously you don't want a bunch of trolls in your party, so you decide to play a party game.

In every round, you give a card to each of the guests present, which has a yes/no question written on it; you may ask different questions to different guests. After handing out the cards, you listen to the answers of the guests, and then expel a single guest, who then cannot return to the party. Note that you must expel someone in order to continue to the next round. The door through which the guest exits is fitted with a troll detector; whenever a person passes through the door, it shows whether the person is a troll or a true friend. After the guest goes out, you begin another round of the same procedure.

You may stop the game at any moment. But if you chance to turn out more than one true friend, you'll be deemed a social failure and nobody will ever come to you party again.

Can you make sure that all the trolls are expelled, without losing your social reputation?

Adapted from Tournament of Towns, Spring 2015.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Do we know that at least one guest is a troll and at least one guest is a true friend? If all the guests are true friends, you will fail after the first round since "expel a single guest" is a required action. $\endgroup$ – Jakob Pamp Bengtsson Mar 6 '17 at 12:30
  • 2
    $\begingroup$ If trolls give "random" responses, is it possible for them to answer 'green' to a yes/no question? $\endgroup$ – Falc Mar 6 '17 at 22:59
  • 2
    $\begingroup$ @n00dles: If the question is intended to be a logic puzzle, it need not be subjective. I would suggest that questions be those equivalent to "Does the pattern of friends and trolls here match any of the ones in this list?" If there are many people present, such a formulation may be unwieldy but any question whose answer would be unambiguous and relevant could be formulated in such manner. $\endgroup$ – supercat Mar 7 '17 at 0:43
  • 2
    $\begingroup$ @Falc yes, it's possible; but you may safely assume they don't, since such a response would only make your task easier. $\endgroup$ – Ankoganit Mar 7 '17 at 4:43
  • 3
    $\begingroup$ Or use the troll detector door as the entrance. Then you can get on with the party without the game. $\endgroup$ – Reuben Mallaby Mar 7 '17 at 17:27
30
$\begingroup$

Solution:

You number all of them 1 to 2017.
You ask all of them "Is 1 a troll?".
|---They all answer yes, you kick 1 out.
|---|--- He was a troll, start over with 1 fewer trolls.
|---|--- He was not a troll, kick everyone out. they are all trolls.
|---at least one answers No. Kick the first one that said NO.
|---|--- He was a troll, go to next one or start over if needed.
|---|----He was not a troll you know 1 is one true friend.

This was about the same thing I said before.
But now...

put the one true friend you found as first and reassign them numbers again.
ask the question "Is the one with the number you have +1 a troll?". This is equivalent to "ask x if x+1 is a troll". (you don't care what the last one answers).
Because 1 is a true friend, you know if 2 is troll or not for sure.
!---if 2 is troll, kick him out and restart.
|---if 2 is not troll, move on to 3 and apply the same logic.
the condition above resumes to... the first one that says "Yes, the next one is a troll", believe him and kick the next person, then move on to the next round with the same question.
Repeat this until everyone says. "No, the next person is not a troll".

See Trenin's answer for a different formulation of the same approach, in case that one is easier to understand.

Previous attempt at solution:

The idea is to find one attendee that is certainly not a troll and don't eliminate him.
If you find one then you can ask him (and everyone else but everyone else's answer you can ignore) about each one of the other attendees.
And here is how you can do that.
You give them all numbers 1 to 2017.
Ask the question. "Is 1 a troll". And ignore the answer 1 gives.
|---If they all answer "Yes" you throw 1 out.
|----|---if it turns out to be a troll, shift their numbers (2 becomes 1 and so on) and restart the process.
|----|---if he is not a troll it means all the others are trolls and you kick them out. So you threw everyone out and only one was not a troll. You keep your social reputation
|---if one (or more) answer "No", you kick out the first one that said no.
|---|---if he is a troll, move on to the next one that said no or restart the process with 1 less troll.
|---|---if he is not a troll it means 1 is not a troll and you found the one you needed.

Corner case (reasoning above still works in this case, I'm just explaining here that you don't need to know if there is at least 1 troll and 1 true friend at the party):

If you repeat the first step and keep asking "Is 1 a troll" and you throw 1 out and it turns out to be a troll, you end up with 1 attendee that always answers "Yes" and you don't care if he is a troll or not, you just throw him out because he is the expendable one.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Seems I misread the question - I thought no friends were expendable! Your answer makes nice use of the fact. $\endgroup$ – Jakob Pamp Bengtsson Mar 6 '17 at 12:56
  • $\begingroup$ I see a small hole here; suppose you found a true-friend. You can't ask him more than one question in a round. If he points out someone as a true friend, you can't eliminate anyone, so you can't continue the game. $\endgroup$ – Ankoganit Mar 6 '17 at 14:32
  • 2
    $\begingroup$ @Ankoganit. I've edited the answer. I think I got it this time. $\endgroup$ – Marius Mar 6 '17 at 15:42
  • 2
    $\begingroup$ Try It Online! $\endgroup$ – Andrew Savinykh Mar 7 '17 at 8:14
  • 1
    $\begingroup$ @n00dles It is kind of hard to get only 2 true friends. Since you have 50% chances that any one is a friend or troll, the problem is similar to "Flip a coin 2017 times and get 2 and only 2 times head". The chance is about $1.351 \times 10^{-601}$ which is close to 0. $\endgroup$ – Marius Mar 7 '17 at 13:08
10
$\begingroup$

Essentially the same a @Marius' answer. Different wording, so leaving it in case someone finds it easier to understand. Give your votes to him.

Phase 1 - Identifying a real person

Arrange everyone in a line.

Beginning with the second person in line, do the following:

  1. If you pass the end of the line, then
    a. Kick out the person at the head
    b. If a real person, kick everyone since they are all trolls.
    c. If a troll, then start over at step 1 with the new second person in line (i.e. used to be the third person in line, but we just kicked out the head)
  2. Ask the current person in line: "Is the person at the head of the line a real person?"
    a. If "No", move to the next person in line and goto step 1.
    b. If "Yes", then kick out the current person.
    i. If a troll, then move to the next person in line and goto step 1.
    ii. If a real person, the person at the head of the line is also a real person, so goto phase 2.

We are guaranteed to either:
- kick out a real person and go to phase 2
- kick out everyone (because they are all trolls)

At no point will we ever kick out more than one real person.

Phase 2 - Removing trolls

This phase is quite simple. Start with the head of the line (who is known to be a real person):

  1. If we reach the last person in line, we are done. Everyone remaining is real.
  2. Otherwise, ask the current person "Is the person behind you a real person?"
    a. If the answer is "Yes", move to the next person in line and goto step 1.
    b. If the answer is "No", then kick out the person behind the current person (people will move forward to fill the gap) and goto step 1.

This works because you will only keep real persons and trust their answers. Thus, the head of the line will have real people, and the people behind them are in doubt. So asking a real person about the person behind tehm will identify the person behind them one way or the other.

Note: You do not need to ask everyone a question in every round. In fact, in phase 1, you stop when you get the first "Yes", or run out of people to ask. In Phase 2, you will stop whenever you hit a troll.

Improve this answer
$\endgroup$
3
$\begingroup$

N.B.: This method requires a minimum of 175 trolls in the room to arrive at a statistical impossibility.

The only consistent variable you have is a lie. In other words, you cannot identify a friend, you can only identify a troll. You cannot use a trolls knowledge, however, because he will give a random reply. You can only us a friend's knowledge.

On the first round, ask every guest if 2 + 2 = 4.

Statistically speaking, you should have at least one troll who answers falsely. You expel him, then ask everyone in the room if the expelled person was a troll. Anyone who answers "no" goes on a "troll list."

Let's presume you have at least 11 people on the troll list. You must expel one in order to go on to the next round: you are left with 2005 unknown guests and 10 known trolls. You then ask each of the guests if any given one of the trolls is a troll. (When no trolls are left on the list, simply ask about an already excluded troll.) Any guest who answers "no" is a troll; (s)he is put on the troll list.

You continue the process until all the known trolls are sent out of the room. Since

2 ^ 175 = 2.3945243 x 10 ^ 52

and 1 / 10 ^ 50 is generally considered a statistical impossibility, by the time all the guests have answered the question 174 times, you should have eliminated all the trolls and just be left with friends.

Edit:

When you get down to just 1 person left on the troll list, seat the guests (excluding the known troll) in a circle ask all the other guests whether the person to his/her left is a troll. If you get a "yes" somewhere, statistical impossibility has occurred, but all is not lost!

You know that the person who said "yes" is a friend: otherwise the person to his right would have said that he wasn't (unless we arrived at two statistical impossibilities simultaneously). Therefore, we simply add the person on his left to the troll list and run the same test again.

Improve this answer
$\endgroup$
8
  • 4
    $\begingroup$ Statistically probable does not mean it will happen. There is a small chance that all trolls will answer truthfully every time you ask them. You should not base your answer on probabilities. It has to be certain. $\endgroup$ – Marius Mar 6 '17 at 15:55
  • $\begingroup$ Or perhaps the trolls are out to sabotage you and can know your plan. They will answer in whatever way they feel works to their advantage. $\endgroup$ – Trenin Mar 6 '17 at 18:11
  • $\begingroup$ @Trenin, I considered that possibility, but discarded it on the basis of the word "random." Of course, that could be interpreted two different ways. $\endgroup$ – anonymous2 Mar 6 '17 at 18:24
  • 1
    $\begingroup$ @anonymous2 Still give you a +1 - always good to look at problems from more than one perspective! $\endgroup$ – Trenin Mar 6 '17 at 18:37
  • 2
    $\begingroup$ @BrunoCosta, except you have to eliminate a troll every time you ask a question. $\endgroup$ – anonymous2 Mar 7 '17 at 14:23
1
$\begingroup$

Pick a person, and ask everyone except Steve, "is Steve a troll?" Ask Steve about any other person, eg "is Becky a troll?". No matter what, kick Steve out.

If he was a troll, everyone who said No is also a troll. Also, his answer about Becky is of no value. You'll be kicking them all out, but each time you will ask about them first. This way trolls who said Yes about Steve may say No about this one, and you will find them also. (Don't bother asking them about another guest, since as a known troll their answer has no value.)

If he was not a troll, everyone who said Yes is a troll, and you will take the same approach with them, but you have used up your free "kick out a person". However you will have a piece of information about Becky. Add her to your troll list, or if she's a person, wait.

It's possible that a troll will tell the truth every single round, or that all the trolls will tell the truth on the first go. If you have kicked out everyone who ever lied, you're basically back at the beginning. If you didn't use up your free "kick out a person" you can just apply the same technique - pick a person, ask about them (but ask them about someone else), and kick them. If you have used it up and you have a known person (Eg Becky) ask "are there any trolls left?". If she says no, you're done. If she says yes, or if you reach this point with no known persons, then I suppose your choices are to take your chances and keep going, or to declare that you've found all the trolls and are stopping. It's not clear what the consequences are for stopping too soon.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The objective of the game is to kick out all the trolls (read the last line of the OP carefully). If you stop too soon, there are no dire consequences: you've simply failed in your mission. $\endgroup$ – Ankoganit Mar 6 '17 at 14:36
0
$\begingroup$

You could theoretically ask each person whether they themselves are a troll. If they say yes, we know they are a troll, because that is just a random answer (if they weren't a troll they wouldn't say that, because they would be being honest). However, if they answer no, they could be really not a troll, so you don't have to do that.

However, imagine this edge case: the trolls tell the truth the same time, i.e. you cannot tell them from the normal people. In this case, the only way to tell a troll from a true friend is to ask about themselves. Another (theoretical) situation is that all trolls lie all the time. In this case, when asked about themselves, they say they aren't a troll, but when asked about a true friend they call them a troll.

Essentially, I don't think there is a surefire way to guarantee that exactly the trolls are kicked out, but it might be possible to only kick out 1 true friend asking each guest about themself.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ "Essentially, I don't think there is a surefire way to guarantee that exactly the trolls are kicked out" - I think I found one. See my answer. $\endgroup$ – Marius Mar 6 '17 at 15:52

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.