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.
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.
So, to repeat, it can indeed be proved that there is a rule—the “Hardin-Taylor rule”, I shall call it — that will, for any arbitrarily chosen function f, correctly predict most values of f on the basis of its past be- havior; that is, for most t the rule will correctly predict f(t) on the basis of f’s values at all s< t.
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!