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:
- All of us have had steak at least once.
- 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.