View source for Talk:Prisoners and hats puzzle

{{oldafdfull| date = 30 August 2014 (UTC) | result = '''keep''' | page = Prisoners and hats puzzle }}
{{WikiProject banner shell|
{{WikiProject Game theory}}
}}
{{merged-to|Hat puzzle|28 November 2017}}

At the suggestion of Ludraman, I looked over this article. Not being an expert in logic or logic puzzles, I can't speak much to that aspect. I will observe that the diagram characters have an amusing resemblance to Pacman (the yellow, probably) and that the hats might be colored in such a way as to indicate indeterminacy. Red and blue polka dots maybe?

:Ah, I was wondering why it looked familiar. Pacman, of course! [[User:Arvindn|Arvindn]] 17:19, 19 Apr 2004 (UTC)

There are other variants of this puzzle. What are some of their names?

The significance of the puzzle in logic history might be mentioned, as well as perhaps an amusing if not necessarily connected aside to the problem of self consciousness. That is, very few animals can be experimentally shown to be aware of themselves in the sense of noticing that something is wrong or changed about themselves as seen in a mirror reflection. At last count, my memory tells me, chimps (both bonobos and common??), dolphins, and homo sapiens have done so. For dogs, cats, parrots, ... and all others tested so far, no way of elicting a demonstration of such awareness has been found. The tempting inference is that no way can be found as all except the small group listed are incapable.

Thus the prisoners here should be limited to those from the listed species??

Minor wording nits, but nothing important.

Perhaps this may be of some help?
[[User:Ww|ww]] 16:21, 19 Apr 2004 (UTC)

----
I've seen a variant with 5 hats and no screen, but can't remember the details. [[User:Arvindn|Arvindn]] 17:19, 19 Apr 2004 (UTC)

----
Do you know variant of 10-hat puzzle with 3,4,5 etc. colors? [[User:Kknop|kknop]] 14:11, 29 May 2007

----

==Diagram==
Is the diagram okay? (BTW its resemblance to pacman is not intentional). When I was writing the article I thought a diagram would help but I'm not much of an artist and scribbled something in Paint that would  do for the time being. Would anyone be willing to make a better diagram? [[User:Ludraman|L<small>UDRAMAN</small>]] | [[User talk:Ludraman|T]] 02:16, 21 Apr 2004 (UTC)

:Has been fine for 8 years! Who would have thought your humble diagram would be doing the rounds in 2012 on the yet-to-be-invented Facebook? Proof enough that it's suitable, methinks. [[User:LightYear|LightYear]] ([[User talk:LightYear|talk]]) 05:22, 22 February 2012 (UTC)

== Is waiting necessary? ==

I frequently fall into traps in logic puzzles, so I invite all and sundry to explain to me why I'm wrong.  That said, is it necessary for B to determine whether or not C is going to act? Wouldn't B (or whichever person saw that the other two were wearing the same color hats, as two of them must be) immediately notice the other hats' colors, and act accordingly?

:Yep, it's necessary. Remember, B can only see A's hat. C is behind him (and the prisoners aren't able to look backwards--this is an important rule), and of course the fourth man is behind the screen. The crux of this game is that even with empirical evidence that doesn't seem strong enough to guarantee an answer, B can '''infer''' from C's (assumed completely rational) action what the answer must be. Thus the prisoners can always go free. --[[User:140.103.133.75|140.103.133.75]] 08:02, 18 July 2005 (UTC)

== Clarification ==

I was trying to solve this puzzle, and want to clarify something.  It says "The prisoners can see the hats in front of them but not on themselves or behind."  Now, based on the diagram, and the description, this means B can only see A's hat, A can see none (since he's in front), and I assume that C can only see B's hat, correct?  This is not clarified, i.e. can C see B AND A's hat?

If C can only see B's hat, and B only A's, perhaps the wording should be:  "The prisoners can see the hat of the prisoner directly in front of them, but not themselves or behind."  Before I make the change, I want to be sure I'm interpreting the description correctly.  [[User:GregTheVirus|GregTheVirus]] 23:25, 26 July 2007 (UTC)

No, the statement is correct.  C can see the colour of the hats A and B [[User:Thisnamestaken|Thisnamestaken]] ([[User talk:Thisnamestaken|talk]]) 17:58, 30 August 2008 (UTC)

:I think it's unambiguous in the current wording, particularly because each prisoner can see the hat'''s''' in front of them. [[User:LightYear|LightYear]] ([[User talk:LightYear|talk]]) 05:22, 22 February 2012 (UTC)

== A different hat puzzle ==
The variant with three hats fails to say that the prisoners are aware which color is used three times and which only one. This information
is vital to make the case where all three (A, B and C) have the same color hat <i>trivial</i>. As far as I can tell, there is no solution,
if they do not have this information. Correct me if I'm wrong.. or correct the example otherwise.  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/128.84.98.99|128.84.98.99]] ([[User talk:128.84.98.99|talk]]) 20:36, 16 February 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

There are 3 prisoners, seated so that A can't see B or C, B can see A, C can see A & B.  The villian shows the prisoners 2 white hats & 3 black hats, then blindfolds them and puts a hat on each head. He says "When I remove the blindfolds I will give you 30 minutes.  If one of you, in 30 minutes can tell me the color of his own hat & prove it, you all go free, otherwise all die.  If any more than one speaks you all die."  When the blindfolds are removed, there is a 29 minute pause, then prisoner A says something, and they are all released.  What does he say? -- Answer: "If C saw two white hats in front of him he would have known he had on a black hat.  He said nothing, therefore either C & B both have on black hats, or one has a black hat and the other a white one. If B had seen a white hat, and heard nothing from C, he would have known that his own hat was black. Since he said nothing, I must have on a black hat."  

I don't know how to include this puzzle in the article, since it is of a somewhat different type. Should I broaden the article, or start a new one? Will someone else help me?  [[User:Too Old|Too Old]] ([[User talk:Too Old|talk]]) 04:55, 10 June 2008 (UTC)

==Enough Information?==
I felt like I was "tricked" despite it claiming not to be a trick question. Shouldn't the problem mention that the men are aware of the position of their fellow prisoners? I assumed they were completely oblivious to what was behind them. Perhaps I am just being a sore loser, but it seems like not enough information is provided, and the problem should be edited to include this information. Any thoughts? [[Special:Contributions/68.59.3.58|68.59.3.58]] ([[User talk:68.59.3.58|talk]]) 05:53, 29 May 2009 (UTC)

:Clarified it a little so it now sounds like the jailer explains the important rules to the prisoners. So each of the prisoners know as much as the reader. [[User:LightYear|LightYear]] ([[User talk:LightYear|talk]]) 05:22, 22 February 2012 (UTC)

==Ten hat puzzle==
As this puzzle is stated, the prisoner could just say the color of the hat of the next prisoner, instead of all that binary - deduction stuff. That's my plan if I ever go to jail anyhow.  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/85.167.15.96|85.167.15.96]] ([[User talk:85.167.15.96|talk]]) 15:16, 20 May 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
:That doesn't guarantee anything. The next prisoner will know his hat color, sure. But you only have a 50% chance of having that hat color yourself. But oh you, say: the prisoner behind me said my hat color too. But that doesn't help at all, because what if the color he said is different from the color of the hat in front of you(this will happen 50% of the time). Which color should you say then? If everyone is following the plan, then you are guaranteed to die if you say the color of the hat in front of you. But if you don't say the color of the person in front of you, then he will die. Knowing this, the logical decision would be to screw the guy in front of you and say your own hat color. Now assuming everyone can figure this much out, you can't trust that the person behind you is following the plan at all. That means your strategy would be completely useless. Assuming everyone followed your plan exactly, everyone would have exactly the same chance of survival as if they had no plan at all: 50%. With a slightly modified version of your method, you can guarantee that at least 50% of the people will survive as follows: The person in the back says the color of the hat in front of him. that person says this color. then the process repeats. That guarantees that half of the prisoners will survive and that the other half have a 50% chance of survival. And that's about the best you can do with anything close to the method you described. Maybe the article description needs to be written better to be more understandable. The back prisoner is just telling the others if there is an even(blue) or odd(red) number of red hats. Then the other prisoners just have to pay attention to how many people (ignoring the first) say they have a red hat. Then they know all the information they need in order to correctly decide their own hat color, because they know then how to interpret the line in front of them. If the running total of reds(excluding the first prisoner and including the hats they can see) is odd, then they say the opposite of the first prisoner, and if it is even, then they say the same as the first prisoner.--[[Special:Contributions/24.24.142.225|24.24.142.225]] ([[User talk:24.24.142.225|talk]]) 04:21, 30 October 2010 (UTC)
----------------------------------
Why can't B or A just ask the guy behind him? There's nothing in the puzzle description that says they can't converse.  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/160.83.72.206|160.83.72.206]] ([[User talk:160.83.72.206|talk]]) 19:46, 22 September 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
:It is listed as a variant of the original puzzle, and that was a requirement of the original puzzle, so it has been assumed here as well. If the puzzle was being described on its own, then that would have to of course be stipulated.--[[Special:Contributions/24.24.142.225|24.24.142.225]] ([[User talk:24.24.142.225|talk]]) 04:23, 30 October 2010 (UTC)

== faulty advertising ==


Hi,

The part of the original article that says "better solution to the countably-infinite variant" is not really better at all!

Why ?  Because the "better solution" allows the prisoners to HEAR what the first person says, but the variant being discussed explicitly disallows this, so it's toe tootly different things.

I'm glad to discuss this:  eric dot osman at rcn dot com    mar 16 2011  <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Ericosman|Ericosman]] ([[User talk:Ericosman|talk]] • [[Special:Contributions/Ericosman|contribs]]) 17:20, 16 March 2011 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

== Countably Infinite Hat Problem with Hearing ==

"When they are put into their line, each prisoner can see which equivalence class the actual sequence of hats belongs to." This is obviously false, as stated. The first prisoner can't see a goshdarned thing. I ''guess'' that this sentence is actually meant to be correct, and the problem ''statement'' is wrong -- seems to me it all works if everyone can see ''every'' hat. [[User:JoDu987|JoDu987]] ([[User talk:JoDu987|talk]]) 22:20, 16 September 2017 (UTC)
: The first prisoner can see all of the other hats. They're at the back of the line. The setup is that prisoner n can see the hats on prisoner m for all m>n, not for all m<n. I think the problem description already says this (each prisoner is said to face away from, not towards, the start of the line) but maybe this could be made more clear with more description or a diagram. [[Special:Contributions/2601:645:8302:AB26:F8F3:53EE:3858:5C5C|2601:645:8302:AB26:F8F3:53EE:3858:5C5C]] ([[User talk:2601:645:8302:AB26:F8F3:53EE:3858:5C5C|talk]]) 22:20, 14 October 2017 (UTC)
:: Cheers. I'm going to try editing the ''solution'' to de-confuse people like me. [[User:JoDu987|JoDu987]] ([[User talk:JoDu987|talk]]) 14:21, 15 October 2017 (UTC)
As far as I can see, the solution to this variant does not need the "equivalence relation" solution, but can be solved in exactly the same way as the "Ten-Hat Variant" (with hearing). In fact, that solution will work for any number as long as they can hear the other answers. Everyone still to answer, must just keep track of when the number of red hats flips between odd and even by listening to the answers behind them.

I didn't just want to edit the solution; so any comments please?  <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/170.252.123.161|170.252.123.161]] ([[User talk:170.252.123.161|talk]]) 12:34, 8 December 2014 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

It cannot be solved in the same way. If you have infinite number of red and blue hats, is their number even or odd? You can use the solution for an arbitrarily large finite constant, which has to be agreed upon beforehand, but everybody after that constant will have no idea of their hat color.  <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/193.66.174.253|193.66.174.253]] ([[User talk:193.66.174.253|talk]]) 07:59, 10 December 2014 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== Merger proposal ==
I propose that [[Prisoners and hats puzzle]] be merged into [[Hat puzzle]]. The two articles are about the same type of logical problem. There is no need to have two articles on the (almost) identical topic. '''[[User:Vanjagenije|<span style="color:#008B8B;">Vanjagenije</span>]] [[User talk:Vanjagenije|<span style="color:#F4A460;">(talk)</span>]]''' 20:44, 6 October 2015 (UTC)

I agree, though I would merge [[Hat puzzle]] into [[Prisoners and hats puzzle]], then rename this article, for convenience. [[User:Steve.dsign1|Steve.dsign1]] ([[User talk:Steve.dsign1|talk]]) 03:17, 2 June 2016 (UTC)

I also agree. The [[Prisoners and hats puzzle]] is just a more specific form of the [[Hat puzzle]]. So it should definitely be a sub heading of the topic.  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/182.48.233.25|182.48.233.25]] ([[User talk:182.48.233.25|talk]]) 17:37, 6 September 2016 (UTC)</small> <!--Autosigned by SineBot-->

I concur, with that which is stated above. Merging the [[Hat puzzle]] into 
[[Prisoners and hats puzzle]] for the efficacy of wiki users.  <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Joshbumpers|Joshbumpers]] ([[User talk:Joshbumpers#top|talk]] • [[Special:Contributions/Joshbumpers|contribs]]) 21:59, 12 November 2017 (UTC)</small> <!--Autosigned by SineBot-->
:Agreed, using the initial direction of the proposal (supported by most). {{done}} [[User:Klbrain|Klbrain]] ([[User talk:Klbrain|talk]]) 12:38, 28 November 2017 (UTC)

== Countably Infinite Hat Puzzle without Hearing ==

" In fact, even if we allow an uncountable number of different colors for the hats and an uncountable number of prisoners, the axiom of choice provides a solution that guarantees that only finitely many prisoners must die. The solution for the two color case is as follows, and the solution for the uncountably infinite color case is essentially the same:"

I don't think this is true. The *exact nature* of an uncountably infinite set is that it cannot be placed in a sequence. There can be no equivalence relation and no representative sequences if there are no sequences at all. I am deleting the references to uncountably infinite extensions of the problem until whoever added it can explain what they mean.  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/73.140.114.118|73.140.114.118]] ([[User talk:73.140.114.118#top|talk]]) 22:23, 18 October 2016 (UTC)</small> <!--Autosigned by SineBot-->

:An uncountable set can't be "sequenced" in the sense of being indexed by the natural numbers, but it can be "sequenced" by indexing on an uncountable ordinal, and such sequencing is not necessary anyway. If we think of the hat placement as a function from prisoners to colors, we can say that any two hat placements are equivalent if they differ on only finitely many prisoners, and we get the necessary equivalence classes. No sequencing is necessary. [[Special:Contributions/2601:645:8302:AB26:F8F3:53EE:3858:5C5C|2601:645:8302:AB26:F8F3:53EE:3858:5C5C]] ([[User talk:2601:645:8302:AB26:F8F3:53EE:3858:5C5C|talk]]) 22:06, 14 October 2017 (UTC)