100 hats puzzle, or, playing with the axiom of choice in the sand

[jack]

Puzzle the first, I assume you have heard this one, but I'll repeat it in case you haven't.

Suppose a hundred people are buried in the sand one in front of another so each can see all the people in front but none of the people behind. An Evil Dictator (TM) places a red or blue hat on each of them. He goes along the line from the back asking each person what colour their hat is, and at the end kills everyone who gets it wrong.

They're allowed to discuss strategy beforehand, but the dictator listens and doesn't allow them to come with any tone-of-voice signals or the like, information can only be conveyed by saying "red" or "blue" when asked.

What strategy is sure to save the most people? If the hats are colored randomly What strategy has the best Expectaion of number saved? For instance the first person is always at risk because NO-ONE knows anything about his hat at all, so no solution can do better than 99 guaranteed saved or 99.5 expected saved.

* You can save all the others. Agree a red/blue code where the first person calls odd/even for the number of red hats in front of him. Suppose the 2...n-1 people have been saved. Then the n'th person knows the of red hats behind him (because everyone just called the colours out aloud) and the number in front of him (because he can see them). The first person can also see the n'th person's hat, so if their count of red hats has the same even/oddness the n'th hat must be blue, else red.

Puzzle the second. What if the line was (semi) infinite?

* If you're willing to let die an infinite number, they can be as sparse as you like, the first, the googolplex'th, conway'th, the mindbogglinglybiggerthanthatth, etc. Just treat [1...googol-1] etc as many copies of the finite problem.

* To make things simpler, pretend the first guy doesn't have a hat and isn't killed. There's nothing you can do about him.

* If the sequence of hats eventually starts repeating you can save everyone: extrapolate the repeating sequence back to the first person (everyone can do this because they can see most of the repeating part) and consider the pattern of hats which differ from that. This is a finite number, so you can do the same trick as before, the first person calling out if the number of differing hats is odd or even, and everyone keeping count of the number behind them and then calling out the colour they expect unless they work out they must differ. (They have to remember the whole sequence because until it gets to them they won't know how many people were behind them, but it's possible if they think fast when it's their turn.)

* Treat red hats as 1 and blue as 0 and ignore the first one then they form a binary sequence n. If it's rational, it eventually repeats, so do the above thing. Otherwise it must uniquely represent a number between 0 and 1. What then? We can save everyone if we use the axiom of choice (who says it's useless :) )

Let x~y if x xor y is rational. This is an equivalence relation because r1^r2 repeats (with a product/lcm of the periods), so we can partition all sequences by it. From each class choose a representative x. Everyone can work out the x corresponding to n because if you change n by a finite number of digits (those behind the guy in the hat) it still ~n so has the same representative x.

Now consider n^x. This is rational, and you know a digit in it iff you know that digit in n, so use the same strategy as before counting those hats which differ from a x^n' where n' is a the repeating part of n extrapolated backwards.

* Can you do it without Choice? I bet you can't but I haven't proved it.

* If you don't have choice, can you manage a finite *expected* deaths?

Comments

[cartesiandaemon.livejournal.com]

I'm too tired to think clearly atm, what is your hash function?

[simont]

Divide the space of infinite bit streams into equivalence classes such that two streams are equivalent iff their bitwise XOR is computable by a finitely long program. (Or "is eventually repeating", as in your example; but I don't think it makes much difference.) Then invoke the Axiom of Choice to find a representative member of each equivalence class. Then, given an input bit stream, you XOR it with the representative member for its own equivalence class, giving a computable infinite bit stream, which you can then convert into the finite program which generates it and then generate a hash bit by some ordinary finite hashing method of your choice. Repeat infinitely many times, with a fresh invocation of the Axiom of Choice for each output bit, and you have an infinitely long bit stream derived from your input one.

I believe even an Infinity Machine cannot invert this function, because taking into account any finite subset of the output bits does not narrow down the possible inputs to the point where they cease to be uncountable. So you can't invert it in any step-by-step manner: you have to hash an entire infinite stream in one go and just hope it comes out right, which it will with probability zero.

Unfortunately, as far as I can see, each invocation of the AoC requires uncountably many bits to store its output, and uncountably many instructions to be executed to invent it in the first place, so an Infinity Machine as I've described it cannot compute such a hash function either! And if you go one better and introduce an Uncountable Machine in order to compute the hash, then the enemy will have an UM as well and can easily enough invert the hash, simply by hashing every infinite bit stream!

[simont]

Of course, you could compute something like this with only an IM, if you made your AoC choices lazily: literally implement a random oracle, which is handed an (integer,sequence) pair and picks a random representative element of the sequence's equivalence class, unless it's already seen an equivalent sequence beside that integer in which case it returns the same representative element it returned last time.

I think that would work, but the downside is that the random oracle would have to be accessible to everyone who wanted to use the same hash function, and they'd all have to trust it with their plaintexts even though those plaintexts were precisely what they didn't trust one another with. So an intractable transfinite computation problem has been turned into an intractable trust problem, which isn't much of an improvement...

[cartesiandaemon.livejournal.com]

"So an intractable transfinite computation problem has been turned into an intractable trust problem, which isn't much of an improvement..."

ROFL.

[simont]

... and (I can't believe it's taken me ten hours to realise) if you were willing to have a centralised Infinity Machine implementing a random oracle, you could simply use that random oracle itself as your hash function and not have to faff about with equivalence classes at all. D'oh!

[cartesiandaemon.livejournal.com]

Yes, thank you.

Am I right, you're intending that the Choice is random, and the choice function is made public?

So if you had lots of infinite machines with that function built in as an extra you would have your hash computable? Of course, it's somewhat cheating to specify the ability of your machine so precisely, I think.

[simont]

Yes, the choice function (in fact countably many separate choice functions) would form part of the definition of the hash algorithm, and hence would have to be public.

And yes, I agree that if you bolted an oracle implementing those choice functions on to the side of the Infinity Machine then it would become able to compute but not break the hash function. However, I also agree that that would be an unconscionable level of cheating :-)

[cartesiandaemon.livejournal.com]

Is it equivalent to using choice to generate e_i, each taking each sequence to 0 or 1 randomly, and considering the sequence of ei of input?

[cartesiandaemon.livejournal.com]

So, in summary, thank you. I think I agree with your analysis but am still thinking about it.