A generalization of Tyler Seacrest's "Three voting prisoners" puzzle

Question

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.

Answer 1

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$.

Answer 2

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.