![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jackPuzzle 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?
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?
no subject
Date: 2006-08-19 10:40 pm (UTC)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.
no subject
Date: 2006-08-19 11:12 pm (UTC)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 :-)