= 27d567bc2d48d9f40e9ccc20ea370b15)
RichardKennaway comments on Open Thread March 31 - April 7 2014 - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (234)
Puzzle:
A countable infinity of prisoners are placed in a room so that they can all see each other, but are not allowed to communicate in any way and cannot see their own heads. The warden places on the head of each prisoner a red hat or a black hat. The prisoners will each guess the color of their own hat. They will all be released if at most finitely many of them guess incorrectly, and they will all be killed otherwise. The prisoners know all of this, and may collude beforehand. The prisoners are all distinguishable - think of them as being numbered 1,2,3,.... Again, once the warden has placed the hats, the prisoners receive no information other than the color of their fellow prisoners' hats. Prove that there is a strategy that guarantees a win for the prisoners.
(On my honor, this is possible.)
Pbafvqre gur sbyybjvat eryngvba orgjrra vasvavgr frdhraprf bs pbybhef: "qvssrerag va bayl svavgryl znal cynprf". Guvf vf na rdhvinyrapr eryngvba, naq jura gur ungf ner cynprq, nyy cevfbaref xabj juvpu rdhvinyrapr pynff gurl ner va. Guvf pynff vf pbhagnoyr, naq gur cevfbaref unir nterrq orsberunaq, gunaxf gb gur nkvbz bs pubvpr, ba n cnegvphyne rahzrengvba sbe rnpu rdhvinyrapr pynff.
Sbe rnpu cevfbare, rknpgyl gjb zrzoref bs gur pynff ner pbafvfgrag jvgu jung ur frrf. Ur thrffrf juvpurire nygreangvir pbzrf svefg va gur rahzrengvba. Bayl svavgryl znal bs gurz pna or jebat, orpnhfr gur pbzcyrgr frdhraprf vzcyvrq ol gurve jebat nafjref ner nyy qvssrerag, naq gur gehr frdhrapr unf bayl svavgryl znal naprfgbef va gur rahzrengvba.
Gur fnzr cebbs nccyvrf gb nal pbhagnoyr ahzore bs pbybhef. Vg'f abg pyrne gb zr lrg ubj zhpu ynetre gur ahzore bs cevfbaref naq gur ahzore bs pbybhef pna or. V fhfcrpg gung Bfpne_Phaavatunz wrfgf nobhg rkgraqvat gb erny-inyhrq pbybhef.
Correct! But it can be simplified (note that this is also a spoiler for the hard version):
Sbe rnpu rdhvinyrapr pynff cvpx n ercerfragngvir zrzore. Gura unir rirelbar thrff nf vs gurl jrer va gung frdhrapr. V guvax guvf jbexf sbe neovgenel pneqvanyvgvrf bs cevfbaref naq pbybhef.
EDIT: I remembered to ROT13 it.
This was my solution, and it does work for arbitrary cardinalities of colors and prisoners, as long as you're okay with the prisoners remembering arbitrary amounts of information. :)
Even harder version, to which this problem was a hint (and which I haven't solved yet, so please continue to ROT13 solutions):
There are countably many boxes 1,2,3,..., into each of which Alice places an arbitrary real number. Bob then opens finitely many boxes, looking at the real numbers they contain as he goes, and then names a single real number and opens a single unopened box. Bob wins if that box contains the number he named. Bob may condition his choice of boxes to open on what numbers he has already seen, and at each time step, he may choose the next box to open by random choice out of finitely many boxes that he identifies at that time step. Show that Bob has a strategy such that no matter how Alice chooses her real numbers, Bob wins--correctly predicts a real number--with very high probability.
I don't believe you.
This sounds related to this "proof of induction" by Alexander George. Sample quote:
Okay. I'm Alice. I placed random numbers into all boxes.
Your turn.
Yes! How simple!