10
$\begingroup$

Disclaimer: this is a scenario that I came up with on my own, and I do not actually know if there is a possible solution. The reason for posting is to see if the combined intellect of PSE can help to find one, or refine the puzzle accordingly so that a good solution emerges. If this is not in line with PSE guidelines, I apologise in advance.

The puzzle begins below, with some flavour text:

Another day in the Puzzling Prison, another weird scenario by the very intelligent, very sadistic, and very bored warden. Having gathered the 100 prisoners (to whom all usual assumptions of intelligence apply) once more, he describes his latest game.

"This game is called the Minority Victory Game. There will be a series of voting rounds, and in each round, all voters will take turns to enter a room to cast their vote. At the end of every round, the vote which was cast less is the winning vote, and all prisoners who cast that vote will be exempted from the rest of the game."

"The game will continue until there are only 1 or 2 voters left, in which case a voting round cannot be valid. My condition to you is this: complete the game within 10 rounds (optimal conditions indicate 7 rounds minimum), or all of you will be executed!"

"You are allowed to convene and discuss your strategy before the first voting round begins, but after that no communication between you will be permitted. LET THE GAMES BEGIN! [insert evil laughter here]"

Detailed rules of the game:

  1. A vote is cast by a voter choosing between two random and different objects presented to him/her in the voting room. The same objects are presented to all voters within the same round, but different sets of objects are used between rounds. The main point is that voters cannot agree before to always vote A in a given scenario.

  2. Voters do not know how many have voted before themselves, with the exception of the very first voter of each round.

  3. All voters (except the first) are allowed to know how the voter immediately before themselves voted.

  4. At the end of each round, the results will be published to all prisoners (not only all voters).

  5. In the event of a tie (e.g. 50 BLACK, 50 WHITE), all voters continue in the next voting round, and the round counts toward their total.

  6. The order in which voters are summoned to the room is completely random and changes between every round.

Is it possible for the prisoners to prevail yet again, or has the warden gone too far this time and created a truly impossible puzzle? Do any of the rules have to be edited/ removed in order for the puzzle to have a possible and non-trivial solution?

EDIT 1: changed rule 1 to increase limitations, but see @Deusovi's excellent answer for a solution with the previous ruleset.

$\endgroup$
  • $\begingroup$ Does everyone know who has been ousted after a particular round? $\endgroup$ – boboquack Nov 8 '17 at 8:37
  • $\begingroup$ @boboquack: according to rule 4, everyone only knows how many people have been ousted, not who. If knowledge of who helps you reach a solution, I'd love to know about it too please! $\endgroup$ – Xenocacia Nov 8 '17 at 8:38
  • 1
    $\begingroup$ When you say "exempted from the next voting round" does this mean they return after 2 rounds, or do they stay exempted for the duration of the game? $\endgroup$ – Saladani Nov 8 '17 at 15:18
  • 2
    $\begingroup$ If I understand the question (especially rule 1) correctly this is basically saying that every prisoner can only vote the same as the prisoner before him, different than the prisoner before him or randomly while the first prisoner in a round has to vote randomly. Then with 100 prisoners there always exists an order where the vote will end 50/50 or 100/0 thus having everyone advance. $\endgroup$ – w l Nov 8 '17 at 15:50
  • $\begingroup$ Regarding rule number 4, is the fact that non-voting prisoners receive the results significant to solving the puzzle? Are voting and non-voting prisoners allowed to interact in some way? $\endgroup$ – Matthew0898 Nov 13 '17 at 0:29
8
$\begingroup$

This is an elaboration on wl's comment, which proves that there is no strategy which guarantees success in any number of rounds, because no matter what strategy the prisoners use, there is at least one ordering which will cause no one to be eliminated in the first round.

The only information a prisoner has is what the last vote was, so their only decision is whether or not to copy the previous vote. Globally, the team's strategy consists of choosing the number of "copiers" for that round, while everyone who is not a copier is a "flopper."

Suppose they choose n prisoners to be copiers in the first round. If n is 100, then everyone votes the same, so no one is eliminated. If n is 99, then the same thing happens if the flopper is picked first. Otherwise, the below arrangements result in tie votes:

n is even: 
           (n/2) copiers, flopper, (n/2) copiers, flopper, 100–n–2 floppers
n is odd : 
           flopper, (n–1)/2 copiers, flopper, (n+1)/2 copiers, flopper, 100–n–3 floppers

By establishing the probabilities of transitioning from $n$ to $n'$ prisoners in a round given then number of floppers, we can use Markov analysis to calculate the best-case chance of success.

Except for the first flopper, each flopper reverses the vote of the previous flopper. Let's label the votes that agree with the first flopper Group A, and the opposite Group B. We can make the following statements about the vote:

  • The first Group A vote is always the first flopper, while the remaining Group A floppers can be distributed anywhere in the remaining Group A votes.
  • The first Group B vote can be either a flopper or copier, so the Group B floppers can be distributed anywhere in the Group B votes.
  • The number of floppers is split equally between Group A and Group B, except when there is an odd number of floppers and there is one more flopper in Group A than in Group B.

If $V_A$ is the number of votes garnered by Group A, $N$ is the number of prisoners voting, and $F$ is the number of floppers, we can establish the following probability while taking care of proper bounds and the edge case of zero floppers:

$$\Pr(V_A{=}v {\mid} N{=}n, F{=}f) = \begin{cases} \cfrac {\dbinom{v{-}1}{\left\lceil{\frac{f}{2}}\right\rceil{-}1} {\dbinom{n{-}v}{\left\lfloor{\frac{f}{2}}\right\rfloor}}}{\dbinom{n}{\,f}} , & \text{if $0 \lt f \le n$, $\left\lceil{\frac{f}{2}}\right\rceil \le v \le n{-}\left\lfloor{\frac{f}{2}}\right\rfloor$ }\\ {1} , & \text{if $f=0$, $v=0$} \\ 0, & \text{otherwise} \end{cases} $$

Using the preceding, the probability of transitioning from $n$ prisoners to $n'$ in a round, given $f$ floppers, is:

$$\Pr(n_{t+1}{=}n' {\mid} n_t{=}n, f_t{=}f)= \begin{cases} \sum_{v \in \{n',\,n{-}n'\}} \Pr(V_A{=}v {\mid} N{=}n, F{=}f), & \text {if $\frac{n}{2} \lt n' \lt n$} \\[1ex] \sum_{v \in \{0,\,n\}} \Pr(V_A{=}v {\mid} N{=}n, F{=}f), & \text {if $n'{=}n$, $n$ is odd} \\[1ex] \sum_{v \in \{0,\,n/2,\,n\}} \Pr(V_A{=}v {\mid} N{=}n, F{=}f), & \text {if $n'{=}n$, $n$ is even} \\[1ex] 0, & \text{otherwise} \end{cases} $$

Implementation of the preceding transition probability function in Python (p_trans):

def memoize(obj):
    cache = obj.cache = {}
    def memoizer(*args, **kwargs):
        if args not in cache:
            cache[args] = obj(*args, **kwargs)
        return cache[args]
    return memoizer

@memoize
def comb(n, k):
    """Combinations of n-choose-k"""
    from math import factorial
    return factorial(n)/factorial(k)/factorial(n-k)

@memoize
def p_voteA(v, n, f):
    """Pr(V_A=v | N=n, F=f)"""
    from math import ceil, floor
    if f != 0 and ceil(f/2.0) <= v <= n - floor(f/2.0):
        combinations = comb(v-1, ceil(f/2.0)-1) * comb(n-v, floor(f/2.0))
        return float(combinations) / comb(n, f)
    if f == 0 and v == 0:
        return 1.0
    return 0.0

@memoize
def p_trans(n_p, n, f):
    """Pr(n_{t+1}=n_p | n_t=n, f_t=f)"""
    if n/2.0 < n_p < n:           vs = [n_p, n-n_p]
    elif n_p == n and n % 2 == 1: vs = [0, n]
    elif n_p == n and n % 2 == 0: vs = [0, n/2, n]
    else:                         vs = []

    return sum(p_voteA(v, n, f) for v in vs)

Having a transition probability function allows us to use Markov analysis. For instance we can use value iteration to calculate the best-case winning percentage based on selecting the optimal number of floppers in each state:

@memoize
def win_pct_max(n, t):
    if n <= 2 and t <= 10:
        return 1.0
    if t >= 10:
        return 0.0
    pcts = []
    for f in range(n+1):
        pct = 0.0
        for n_p in range(n+1):
            p = p_trans(n_p, n, f)
            if p != 0:
                pct += p*win_pct_max(n_p, t+1)
        pcts.append(pct)

    return max(pcts)

print(win_pct_max(100, 0))

The result 0.9623222013994797. This is the best we can do by optimizing floppers each round.


Given that there is no perfect strategy, we turn our attention to finding the best strategy.

We assign each number of prisoners that are left to vote a score that represents the average amount of rounds needed to win. When there are only 1 or 2 prisoners left, the game is won: $s(1)=s(2)=0$. With 3 prisoners left, we can always get to 2 prisoners left by choosing 3 floppers, therefore $s(3)=s(2)+1$. Below are the scores and best strategy for a few numbers.

$\begin{array}{r|r|l} \text{prisoners} & \text{score} & \text{voting strategy} \\ \hline 1 & 0 \\ \hline 2 & 0 \\ \hline 3 & 1 & \text{3 floppers} \\ \hline 4 & 2.5 & \text{2 floppers} \\ \hline 5 & 2 & \text{5 floppers} \\ \hline 6 & 3.5 & \text{2 floppers} \\ \hline 7 & 3.3 & \text{4 floppers} \\ \hline 8 & 3.75 & \text{6 floppers} \\ \hline 9 & 3 & \text{9 floppers} \\ \hline 10 & 4.5125 & \text{2 floppers} \\ \hline 11 & \approx 4.4317 & \text{7 floppers} (\frac{2659}{600}) \\ \hline 12 & \approx 4.6865 & \text{6 floppers} (\frac{3393}{724}) \\ \hline 13 & 4.3 & \text{13 floppers} \\ \hline 14 & \approx 4.8960 & \text{8 floppers} (\frac{64431}{13160}) \\ \hline 15 & \approx 4.5192 & \text{12 floppers} (\frac{235}{52}) \\ \hline 16 & 4.875 & \text{14 floppers} \\ \hline 17 & 4 & \text{17 floppers} \\ \hline 18 & \approx 5.5901 & \text{2 floppers} (\frac{41544062881}{7431715200}) \\ \hline 19 & \approx 5.4887 & \text{16 floppers} (\frac{11197}{2040}) \\ \hline 20 & \approx 5.6829 & \text{4 floppers} (\frac{41544062881}{7431715200}) \\ \hline 21 & \approx 5.4317 & \text{21 floppers} (\frac{3259}{600}) \\ \hline 22 & \approx 5.7503 & \text{8 floppers} (\frac{54422747555537}{9464289307200}) \\ \hline 23 & \approx 5.5760 & \text{20 floppers} (\frac{141297}{25340}) \\ \hline 24 & \approx 5.7568 & \text{10 floppers} (\frac{21644780716829}{3759863970720}) \\ \hline 25 & 5.3 & \text{25 floppers} \\ \hline 26 & \approx 5.9097 & \text{12 floppers} (\frac{1037335451143696343}{175530959563814400}) \\ \hline 27 & \approx 5.7170 & \text{18 floppers} (\frac{46416921682337}{8119148856000}) \\ \hline 28 & \approx 5.8679 & \text{18 floppers} (\frac{11486474568601}{1957513783680}) \\ \hline 29 & \approx 5.5192 & \text{29 floppers} (\frac{287}{52}) \\ \hline 30 & \approx 6.0077 & \text{22 floppers} (\frac{64203605748067}{10686806457600}) \\ \end{array}$
These values were calculated using brute force. For $2^n+1$ all floppers will always be the best strategy. For $2^(n+1)$ all but 2 floppers is a great strategy because in over 50% of the cases we will get to $2^n+1$ which will guarantee a victory in $n$ rounds.

From the table we can see that for 6 prisoners we want to try to avoid a result too close to an even split because removing only one prisoner is actually preferable. With 8 prisoners on the other hand we want to get as close as possible to the even split. The winning strategy of 6 floppers will tie votes $\frac{3}{7}$ of the time and thus have no one advance, but it is still the best strategy because if they advance, they will win in 2 more rounds.

By just using these rules while otherwise defaulting odd rounds to all floppers and even rounds to all random votes, the prisoners can already win in over 95% of the cases (up from 85% for only using the two default rules). With perfect play in all rounds this would rise even further, but playing perfect in the last rounds is most important.

If the prisoners are smart enough to take all this into account they have a reasonably high chance to survive yet another day in Puzzling Prison.

$\endgroup$
  • $\begingroup$ totally right, if the first don't know he is (and is given false information) and the last know he is last, the puzzle is therefore possible $\endgroup$ – Neil Nov 9 '17 at 13:41
  • $\begingroup$ Can this maybe be improved, if some people are voting randomly? That is, we add some random voters among the copiers and floppers. $\endgroup$ – elias Nov 9 '17 at 22:28
  • 1
    $\begingroup$ I'd like to add, that if there are 4 prisoners, 1 flopper gives them 1/2 chance to get down to 3 for the next round, but 2 floppers provide a 2/3 chance. I think how they utilize who's gonna be a flopper is impossible unless they know who are the prisoners still voting. $\endgroup$ – elias Nov 10 '17 at 17:43
  • $\begingroup$ A more general approach allows every prisoner to copy the previous vote with any given p probability in a specific round. Then a flopper is someone who's p-value is 0, a copier's is 1. Even introducing these random voters I did not find any setup which allows them more success then the setup with 2 floppers and 2 copiers was. $\endgroup$ – elias Nov 10 '17 at 17:45
  • $\begingroup$ It seems that 7 floppers in a group of 7 prisoners is suboptimal. With 4 floppers out of 7 prisoners, you can progress to either 4 or 5 instead of always to 4. $\endgroup$ – D Krueger Nov 14 '17 at 3:06
4
$\begingroup$

Partial solution

This is a method which is stochastic, and does not work 100% of the time. Actually it works in exactly 50% of the cases. However, maybe it can help someone to come up with a better idea.

The strategy the prisoners come up with is the following:

They announce one of them being the Leader.
We should come up with a strategy that makes the Leader never belong to the minority in any voting, so there is no need to come up with a replacement in case he gets removed from the process.
The Leader is the only one who should vote with the very same token that the previous voter did, everyone else gives a different vote from the one that he sees the previous voter did. The first voter is free to choose how to vote regardless of him being the Leader.

With this strategy the Leader will not belong to the minority neither in the case of even nor odd voters:
Note that the sequence of the other n-1 voters (removing the Leader's vote) is alternating. If there were an odd number of voters, the votes of others are distributed (n-1)/2 vs (n-1)/2, whatever the Leader votes will be the majority. If there were an even number of voters, the others' votes are n/2 vs n/2-1. Depending on which position the Leader was voting, he either turns it into n/2+1 vs n/2-1 (and he belongs to the former, and advances to the next round as part of the majority), or into n/2 vs n/2 (and he advances just like everyone else).

Please also note that in case of odd voters if everyone was voting alternately, the Leader had a significant chance to vote with the minority, and his replacement is problematic as the prisoners didn't know if he was out (they only learn the results of how many voted how, but not who voted with which option), and who should act as a Leader in the remaining rounds. To grant the Leader's 'survival', he should vote same as the previous voter even in the case of odd number of voters, otherwise he risks belonging to the minority and hence the success of future rounds, even if the current one would be successful.

The problem:

If there are an even number of voters, and the voting order leaves the Leader in an odd position, there will be a tie. Just think about the difference between votes of a,b,a,A,b,a and a,b,B,a,b,a. (a and b are the options to choose from, the capital letter marks the Leader). The Leader is in an odd position in 50% of times when there are even voters - meaning on average 2n voters need 2 rounds to be reduced to n+1 voters, while 2n+1 is always reduced to n+1 in 1 round. Thus, the expected number of rounds for 100 voters is 11. However, if the random orderings are lucky, they can finish in 10 rounds.

Probability of success:

As Mike Earnest pointed out in his comment, the number of rounds follows a negative binomial distribution (its parameters are based on: with an even number of voters, the probability of the round not resulting in a tie is 0.5, there are 4 stages with an even number of voters (100, 26, 14 & 8), and as there are 7 stages in total (100, 51, 26, 14, 8, 5, 3, 2), if the prisoners end up with a tie in 3 or less rounds they are still winning), and the probability of finishing is exactly 50%. Thanks, Mike!

$\endgroup$
  • $\begingroup$ It is not a special case. If there are even number of voters, the round will be a tie, as 1 is an odd number. $\endgroup$ – elias Nov 8 '17 at 9:32
  • 1
    $\begingroup$ Huh, turns out the probability of your strategy succeeding in 10 or fewer rounds is exactly 50%! $\endgroup$ – Mike Earnest Nov 9 '17 at 18:33
  • $\begingroup$ Thanks Mike, I updated my answer with that. $\endgroup$ – elias Nov 9 '17 at 22:24
2
$\begingroup$

They can simply coordinate their votes like so:

Give everyone one of these numbers.
XX65544433
3333222222
2222221111
1111111111
1111111111
1000000000
0000000000
0000000000
0000000000
0000000000
Each prisoner given a number $n$ votes for the alphabetically earlier option up to the $n$th round, and the alphabetically later option on round $n+1$, at which point they will be eliminated. The two given X always vote for the alphabetically earlier option and are the final two remaining.

$\endgroup$
  • $\begingroup$ Ah, but what if they are colourblind or dispute BLUSH and PURPLEY-RED or other colour names? $\endgroup$ – boboquack Nov 8 '17 at 8:03
  • $\begingroup$ @boboquack - Then replace "alphabetically earliest" with any other distinguishing criterion, such as "darkest" or "closest to light blue". $\endgroup$ – Deusovi Nov 8 '17 at 8:05
  • $\begingroup$ This was why I introduced a different colour match per round as opposed to BLACK and WHITE throughout, but kudos on catching alphabetical order as a proxy. If the difference between votes were a property outside colour, e.g. ROUND vs SQUARE, LIGHT vs HEAVY, etc, would there really no longer be a valid strategy? $\endgroup$ – Xenocacia Nov 8 '17 at 8:10
  • $\begingroup$ @micsthepick I don't see why not. Maybe we could discuss in chat though? $\endgroup$ – boboquack Nov 8 '17 at 8:19
  • 2
    $\begingroup$ They are objects, so why not a hierarchy of physical criteria? Choose the heavier. If they are the same weight, choose the larger. If they are the same size (and weight), choose the harder (use one to scratch the other, say). If those are all the same, darkest color. Fewest geometrical faces. Lesser height when laid flat on a table. $\endgroup$ – Hugh Meyers Nov 9 '17 at 9:12
2
$\begingroup$

Here is a strategy for objects presented in random order/arrangement:

Vote randomly! If the prisoners agree to always choose the "first" object (top to bottom, left to right, front to back, first to last depending on how they are presented), and the objects are placed randomly for each vote, then each vote becomes a Bernoulli trial. The probability of getting at least 40 out of 100 in the minority is roughly 96% formula and explanation, while the probability of getting exactly 50 of each is only about 8% formula. In other words, the prisoners are very likely to have an near-optimal voting round. These probabilities obviously become less stable with a small voting population. If the prisoners want to do even better, they can utilize rule 4 to keep track of when there are an odd number of voters. In this case, they should use rule 3 to alternate their votes, thus guaranteeing an optimal round.

$\endgroup$
  • $\begingroup$ Voting randomly and independently every time does give the prisoners a nearly 2/3 chance of surviving, but they are trying to always win. Switching to alternating votes for odd numbers pushes the chance to around 6/7, but still shy of 100%. $\endgroup$ – w l Nov 8 '17 at 15:34
  • $\begingroup$ True, this strategy technically does not guarantee victory. I also agree that the naïve version (always picking randomly) is not viable without the improvement of alternating votes when there is an odd number of voters. I am curious how you computed the probabilities for success? $\endgroup$ – Sam Hazleton Nov 8 '17 at 17:46
  • 1
    $\begingroup$ I used simulation. That's pretty much always the fastest way to get the result if you are not interested in the exact numbers. I also tried some other variations, but at least for simple solutions this gives the prisoners the best chance. $\endgroup$ – w l Nov 8 '17 at 18:27
  • 1
    $\begingroup$ @elias I just tried and there might be a sweet spot. If there is it will probably be around 0.49, but the improvement is lower than the variation I get so I have to do some math to find it. Changing the distribution depending on the numbers of voters in the current round might improve it even more. $\endgroup$ – w l Nov 10 '17 at 8:39
  • 1
    $\begingroup$ @elias I'm at a 90% win chance by just modifying voting rounds with 6 prisoners right now. I will make an answer when I have the optimal voting behavior for all rounds. $\endgroup$ – w l Nov 10 '17 at 15:46
2
$\begingroup$

I think it is possible to do it with a really high chance of success. Here is how:

If there are odd number of voters left, first prisoner votes randomly, all other prisoners vote against the previous one, which will create the 2n+1(number of prisoners) situation to n and (n+1) votes.
If there are even number of prisoners, than the first one votes randomly, the oldest(they should set up a priority list before the game, age is one good easy example to memorize) one who can still vote will vote the same as the previous, all others vote against the previous one, thus creating a 2n situation to an (n-1) and (n+1) votes.
The problem with this is if the oldest one votes first, it will be an even vote, applying rule number 5. In this case they should vote again with the same rules(but of course they "wasted" one round).
So, the numbers will go like 100 - 51 - 26 - 14 - 8 - 5 - 3 - 2, optimally finishing in 7 rounds, so the can "waste" maximum 3 rounds. The tricky ones where the can waste a round are the 100, 26, 14, 8 rounds.I calculated their chance of success with pretty much counting all possible positive outcomes: $$\frac{99}{100}*\frac{25}{26}*\frac{13}{14}*\frac{7}{8}*(1+\frac{1}{100}+\frac{1}{26}+\frac{1}{14}+\frac{1}{8}+\frac{1}{100}*\frac{1}{100}+\frac{1}{26}*\frac{1}{26}+\frac{1}{14}*\frac{1}{14}+\frac{1}{8}*\frac{1}{8}+\frac{1}{100}*\frac{1}{26}+\frac{1}{100}*\frac{1}{14}+\frac{1}{100}*\frac{1}{8}+\frac{1}{26}*\frac{1}{14}+\frac{1}{26}*\frac{1}{8}+\frac{1}{14}*\frac{1}{8}+\frac{1}{100}*\frac{1}{100}*\frac{1}{100}+\frac{1}{26}*\frac{1}{26}*\frac{1}{26}+\frac{1}{14}*\frac{1}{14}*\frac{1}{14}+\frac{1}{8}*\frac{1}{8}*\frac{1}{8}+\frac{1}{100}*\frac{1}{100}*\frac{1}{26}+\frac{1}{100}*\frac{1}{100}*\frac{1}{14}+\frac{1}{100}*\frac{1}{100}*\frac{1}{8}+\frac{1}{26}*\frac{1}{26}*\frac{1}{100}+\frac{1}{26}*\frac{1}{26}*\frac{1}{14}+\frac{1}{26}*\frac{1}{26}*\frac{1}{8}+\frac{1}{14}*\frac{1}{14}*\frac{1}{100}+\frac{1}{14}*\frac{1}{14}*\frac{1}{26}+\frac{1}{14}*\frac{1}{14}*\frac{1}{8}+\frac{1}{8}*\frac{1}{8}*\frac{1}{100}+\frac{1}{8}*\frac{1}{8}*\frac{1}{26}+\frac{1}{8}*\frac{1}{8}*\frac{1}{14}+\frac{1}{26}*\frac{1}{14}*\frac{1}{8}+\frac{1}{100}*\frac{1}{14}*\frac{1}{8}+\frac{1}{100}*\frac{1}{26}*\frac{1}{8}+\frac{1}{100}*\frac{1}{26}*\frac{1}{14})$$

,which is around 99.928101779% for success(i used google) (about 1 in 1390 attempt they won't fit in the 10 round).

Way to make it 100% by changing the rules:

If they announce to everyone the information of who will be the first voter before every round, making strategy change at even numbers that oldest prisoner votes the same as the previous, but if the oldest is the first, than the second oldest will vote the same as the previous. This way they can avoid execution all the time in 7 rounds.

$\endgroup$
  • 1
    $\begingroup$ This is the very same answer as mine. You missed that in case the oldest (who I called the Leader) is not the first, but the third, fifth, or in any other odd number position, the even voter cases will still end in a tie. $\endgroup$ – elias Nov 8 '17 at 16:47
  • 2
    $\begingroup$ Could you please describe in details what happens when there are 6 voters, and the 3rd one is the oldest? Thank you! $\endgroup$ – elias Nov 8 '17 at 17:42
  • 1
    $\begingroup$ @elias is right. If there are an even number of voters, and the leader votes 1st, 3rd, 5th, 7th, or any odd numbered position within the voting order, the vote will result in a tie. $\endgroup$ – Sam Hazleton Nov 8 '17 at 18:06
  • 1
    $\begingroup$ Would you please correct the answer by editing it? Or even delete is, as in its corrected form it's just a duplicate? Thank you! $\endgroup$ – elias Nov 9 '17 at 9:44
  • 1
    $\begingroup$ @AndyT, thanks for the suggestion, I added some details to my answer. $\endgroup$ – elias Nov 10 '17 at 10:24
0
$\begingroup$

With an odd number of particpants they just need to always vote the opposite of what was the previous vote to ensure a maximum of eliminations every round.

That being said, the difficulty is to eliminate exactly 1 prisoner or 50% - 1 on even rounds (or as close as possible). This is impossible to ensure (100% success). So there is always a chance of failure on a sequence of improbable failures.

What would make it possible, is knowing who voted right before you. (everyone flips whoever votes after leader and leader always copies on even rounds)

$\endgroup$
-1
$\begingroup$

Lets say at a given round 2 objects are there A and B. At each round the 1st person votes A and then tell the next person to vote A but 3rd person onwards the voters vote opposite the previous guy. After 1st round : 51 A , 49 B. B's get eliminated. After 2nd round : 26 A , 25 B. B's get eliminated. After 3rd round : 14 A , 12 B. B's get eliminated. After 4th round : 8 A , 6 B. B's get eliminated. After 5th round : 4 A , 2 B. B's get eliminated. After 6th round : 3 A , 1 B. B's get eliminated. After 7th round : 2 A, 1 B. B's get eliminated.

$\endgroup$
  • $\begingroup$ The second person does not know if he is second, the third does not know he is third, they only know they are not the first to vote (because there is a previous vote registered). How could they apply a different strategy? $\endgroup$ – elias Nov 8 '17 at 16:48
  • $\begingroup$ According to rule 3 they know the vote of person just before them.That is all it needs. $\endgroup$ – abhi5154 Nov 8 '17 at 16:59
  • $\begingroup$ There is no possibility for the prisoners to share information once the woting has started. The first voter cannot tell the second how he should vote, or that he is the second. That was my point. $\endgroup$ – elias Nov 8 '17 at 17:44
  • $\begingroup$ @elias is correct: prisoners only know what vote the voter before them cast, but not which position the voter before them was. $\endgroup$ – Xenocacia Nov 9 '17 at 5:23

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.