# It's a Vote! Everybody Out!

There is a country ruled by a ruthless Emperor. He has a plan to make people miserable by ridding himself of the most popular members of the population.

1. Every month, each person in the population has to vote what other person they like best. Anyone who gets at least 10 votes gets let go from the population and their current vote is nulled.

2. If this somehow results in a paradox, everyone gets to stay.

The people quite quickly learn what is going on, and decide they would actually LIKE to leave. They realize, however, that once the population is down to 10 or less, the remaining people would never be able to get enough votes, and would never get to leave.

At this point, there are 500 people left. What strategy can they employ to make sure everyone can leave as soon as possible, with no man left behind?

Assume that if they were to actually discuss who exactly they will vote for, they will be promptly executed. On the day of the vote they also do not know when casting their vote who has already voted for whomever else, or if indeed they are the last to cast their vote. The only information they get is who was in the voting booth immediately before them.

This comes from a friend and the answer is unknown at post time.

• Vote for the Emperor! – Jeff Zeitlin Sep 14 '17 at 13:02
• What does "their current vote is nulled" mean? You mean if you get ten votes your vote doesn't count? – DJClayworth Sep 14 '17 at 13:08
• "Anyone who gets at least 10 votes gets let go" does this mean 10 votes in the current voting session, or total? all the months before? – Marius Sep 14 '17 at 13:34
• Why does the order of voting matter? Does it affect whether their votes are negated? It seems impossible to save everyone, even without the nullification rule- if there are $x$ people left, you need at least $10x$ votes to free all of them, but you only have $x$ votes. How would you ever be able to save everyone? – Kevin Long Sep 14 '17 at 14:41
• Do votes accumulate? I think then the problem is tractable (and actually is simple - it becomes an exercise in proof about "fastest" and "complete") – Neil Slater Sep 14 '17 at 15:09

They vote the emperor out, thus escaping him.

If this is not the answer, then this puzzle doesn't seem possible. There must be an error in the rules, because once you are down to the last ten it is simply impossible to vote everyone out. For instance if we were to change it so votes are cumulative this would seem to be a potential answer:

Everyone votes for the person in front of them in line, this way they all get 10 votes on the same vote.
However the rule on vote negation might also counteract this, as as soon as one person is removed from the equation another would drop to 9 votes.

Then there is the paradox rule, is this supposed to be if there is a paradox everyone gets to leave? If so the answer could actually be.

Everyone votes for the person ahead of them, once they receive 10 votes all should leave, but removing them all causes them to drop to no votes, meaning they should all stay, since this is a paradox they all must leave.

• Why is that one spoiler tag busted. I tried to fix it. – Almo Sep 15 '17 at 9:48

The votes must be cumulative, or there would be no solution. Even allowing people to plot and scheme in advance, 500 people could give 10 votes to at most 50 people, and 50 of those votes would be from leavers, so you would need to scheme for 450 people to give votes to 45 people, each of whom voted for a stayer. (Their votes would all cancel.) The same ratios would continue to apply round after round. So votes must be cumulative. The mention of "current vote" also points to this.

Now imagine the round where all the remaining people are going to leave. They have less than 10 votes each - it could be as many as 9. If they are all going to leave, they need to get one or more votes, but they are getting them from leavers, and leavers votes are cancelled. The first person to be voted for can leave, but not whoever that person voted for. You can't get to zero that round.

If you end up with one person, they can't vote for themselves (and if they could and it made them a leaver, it would be cancelled.) If you end up with two people, each with 9 votes, they each vote for each other, one vote is cancelled but the other isn't, and one leaves, reducing you to one that can't leave.

This leads me to conclude they can't all leave. There has to be a stayer whose vote counts in order to send the last leaver away.

That said, I think the best strategy is "vote for the person in front of you." (The first person votes randomly.) 498 people get one vote, one (the last to vote) gets none, and someone gets 2. The majority of folks would have 9 votes. 9 people would have one less from having been last, and 9 people would have more on this round, from being the random ones. Yes, it's possible someone got two twice, and someone got none twice, and someone got none once and twice once, but I don't think the exact numbers matter anyway. If the vote counts are public you could say whoever got two votes has to vote last next time, which will even it out in subsequent rounds.

On the next round, almost everyone gets a vote that puts them over. One gets to leave, which cancels their vote, meaning the person they voted for stays, meaning their vote counts and the person they voted for leaves, etc. Even though everyone was on the cusp, this enables essentially half the votes to count and gets half the people off the island. The rest stay at 9. (ish, there are the last and the randomly-chosens messing it up, but we're not working our way 512, 256, 128 etc so it's ok if we are off by one or two.) You just repeat this until you get to one person left. We weren't asked how to minimize the number of rounds, but I feel this is the way to do it: any other strategy might send someone off with 11 votes (wasting one) or have rounds after the first 9 in which fewer than half the people leave.