5
$\begingroup$

Imagine you are in a big hall. Except you, there are 20 other people.

In the beginning, you have different pieces of paper:

10 times: 'leave the room' (a)
20 times: 'leave the room in the next round' (b)
20 times: 'stay here for the rest of the time, do not care what paper I'll give you in further rounds!' (c)
20 times: 'are you a murderer?' (d)
100 times: (empty ticket) (e)
  • You play at most 15 rounds.
  • At the end of the game, every person must have at least 5 pieces of paper (so you shouldn't let somebody go before he has at least 4 papers)
  • In every round, you have to allot 10 papers - not less and not more! You give every person 0 or 1 papers per round. Not more.
  • 5 of these 20 persons are murderers (in the game :p)
  • When a murder gets a 'are you a murderer?' paper, he will remove all the papers he got before. A 'not murderer' will do nothing when he gets it.
  • To win, at the end, no murderer should be in the room!
  • You can see, what papers every person already got
  • It doesn't matter if a 'not murderer' person leaves the room

The crucial question is:

What's your strategy to win the game? (You should write a whole gameplay)

$\endgroup$
  • 3
    $\begingroup$ Is there something missing? It seems that if we hand out 10*e for each of the first 8 rounds such that every candidate has 4 tickets, we can then evacuate the room in round 10 by handing out 10*b in 9 and 10*a in 10. $\endgroup$ – Jonathan Allan Jan 29 '17 at 14:39
  • $\begingroup$ My guess is, the trick is that you can't choose which papers to give people. So the winning plan has to work if you are blind to what each paper says until the person receives it. $\endgroup$ – Daphne B Jan 29 '17 at 18:56
5
$\begingroup$

I think I may be missing something.

First eight rounds: four empty tickets for everyone. Next round: "leave next round" tickets for an arbitrary 10 of them. Next round: "leave now" tickets for the rest.

This

gets everyone to leave the room after only 10 rounds and doesn't use any more resources than you have.

But

it's completely "blind", and it totally ignores the business about murderers, and it seems too easy.

Was there meant to be a condition saying that you have to

identify the murderers?

If so, then

first give everyone a blank ticket (two rounds). Then give everyone an "are you a murderer" ticket (two rounds). Then give everyone three blank tickets (six rounds). Then tell everyone to leave (two rounds). That takes 12 rounds and again gets everyone out. This still seems "too easy". Is there a requirement I've violated without noticing it?

$\endgroup$
  • $\begingroup$ I would optimize that by giving 10 people a blank ticket and then giving them the "are you a murderer" ticket. Because the probability that the 2 murderers are in the first 10 is quite significant and you might save yourselves one turn. $\endgroup$ – stack reader Jan 30 '17 at 5:30
  • $\begingroup$ There are five murderers. The probability that they are all in the first 10 is (10 choose 5) / (20 choose 5) which if I've done the arithmetic right is 3/1292. I was much more interested in simplicity than maximal average efficiency, but in any case the gain in efficiency from doing as you describe is pretty small :-). $\endgroup$ – Gareth McCaughan Jan 30 '17 at 10:34
  • $\begingroup$ Woops. 5 was it? my bad. In that case odds are not on your side. $\endgroup$ – stack reader Jan 30 '17 at 11:29
2
$\begingroup$

For the first two rounds, give everyone the piece of paper with that is empty. In the third round, give an "are you a murderer?" piece of paper. The murdered would dispose of the earlier pieces of paper. Take note of these people. Then give two more rounds of empty pieces of paper. In the sixth round, give "leave the room in the next round" piece of paper to the murderers, and "stay here for the rest of the time, do not care what paper I'll give you in further rounds" to the other people. In the seventh round, all the murderers would leave, having four pieces of paper each (from rounds three to six). The people left are not murderers.

$\endgroup$
  • 1
    $\begingroup$ This seems to be identical to the second solution in my earlier answer, apart from a minor mistake ("in the third round" actually needs to be "in the third and fourth rounds" and the other round numbers need bumping up appropriately) and a not-so-minor mistake (a murderer gets one ticket in round 1/2, disposes of it but gets another in rounds 3/4, gets two more in rounds 5/6 and 7/8, gets a "leave next time" order in round 9, and then leaves in round 10 with only four pieces of paper when they're meant to have five). Fixing these yields exactly my solution. $\endgroup$ – Gareth McCaughan Jan 29 '17 at 18:24

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.