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.
