# A generalization of Tyler Seacrest's “Three voting prisoners” puzzle

The following is a straightforward (but nonetheless not completely trivial) generalization of Tyler Seacrest's great puzzle "Three voting prisoners".

There are $n\ge2$ prisoners that have a brief strategy meeting, and then are not allowed to communicate any more.

On the following days, exactly $s$ out of the $n$ prisoners get steak for dinner, while the remaining $n-s$ prisoners get fish tacos. Also each night, each of the $n$ prisoner casts a vote for one of the following two options:

1. All of us have had steak at least once.
2. Don't know yet.

If at least $m$ out of the $n$ prisoners go with option 1, then they are all set free if they are right, and all executed if they are wrong. If at most $m-1$ of them go with option 1, then nothing happens that night.

Question: For which combinations $(n,s,m)$ does there exist a deterministic strategy for the prisoners that (a) avoids execution and (b) guarantees that they are eventually set free, once all of them have had steak at least once.

• hey fellow prisoners, looks like there are m of us here.. we all vote option 2 for m nights, then vote option 1 for FREEDOM! --or have I misread that completely? – RozzA Oct 1 '15 at 22:59
• @RozzA Focus on the part where it says at least once and you will know. – Vikram Tiwari Oct 2 '15 at 4:27

A strategy exists

if and only if $n-s\leq m\leq n$.

Clearly no strategy can exist if $m>n$, and f'' has given an argument that no strategy can exists if $m<n-s$.

Suppose $n-s\leq m\leq n$, and set $k=m-(n-s)\geq 0$. There are ${n\choose k}$ possible groups of $k$ prisoners, and the prisoners agree on an ordering of the groups. Say the groups are $G_0,\ldots,G_{{n\choose k}-1}$.

Call a prisoner fishy if they were served fish the first day, and steaky if they were served steak the first day. There are $s$ steaky prisoners and $n-s$ fishy prisoners. The prisoners will use the following strategy:

• If you are a fishy prisoner, then vote $1$ if you have ever been served steak, and vote $2$ otherwise
• If you are a steaky, then vote $1$ if you are a member of group $G_r$, where $r$ is the remainder when the day number is divided by ${n\choose k}$, and vote $2$ otherwise.

At most $k$ steaky prisoners vote $1$ on any day. So if $m$ prisoners voted $1$, then is must be the case that all $n-s$ fishy prisoners voted $1$, meaning that every prisoner has been served steak.

Conversely, if everyone has been served steak, then all $n-s$ fishy prisoners will vote $1$. If $G_r$ is a group of $k$ steaky prisoners (such a group exists because $k\leq n$, which follows from the assumption $m\leq n$), then the next time the day number leaves a remainder of $r$ when divided by ${n\choose k}$, $k$ steaky prisoners and $n-s$ fishy prisoners will vote $1$, for a total of $m$.

• In your last paragraph, where you have $k\leq n$ I think you mean $k \leq s$. If $S$ is the set of steaky prisoners (so $S$ has size $s$) then from $k\leq s$ we conclude that $S$ has a subset of size $k$--that is, there is a set of $k$ steaky prisoners, as claimed. (The inequality $k\leq s$ does indeed follow from $m\leq n$, since $k = (m-n) +s \leq s$.) – mathmandan Oct 5 '15 at 15:11

Suppose that there is a winning strategy for the prisoners with $m<n-s$.

For an arbitrary sequence of steak allocations such that every prisoner eats steak, some $m$ prisoners will eventually vote for option 1. If we swap the meals of the $n-m$ other prisoners around, the $m$ prisoners cannot tell the difference, so they must vote for option 1 anyway. But $n-m>s$, so we can swap the meals of those $n-m$ such that one never eats steak.

This shows that a winning strategy is impossible for $m<n-s$.

If $m=n-s$, we can use the same strategy that @matega described for the original problem. The $s$ prisoners who receive steak on the first day always vote for option 2, and the other $m$ vote for option 1 if they have received steak at least once.

• You mean if $m \ge n - s$? – Joe Z. Oct 2 '15 at 4:27
• No, the strategy I mentioned doesn't work for $m>n-s$. See @JulianRosen's post for those cases. – f'' Oct 2 '15 at 17:45