Register Guidelines E-Books Search Today's Posts Mark Forums Read

 MobileRead Forums Escape from Prison Puzzle

06-17-2010, 02:21 PM   #46
dsvick
Wizard

Posts: 2,737
Karma: 635747
Join Date: Nov 2009
Location: Northeast Ohio, USA
Device: PRS-900
Quote:
 Originally Posted by pdurrant Do the thought experiment - pretend you're the first prisoner to arrive, and you're given a green mark (although you don't know it's green). Subsequently one more green and two blue prisoners arrive. Every prisoner can now see at least one prisoner of each colour. So every prisoner knows that the prison contains prisoners of both colours. Can any of them conclude anything about their own colour from this? I think you will see that they cannot, especially if you try to consider the situation from the viewpoint of any one of the prisoners. Spoiler: And yet if the governor gathers all four prisoners together and gives his speech to them, I think you'll find that there is a now a difference, even though he appears to have only told them something that they all already know. In fact, he's told them something else as well. Work out what that is, and you'll probably be able to see the answer.
You're right, the governor is letting them know that everyone now knows there are two colors represented. But I think it only works when you have 2 of each color.

Spoiler:
If there are four of them sitting around, 2 blue and 2 green. Each of the four knows that both colors are represented. Regardless of what color I have I'll see 2 of one color and 1 of another. If the person that I see that is the single color does not leave then he must see both colors also, which means I've got the same color as him. But it only works if I know that he knows that both colors are represented, if he didn't know that then he would also have to consider that he had the same color as everyone else.

As soon as you have 3 of each color, you can be assured that everyone can see at least one of each color.

Spoiler:
I can then know that everyone else see's at least two of each. More importantly, I know that there are two people who see 3 of one color and at least one of the other. If neither of them leaves on the second day I have to assume they see the same color on me, making it at least two that they see.

Of course I could be way wrong

 06-17-2010, 02:40 PM #47 omk3 Wizard     Posts: 1,454 Karma: 37243 Join Date: Dec 2009 Location: Europe Device: pocketbook 360, kindle 4 Ok, I can see the logic in the solution. I was halfway there myself, and then looked at obs20's answer and it was what I was thinking. But at the same time, it still seems illogical to me. I mean, they can obviously SEE there are both colours there for &*&%'s sake! It's exhausting to be in two minds. Seeing the logic and seeing the irrationality of something at the same time is where madness lies.
06-17-2010, 03:06 PM   #48
pdurrant
The Grand Mouse 高貴的老鼠

Posts: 46,778
Karma: 159867736
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Voyage
Quote:
 Originally Posted by omk3 Ok, I can see the logic in the solution. I was halfway there myself, and then looked at obs20's answer and it was what I was thinking. But at the same time, it still seems illogical to me. I mean, they can obviously SEE there are both colours there for &*&%'s sake! It's exhausting to be in two minds. Seeing the logic and seeing the irrationality of something at the same time is where madness lies.
I'll try to explain tomorrow or Saturday. It is confusing.

06-17-2010, 06:48 PM   #49
obs20
Wizard

Posts: 2,561
Karma: 28118448
Join Date: May 2010
Location: Florida
Device: Sony PRS 600, Nook ST, Toshiba Excite 10.1 AT 300
Quote:
 Originally Posted by pdurrant I'll try to explain tomorrow or Saturday. It is confusing.
I'm teaching a summer class for at risk middle school students, this is a class of 12 and 13 year old children.
I gave them this problem today. While none were able to solve it, they were all able to understand the answer and apply it.

 06-17-2010, 09:12 PM #50 dreams It's about the umbrella     Posts: 25,114 Karma: 56218156 Join Date: Jan 2009 Device: Sony 505| K Fire | KK 3G+Wi-Fi | iPhone 3Gs |Vista 32-bit Hm Prem w/FF Alright, I give. I even peeked at obs20's spoiler, and still don't understand it.
 06-17-2010, 09:13 PM #51 poohbear_nc 2017 Is Here! Run Away!     Posts: 34,837 Karma: 100100919 Join Date: Feb 2009 Location: Durham, NC Device: Every Kindle Ever Made & To Be Made + Kobo Aura + Nexus7.2! I vote we break out of the prison through a tunnel and incarcerate pdurrant in solitary - with a red marked forehead!
 06-17-2010, 10:15 PM #52 Wetdogeared Grand Sorcerer     Posts: 5,716 Karma: 5813057 Join Date: Nov 2008 Location: Maritime, Canada Device: S0ny PRS-300/350/505/700/T1 Spoiler: The visiting logician that verifies your conclusion is colourblind, so noone is leaving....ever. Last edited by Wetdogeared; 06-18-2010 at 12:11 PM. Reason: forgot spoiler
06-18-2010, 03:50 PM   #53
dreams

Posts: 25,114
Karma: 56218156
Join Date: Jan 2009
Device: Sony 505| K Fire | KK 3G+Wi-Fi | iPhone 3Gs |Vista 32-bit Hm Prem w/FF
Quote:
 Originally Posted by poohbear_nc I vote we break out of the prison through a tunnel and incarcerate pdurrant in solitary - with a red marked forehead!
Just drop him in as prisoner #101 with a mark that's half green and half blue. He'll never guess that one.

<and I still haven't figured this one out>

06-18-2010, 04:16 PM   #54
pdurrant
The Grand Mouse 高貴的老鼠

Posts: 46,778
Karma: 159867736
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Voyage
Quote:
 Originally Posted by dreams Just drop him in as prisoner #101 with a mark that's half green and half blue. He'll never guess that one.
In that case, I won't post the answer until some time tomorrow. You've got at least 12 hours left to work it out!

06-18-2010, 04:37 PM   #55
dreams

Posts: 25,114
Karma: 56218156
Join Date: Jan 2009
Device: Sony 505| K Fire | KK 3G+Wi-Fi | iPhone 3Gs |Vista 32-bit Hm Prem w/FF
Quote:
 Originally Posted by pdurrant In that case, I won't post the answer until some time tomorrow. You've got at least 12 hours left to work it out!
Noooooo! I take it back. Forgive me for that terrible thought.

<you realize that they will all blame me for the delay, yes?>

You can stay there and I'll send massive amounts of chocolate, and your favorite drink, and all the books you've been trying to buy, and, and,....

 06-18-2010, 04:54 PM #56 poohbear_nc 2017 Is Here! Run Away!     Posts: 34,837 Karma: 100100919 Join Date: Feb 2009 Location: Durham, NC Device: Every Kindle Ever Made & To Be Made + Kobo Aura + Nexus7.2! OK - we put the blonde bimbo in the cell with #101 - and watch how he gets out!
06-18-2010, 07:11 PM   #57
pdurrant
The Grand Mouse 高貴的老鼠

Posts: 46,778
Karma: 159867736
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Voyage
Quote:
 Originally Posted by dreams Noooooo! I take it back. Forgive me for that terrible thought. You can stay there and I'll send massive amounts of chocolate, and your favorite drink, and all the books you've been trying to buy, and, and,....
OK, here's the answer and my explanation. Inside a spoiler tag, since I said I wouldn't post it yet.

Spoiler:
No-one gets out for 44 days after the governor's speech. On the 45th day, all the prisoners with green ink apply to be released, and are released. On the 46th day, all the prisoners with blue ink apply to be released and are released.

Explanation:
I think it's best to look at what would happen with smaller numbers of prisoners. And to do that, we'll pretend to be one of the prisoners - so we don't initially know our ink colour. I'm going to assume I can see the same or more blue than green. This is just to make the language less convoluted. The problem is obviously symmetric and works just as well with the colours all swapped.

First Case (two or more prisoners). All the other prisoners I can see have blue ink. I don't know my colour. The governor says that there are both colours. I immediately know I must be green, and apply for release the next day. The other prisoners apply the next day, as I can only have applied for release if I could see only one colour, which means they now all know that they are all blue.

Second Case (three or more prisoners): I can see one green and one or more blue prisoners. So you would think that the governor's statement doesn't help me, as I already know that there are both blue and green prisoners. But I can now reason as follows:
* If I am blue, the green prisoner can only see blue prisoners, so he will apply to be released tomorrow, as the governor's speech has told him that there are both colours present. This will confirm I'm blue and I can apply the following day.
* If the green prisoner I can see does not apply for release tomorrow, he must be able to see another green prisoner, which must be me. I must be green, and I can apply for release on the second day after the governor's speech.

Third Case (five or more prisoners): I can see two greens and two or more blues. This is an interesting case to consider, as I now know that all the other prisoners know that there are blue and green prisoners in the prison. However:
* If I am blue, each green prisoner can only see one other green prisoner. By the reasoning in the Second Case, they will both apply to be released on the second day after the governor's speech. This will confirm that I'm blue and I can apply to be released on the third day.
* If the two green prisoners I can see do not apply for release on the second day after the governor's speech, they must be able to see another green prisoner, which must be me. I must be green, and I can apply for release on the third day after the governor's speech.

Fourth Case (seven or more prisoners): I can see three greens and three or more blues.
* If I am blue, each green prisoner can see two other green prisoners. By the reasoning in the Third Case, they will all apply to be released on the third day after the governor's speech. This will confirm that I'm blue and I can apply to be released the fourth day.
* If the three green prisoners I can see do not apply for release on the third day after the governor's speech, they must be able to see another green prisoner, which must be me. I must be green, and I can apply for release on the fourth day after the governor's speech.

I think it's now obvious that this line of reasoning can be continued forever. Leading to the answer I gave above.

So what information has the governor given me with his speech?

1. He's given me the information that both colours are present in the prison. This allows me to get released in the First case.

2. He's given me the information that all the prisoners know that both colours are present in the prison (by telling us all when we're all gathered together). This allows me to do the reasoning to get released in the Second Case.

3. He's given me the information that all the prisoners know that all the other prisoners know that both colours are present in the prison. This allows me to do the reasoning in the Third Case.

4. He's given me the information that all the prisoners know that all the other prisioners know that all the other prisoners know that both colours are present in the prison. This allows me to do the reasoning in the Fourth Case.

And so on.... He's given me the information that it's valid to reason about what the other prisoners can reason about what the other prisoners can reson about..... etc. Which allows the chain of reasoning for the 45th Case to work.

Not convinced? Let me write out the Fourth Case in full, rather than refer to the earlier reasoning.

Fourth Case (seven or more prisoners): I can see three greens and three or more blues.
* If I am blue, each green prisoner I can see two green prisoners. Each of the three green prisoners I can see will reason as follows:
* If I am blue, each green prisoner I can see can only see one green prisoner. Each of the two green prisoners I can see will each reason as follows:
* If I am blue, the one green prisoner I can see can only see blue prisoners, and will reason as follows:
* I can only see blue prisoners and the governor's just said that there are blue and green prisoners. I can apply for release tomorrow, as I must be green.
I can then apply for release on the second day.
* If the one green prisoner I can see doesn't leave, there must be another green prisoner which that prisoner can see, which must be me. We'll both leave on the second day.
Of course, I can see two green prisoners, so I know that no-one will leave on the first day. But if the two green prisoners I can see leave on the second day, I must be blue and can leave on the third day.
* If the two green prisoners I can see don't leave on the second day, there must be another green prisoner which they can both see, which must be me. All three of us can leave on the third day
Of course, I can see three green prisoners, so I know that no-one will leave on the first or second days. But if the three green prisoners I can see leave on the third day, I must be blue and can leave on the fourth day.
* If the three green prisoners I can see don't apply to leave on the third day, there must be another green prisoner that they can all see, and it must be me. We can all apply to leave on the fourth day.

This is an case of Common Knowledge. When a fact is Common Knowledge, it isn't just known to all members of the group, but all members of the group know that all other members of the group know the fact, and also that all members of the group know that all members of the group know that all members of the group know the fact, etc.

Because the governor's speech has made the presence of both colours Common Knowledge amoung the prisoners, each prisoner can make a chain of assumptions about what the green prisoners that they can see can themselves see and can know, which leads to them to deduce their ink colour depending on whether the n green prisoners they can see leave the prison on the nth day after the speech.

The end of the chain of reasoning depends on the information from the governors speech. Without the governor having given the speech to them all, the chain of reasoning would break. What the governor's speech has done has been to convert the fact that there are both colours in the prison from a fact known to all the prisoners to a Common Knowledge fact.

06-18-2010, 07:37 PM   #58
dreams

Posts: 25,114
Karma: 56218156
Join Date: Jan 2009
Device: Sony 505| K Fire | KK 3G+Wi-Fi | iPhone 3Gs |Vista 32-bit Hm Prem w/FF
Thank you, pdurrant! That was so great of you to write that out and make it so understandable (well, at least with the last part you wrote, I finally understood. )

Spoiler:
I didn't realize that this part made a difference in reasoning..
Quote:
 What the governor's speech has done has been to convert the fact that there are both colours in the prison from a fact known to all the prisoners to a Common Knowledge fact.
I also got lost when I was trying to figure out how many saw what and thought what on the succeeding days, by using the 100 total. I should have tried it with smaller numbers first.

Many, many thanks for the explanation and for the fun puzzles.

 06-18-2010, 07:42 PM #59 zelda_pinwheel zeldinha zippy zeldissima     Posts: 27,827 Karma: 915726 Join Date: Dec 2007 Location: Paris, France Device: eb1150 & is that a nook in her pocket, or she just happy to see you? all right, i'm just going to take the fact that pdurrant himself has posted the solution as a general blessing to forget trying to solve it myself. i officially give up. i blame work, and the rain. (seriously. i've been feeling like an old sock all week, and i'm sure it's the lack of sun.) now, off to click all the spoiler buttons.
 06-18-2010, 08:01 PM #60 zelda_pinwheel zeldinha zippy zeldissima     Posts: 27,827 Karma: 915726 Join Date: Dec 2007 Location: Paris, France Device: eb1150 & is that a nook in her pocket, or she just happy to see you? okay, i've just re-read this entire thread with all the spoilers. crikey ! to be honest, i'm not sure i would have figured this out on my own, even if i had had enough time to really think about it (i didn't, this week). that was a brilliant puzzle though, thank you pdurrant ! i hope you'll post some more.