84

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?

Oliphaunt
  • 588
  • 1
  • 4
  • 9
Tyler Seacrest
  • 9,174
  • 2
  • 28
  • 62
  • 2
    This is pretty easy if you are familiar with this type of puzzle, but I still thought it was cute. – Tyler Seacrest Oct 01 '15 at 16:19
  • 1
    I'm assuming that who has what meal is randomly selected each night? – lorimer Oct 01 '15 at 16:25
  • 1
    @lorimer: Under the assumption that they want to avoid being executed at all costs, I don't think it matters how the meals are selected. But you can assume randomly if you'd like. – Tyler Seacrest Oct 01 '15 at 16:27
  • 2
    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'.

     – lorimer Oct 01 '15 at 16:32
  • 2
    @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. – Tyler Seacrest Oct 01 '15 at 16:38
  • 12
    It does matter a bit, as the guards can guarantee either execution or perpetual imprisonment by choosing to never feed inmate #3 steak. :) – lorimer Oct 01 '15 at 16:49
  • @lorimer The strategy is supposed to be optimal at the average case. – Rohcana Oct 01 '15 at 17:01
  • This question would be alot more interesting with either more players or the possibility that no one receives steak on random nights (without notification of course). – kaine Oct 01 '15 at 20:18
  • 1
    The thing I was missing was that the same prisoner can get steak multiple times. I was confused why they just wouldn't all vote 2 on night 1 and vote 1 on night 2. and be set free. – Captain Man Oct 01 '15 at 20:27
  • then they are set free if they are right, and executed if they are wrong Who is "they"? The majority, or all three prisoners? If "they" means the majority of voters, this is pretty simple. – user2023861 Oct 02 '15 at 12:49
  • 2
    I get stuck on the bit where they vote 'for' a statement that refers to the past ... – Lamar Latrell Oct 03 '15 at 05:56
  • Is there a solution to this problem if there are n prisoners? – ytoledano Oct 04 '15 at 21:32
  • 8
    Free steak and fish tacos? Why would they WANT to escape!? – n00b Oct 05 '15 at 13:37
  • I suppose, All of us have had steak at least once (in our lives) = Vote 1 immediately, would go against the spirit of your question ;) – Mazura Jan 09 '16 at 10:05

8 Answers8

166

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.
Gamow
  • 45,573
  • 10
  • 147
  • 381
matega
  • 1,476
  • 1
  • 9
  • 6
  • 19
    Wow! This is much simpler than the intended solution -- nice job. – Tyler Seacrest Oct 01 '15 at 18:19
  • Over 9000 really. I was thinking it out between this answer and Arthur's when he posted his, so I stopped. But yeah, this is by far the best answer. – Spacemonkey Oct 01 '15 at 19:10
  • 1
    It's nice that this sets the prisoners free on the earliest possible night. – xnor Oct 01 '15 at 20:47
  • 5
    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 – sriram Oct 01 '15 at 20:57
  • 5
    @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. – kaine Oct 01 '15 at 22:20
  • "The prisoner that gets steak the first night should always vote 2 (Don't know)" Is this just for the first day or everyday after that? I assumed just the first day – sriram Oct 02 '15 at 00:34
  • @sriram it won't fail it'll work perfectly, the voting will be: 1st night a2 b2 c2; 2nd night a2 b1 c2; 3rd night a2 b1 c2; 4th and first night they've all had steak a2 b1 c1 – Paul Evans Oct 02 '15 at 02:06
  • 2
    agreed. i misunderstood the "always" as only the first day. – sriram Oct 02 '15 at 04:13
  • 9
    All mothers know that, they keep telling this to their daughters: "never say yes for the first night" ;-) – fpierrat Oct 02 '15 at 08:42
  • Now give that 800 rep bounty please with sprinkles and extra candy on top! Or I will summon Jon Skeet... Awww my cell phone isn't working. Never mind about the last part... – Anthony Pham Oct 05 '15 at 21:16
32
  • 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.
Gamow
  • 45,573
  • 10
  • 147
  • 381
29

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.

Briguy37
  • 1,221
  • 9
  • 12
  • Awesome -- simple and solves Artur Kirkoryan's extended version of the problem. – Tyler Seacrest Oct 02 '15 at 17:11
  • 2
    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".     – fpierrat Oct 05 '15 at 08:25
  • 1
    @fpierrat both rules are identical, if we assume "vote the other option otherwise". – Paŭlo Ebermann Oct 05 '15 at 12:48
  • @PaŭloEbermann Complementary rather than identical; that's what I meant by "one of them is enough" – fpierrat Oct 05 '15 at 14:27
  • My friend got the same solution. I can't see why this post has so less votes as compared to matega's. – ghosts_in_the_code Oct 19 '15 at 09:32
15

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

Community
  • 1
Puzzle Prime
  • 6,964
  • 31
  • 62
  • 1
    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) – Spacemonkey Oct 01 '15 at 17:40
  • 2
    @Spacemonkey, you are right, it may happen on the second day. Thanks for the remark! – Puzzle Prime Oct 01 '15 at 17:57
4

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.

Oliphaunt
  • 588
  • 1
  • 4
  • 9
  • 1
    How would one prisoner know what the others voted? – Engineer Toast Oct 02 '15 at 12:05
  • 1
    @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. – Oliphaunt Oct 02 '15 at 12:15
3

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.

Jakub Konieczny
  • 131
  • 4
2

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 !

Ishan
  • 21
  • 1
  • You are correct on the first three days, but can you explain what is their strategy after those three days? – Rohcana Oct 01 '15 at 18:31
  • 1
    @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. – Zandar Oct 01 '15 at 18:59
2

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.

f''
  • 33,665
  • 4
  • 120
  • 165
Swiss Frank
  • 548
  • 2
  • 9