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