87
$\begingroup$

Three prisoners have a brief strategy meeting, and then are not allowed to communicate.

Each night one of the three has steak for dinner, while the other two have fish tacos. Also each night, each of the three prisoners votes for one of the following two options:

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

If a majority go with option 2, nothing happens that night. If a majority go with option 1, then they are set free if they are right, and executed if they are wrong. The distribution of votes is kept secret, so it is unknown what each of the others voted.

What should their strategy be?

Improve this question
$\endgroup$
14
  • 2
    $\begingroup$ This is pretty easy if you are familiar with this type of puzzle, but I still thought it was cute. $\endgroup$
    – Tyler Seacrest
    Commented Oct 1, 2015 at 16:19
  • 2
    $\begingroup$ Are they told anything about the vote results once cast other than "Nothing happens", "You all live", or "You die"? Also, I think I'm missing something. If they can select the meals, then they agree to have each person in sequence select 'steak' night 1, night 2, and night 3 while all voting '2', and on night 4 they all vote '1'. $\endgroup$
    – lorimer
    Commented Oct 1, 2015 at 16:32
  • 2
    $\begingroup$ @lorimer: Oh, I guess I mean to say that it doesn't matter how the prison guards select their meals. Assume the prisoners have no control over their meals. $\endgroup$
    – Tyler Seacrest
    Commented Oct 1, 2015 at 16:38
  • 12
    $\begingroup$ It does matter a bit, as the guards can guarantee either execution or perpetual imprisonment by choosing to never feed inmate #3 steak. :) $\endgroup$
    – lorimer
    Commented Oct 1, 2015 at 16:49
  • 8
    $\begingroup$ Free steak and fish tacos? Why would they WANT to escape!? $\endgroup$
    – n00b
    Commented Oct 5, 2015 at 13:37

8 Answers 8

Reset to default
169
$\begingroup$

Another intuitive, no-math (and I believe best) strategy could be as follows:

The prisoner that gets steak the first night should always vote 2 (Don't know). The other two prisoners that get fish tacos the first night should vote 2 until they get steak for the first time, then vote 1 (Steaks) every night from then on.

This ensures that

  • The majority won't vote 1 (Steaks) when they would be wrong.
  • The majority will vote 1 the first night they all had steak.
Improve this answer
$\endgroup$
10
  • 19
    $\begingroup$ Wow! This is much simpler than the intended solution -- nice job. $\endgroup$
    – Tyler Seacrest
    Commented Oct 1, 2015 at 18:19
  • 5
    $\begingroup$ This will fail for a,b,b,c(?) where the letter is the prisoner receiving steak that night. I think the modification should be vote 1 after you receive steak unless you get the steak $\endgroup$
    – sriram
    Commented Oct 1, 2015 at 20:57
  • 5
    $\begingroup$ @sriram How? First night they all vote (2); Second night b votes (1) which is weird and the others vote (2); Third night b votes (1) which is weird and the others vote (2); Final night a votes (2) and the others vote (1) which is correct. $\endgroup$
    – kaine
    Commented Oct 1, 2015 at 22:20
  • 2
    $\begingroup$ agreed. i misunderstood the "always" as only the first day. $\endgroup$
    – sriram
    Commented Oct 2, 2015 at 4:13
  • 9
    $\begingroup$ All mothers know that, they keep telling this to their daughters: "never say yes for the first night" ;-) $\endgroup$
    – fpierrat
    Commented Oct 2, 2015 at 8:42
32
$\begingroup$
  • Call the three prisoners $A$, $B$, $C$.
  • Denote by $a_n$ (respectively $b_n$, $c_n$) the number of times prisoner $A$ (respectively $B$, $C$) had steak during the first $n$ days.
  • Note that prisoner $A$ (respectively $B$, $C$) knows his own value $a_n$ (respectively $b_n$, $c_n$), but does not know the other two values.
  • Then $a_n+b_n+c_n=n$ for all $n$

One good strategy for the three prisoners is

$A$ votes for option 1, if and only if $1\le a_n<n/2$
$B$ votes for option 1, if and only if $1\le b_n<n/2$
$C$ votes for option 1, if and only if $1\le c_n<n/2$

Proof that they will never be executed:

  • As long as only one prisoner (say $A$) has had steak, we have $a_n=n$ and $b_n=c_n=0$. Then $B$ and $C$ both vote for option 2.
  • As long as only two prisoners (say $A$ and $B$) had steak, we have $a_n+b_n=n$ and $c_n=0$. Then $C$ votes for option 2. Furthermore, it is impossible that simultaneously $a_n<n/2$ and $b_n<n/2$ (as this would imply the contradiction $a_n+b_n<n$). Hence at least two prisoners vote for option 2.
  • Summarizing: unless all three have had steak already, the majority will vote for option 2.

Proof that they will be set free on the first day where this becomes possible:

  • If all three already had steak on day $n$, then $a_n,b_n,c_n\ge1$ and $a_n+b_n+c_n=n$ implies that at least two of the numbers are strictly smaller than $n/2$. (If two are at least $n/2$ and the third one is at least $1$, then their sum would be at least $n+1$.) Hence at least two of the prisoners vote for option 1, and they are set free.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is the intended solution =). $\endgroup$
    – Tyler Seacrest
    Commented Oct 1, 2015 at 18:20
30
$\begingroup$

Rule 1:

Vote "I don't know" if you had steak that day or haven't had it yet.

Rule 2:

Vote "All have had steak" if you didn't have steak that day, but have had it in the past.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Awesome -- simple and solves Artur Kirkoryan's extended version of the problem. $\endgroup$
    – Tyler Seacrest
    Commented Oct 2, 2015 at 17:11
  • 2
    $\begingroup$ Any of these 2 rules is even enough alone, isn't it? Form1= Say "I don't know" if you never had steak or if you had steack tonight, otherwise say "We all had steak", or Form2= Say "We all had steak" if you had steack in the past but not today, otherwise say "I don't know". $\endgroup$
    – fpierrat
    Commented Oct 5, 2015 at 8:25
  • 1
    $\begingroup$ @fpierrat both rules are identical, if we assume "vote the other option otherwise". $\endgroup$
    – Paŭlo Ebermann
    Commented Oct 5, 2015 at 12:48
  • $\begingroup$ @PaŭloEbermann Complementary rather than identical; that's what I meant by "one of them is enough" $\endgroup$
    – fpierrat
    Commented Oct 5, 2015 at 14:27
  • $\begingroup$ My friend got the same solution. I can't see why this post has so less votes as compared to matega's. $\endgroup$
    – ghosts_in_the_code
    Commented Oct 19, 2015 at 9:32
15
$\begingroup$

@Gamow already offered a nice solution, but I decided to give an alternative one.

The good thing about this one is that even if the prisoners are not told when they will start getting steaks for dinner, it still works.

Strategy:

A prisoner always votes 2 if he has never had steak for dinner.

If a prisoner had steak for dinner, then he votes 1 if he had odd number of consecutive steaks nights and 2 if he had even number of consecutive steak nights. If a prisoner didn't have steak for dinner (but had steak in the past), then he votes 1 if he had even number of consecutive non-steak nights and 2 if he had odd number of consecutive non-steak nights.

This way the prisoners will never be executed, because in case just 2 of them have had steaks, each day exactly one of them will be voting for option 1. Also it is easy to see that the prisoners will be released on the first or second possible day.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Good solution, I was in the process of reasoning this and you found it/complete it before I could, also kudos for the 'no math' answer. Key is indeed even/odd amount of days. Will +1 when I have more votes. However this doesn't necessarily free them on the first possible night in a scenario where every night the steak dinner alternates from one to another (ratio 1-1-1) as the 'consecutive' part will mean the one with the steak will vote 1, and the other 2 will vote 2 (because they've only eaten 1 consecutive steak dinner) $\endgroup$
    – Spacemonkey
    Commented Oct 1, 2015 at 17:40
  • 2
    $\begingroup$ @Spacemonkey, you are right, it may happen on the second day. Thanks for the remark! $\endgroup$
    – Puzzle Prime
    Commented Oct 1, 2015 at 17:57
4
$\begingroup$

Note: this is no longer valid since the stipulation was added that the vote is secret.

This is not optimal (release one day later), but my intuition came up with:

  • Vote 1 to communicate "I had steak for the first time tonight";
  • Vote 2 on fish taco or any subsequent steak nights.

This is repeated until each prisoner has voted 1. Then they have the next day to pack their belongings: they all vote 1 that night and are set free.

A small benefit over the intended (mathematical) answer is that the prisoners only require three bits of write-once memory each. Chalk on their cell walls will do.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ How would one prisoner know what the others voted? $\endgroup$
    – Engineer Toast
    Commented Oct 2, 2015 at 12:05
  • 1
    $\begingroup$ @EngineerToast Ah. I had assumed voting was simultaneous but public, as in: each prisoner writes down his vote and then the votes are revealed simultaneously. The puzzle doesn't specify either way. I proposed an amendment. $\endgroup$
    – Oliphaunt
    Commented Oct 2, 2015 at 12:15
3
$\begingroup$

Here is a very mathematical one. It works, but is much more complicated than it needs to be. I thought I'd write it down just for fun.

Fix some sequences of integers $a_n, \ b_n, \ c_n$ so that 1) $a_n, b_n, c_n \leq n$, and 2) for any triple of integers $a,b,c$, there is some $n$ with $a_n = a, \ b_n = b,\ c_n = c$ (this $n$ need not be unique). The plan is now to check, on $n$-th day, if it was the case that prisoner A got steak on day $a_n$, prisoner B on night $b_n$ and prisoner C on night $c_n$.

The voting rule is now simple. On day $n$, prisoner A votes 1 if and only if he got steak on day $a_n$, and fish on days $b_n$ and $c_n$. Analogous rule applies to B and to C.

The prisoners will eventually be set free. Indeed, if they get steak on days $a,\ b$ and $c$ respectively, then they will be set free on the $n$-the day, where $n$ is the first integer with $a_n = a, \ b_n = b,\ c_n = c$.

Conversely, if two prisoners (say A and B) vote 1 on a given day $n$, then between them on days $a_n,\ b_n,\ c_n$ they only ate 2 steaks. Since the total of 3 steaks was distributed, the third one had to go to C.

This has a nice added bonus that on the day the prisoners are set free, each of them votes 1.

Improve this answer
$\endgroup$
2
$\begingroup$

I thought of it like this.

First reduce number of cases. Every prisoner is identical.

Consider 3 days.

If after 3 days , a person has received steak more than once, he will say no as it cant be possible that the rest have received it. The person who didnt receive it is 1 person and he will say no as he knows he didnt receive it. Majority : N N Y(Safe)

If after 3 days , a person has received steak once only, he might anticipate the other two have got it. The other person if he has gotten steak twice , its reduced to case 1.So he also got once. The third person will have to get once. So all will say Y and will be set free !

Improve this answer
$\endgroup$
2
  • $\begingroup$ You are correct on the first three days, but can you explain what is their strategy after those three days? $\endgroup$
    – Rohcana
    Commented Oct 1, 2015 at 18:31
  • 1
    $\begingroup$ @Anachor I think the intent is, "If you have received exactly one steak in the last three days, vote yes." It's a safe strategy, but doesn't guarantee escape. If there were another rule, "If you have received steak in the past and have not received steak in the last three days, also vote yes," I think it would work. $\endgroup$
    – Zandar
    Commented Oct 1, 2015 at 18:59
2
$\begingroup$

Vote 1 if you've had steak but didn't get it tonight.

Rationale:

Whoever has steak first may have it once or many days. Once they lose it the second person to get steak has steak once or many days, and the first person is voting 1.

Should the first person then get steak again, second steak-eater is voting 1 but first one stops. The steak may flip between these two any number of times and only one will be voting for freedom.

Once the third prisoner to get steak has steak, both other prisoners are voting 1. So they're freed.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.