7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – RozzA Oct 1 '15 at 22:59
  • $\begingroup$ @RozzA Focus on the part where it says at least once and you will know. $\endgroup$ – Vikram Tiwari Oct 2 '15 at 4:27
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$.) $\endgroup$ – mathmandan Oct 5 '15 at 15:11
8
$\begingroup$

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.

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

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.