Author |
Topic: Well-ordered hat execution (Read 4474 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Well-ordered hat execution
« on: Apr 5th, 2005, 5:50pm » |
 Quote  Modify
|
Countably infinitely many prisoners, labelled 0,1,2,..., are on death row. They are allowed to discuss a plan* before the following happens:
The prisoners are arranged such that each can only see the higher-numbered prisoners. A hat, black or white, is placed on each prisoner's head.
Starting with prisoner 0, and proceeding in order, each prisoner will guess his own hat color. Thus prisoner n hears the guesses of 0,1,...,n-1, and sees the hats of n+1,n+2,....
Any prisoners who guess correctly are released, and those who guess incorrectly are executed; what happens to whom is unknown during the guessing.
What plan will give optimal performance of its worst-case scenario?
*A plan here can be thought of as a function p=(p0,p1,...) from infinite binary strings to infinite binary strings: If prisoner n hears guesses g0,...,gn-1, and sees hats hn+1,hn+2,..., his guess is pn(g0,...,gn-1,hn+1,hn+2,...).
The prisoners therefore are allowed to agree on a function p in advance. There are uncountably many possible plans, so p can't really be communicated in a finite amount of time, but if you're willing to accept infinitely many prisoners, that shouldn't be a problem.
Hint: It may help to consider the following similar, simpler, but extremely surprising, situation:
If the prisoners can't hear each others' guesses, they can still guarantee that only finitely many die!
If you know what this means: What happens if the prisoners form an arbitrary ordinal? (I believe the only reason the prisoners need to be well-ordered is for the induction to go through.)
|
|
 IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Well-ordered hat execution
« Reply #1 on: Apr 9th, 2005, 4:24pm » |
Quote Modify
|
This result did seem impossible. 
| hidden: |
We say that two sequences ai and bi have the same tail, or are in the same tail class, if for some N, an = bn for all n > N. It's easy to see that this is an equivalence relation. For the no-hearing version, the prisoners simply decide on a representative for each tail class of sequences of black and white hats; each prisoner can determine which tail class their hats are in, and picks black or white to match the chosen representative. Beyond some N everyone will get the answer right, so only finitely many are executed. This is the best that the prisoners can do. Whatever strategy the prisoners use, and for any n, the executioner can pick an+1 arbitrarily, then pick an, an-1, ... , a1 so that everyone gets the opposite of what they will guess.
If you can hear the previous guesses, then you can save everyone but the first prisoner. For the sequence of hats the executioner chooses, let di be 1 if the sequence differs from the chosen representative of the tail class at the ith hat, and 0 if they are the same. We know that only finitely many will be 1. The first prisoner chooses white of the sum d1 + d2 + ... is odd, and chooses black if the sum is even. Each subsequent prisoner will know every hat except the first and his own, so he knows whether his hat differs from that in the chosen representative, and can pick accordingly.
What about larger ordinals? for alpha = omega*2, using the above definition of tail class doesn't seem to work - the people in the second omega sequence can't identify which tail class their hats belong to. Instead, we define two sequences to be in the same tail class if they differ in only a finite number of elements. Again, proving that this is an equivalence relation is straightforward. So the prisoners use the same strategy, and the same proof works; by induction, everyone knows all the previous hats except the first, and so he knows whether his hat differs from the chosen representative or not. So only the first person can be executed.
In the no-hearing version, the executioner can kill any finite number in any omega sequence; so he can kill an order type beta such that omega * beta >= alpha. For alpha a multiple of omega ^ omega, we have beta = alpha; in particular, beta can be alpha for alpha any uncountable cardinal.
|
OK, how about linearly-ordered hat execution? It's less clear how you define a strategy in this case, so I'll make two definitions: (in both cases, the prisoners form some linear order L)
1. A strategy is an set of functions {palpha, alpha in L}, where if prisoner alpha hears gbeta for beta < alpha, and sees hbeta for beta > alpha, the prisoner guesses p({gbeta}, {hbeta}). Such a strategy is only well-defined if for any sequence of hats, there is a unique sequence of guesses that satisfies the strategy.
2. A strategy is a map from binary functions on L (i.e. hats) to binary functions on L (i.e. guesses), such that there do not exist two sequences of hats and an alpha such that, for the two sequences, the alphath prisoner will see the same hats and hear the same guesses, yet will give a different guess for each sequence.
I believe #2 allows a wider range of strategies than the first, but I'm not clear on precisely what strategies we can define. For Z and Q, I'm guessing the executioner can kill infinitely many; I don't think there's any way to insure everyone below some value will all guess correctly. But I'm having trouble trying to prove anything without a starting point.
|
| « Last Edit: Apr 9th, 2005, 10:46pm by Deedlit » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Well-ordered hat execution
« Reply #2 on: Apr 9th, 2005, 5:34pm » |
Quote Modify
|
Excellent! Here's a result that's even more surprising:
Suppose now there are omega1 prisoners, each in his own soundproof cell. Thus no prisoner can see any hats or hear anybody else's guesses. Of course now there's no way to guarantee any of them will guess their own hat; instead, they are asked only to name the hat color of everybody before them. A prisoner needs to get them all right to survive. (Prisoner 0 gets out of jail free.)
Is there a strategy which will guarantee that infinitely many of them survive?
It is consistent with ZFC that the answer is yes! This follows from Jensen's Diamond.
Another interesting consequence of Diamond is that Souslin's conjecture is false.
I don't know what you can do if they're not well-ordered. For example, with Q, you can save every prisoner numbered at least 1, as well as infinitely many in every initial segment.
Can you always save all sufficiently high-numbered prisoners?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Well-ordered hat execution
« Reply #3 on: Apr 9th, 2005, 5:37pm » |
Quote Modify
|
It is frustrating when a puzzle you've been stuck on turns out to have an "obvious in hind-sight" solution!
If the prisoners are in a general linear order, then their indexes will not necessarily be ordinals. Let L be the index set, so 2L is the set of all maps from L into {0,1} (0=black hat, 1=white hat). A strategy is a map P: 2L --> 2L with the property that for all a, b  2L, y L, if a(z) = b(z) for all z other than y, then P(a)(y) = P(b)(y).
As with Deedlit, a 2L represents a possible sequence of hats, and P(a) the guesses the prisoners should make. The condition on P indicates that prisoner y's guess does not depend on his own hat color. I believe this is Deedlit's second choice of strategy definition. But the "ordinal" terminology leaves me wondering (ordinals by definition represent only well-ordered sets).
First, suppose L has a least element (for instance, the non-negative real numbers). The same strategy still works. The type is still determinable, and the initial player can still provide corrective information for the finite number of disagreements from the type representative.
Suppose L has no least element. At the very least, some prisoner can be chosen (as early as possible in the line-up) to act as initial prisoner, with everyone before him left to chance.
Beyond this, though, it may be impossible to define a strategy - such a function's existance may be provable only by using the Axiom of Choice.
|
| « Last Edit: Apr 8th, 2007, 11:46am by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Well-ordered hat execution
« Reply #4 on: Apr 9th, 2005, 5:48pm » |
Quote Modify
|
on Apr 9th, 2005, 5:37pm, Icarus wrote:| First, suppose L has a least element (for instance, the non-negative real numbers). The same strategy still works. The type is still determinable, and the initial player can still provide corrective information for the finite number of disagreements from the type representative. |
|
That certainly sounds true, but it's not clear to me how you'd prove it works without induction.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Well-ordered hat execution
« Reply #5 on: Apr 9th, 2005, 10:42pm » |
Quote Modify
|
Whoops!  I meant to be talking about index sets of course, but I had ordinals on the brain.
on Apr 9th, 2005, 5:48pm, Eigenray wrote:
That certainly sounds true, but it's not clear to me how you'd prove it works without induction. |
|
Under definition 2, all you need to do is prove no one is using more information than they have - easy enough in this case, since you everyone know's everyone else's hat except for the first. So you might consider definition 2 as begging the question.
Note that even if there is no smallest element of L, we can take any set that is unboundedly small to save the rest - for the reals, we can take the negative integers, so we can save all but aleph0 prisoners.
Under definition 1, we have to prove that there is no other possible choice of guesses that fit with everyone's individual strategy. But I don't think our current strategy precludes this - we need to be more careful about how we pick our type representatives.
Eigenray, does your answer for Q work under definition 1? Maybe we can make it work under other linear orders.
Random question: any reason for the use of terms like diamond and club?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Well-ordered hat execution
« Reply #6 on: Apr 10th, 2005, 9:43am » |
Quote Modify
|
For Q, you can have prisoner -n act as the first prisoner for those labeled a/n, with (a,n)=1, a>-n2 (a well-ordered set). Then all prisoners > -1 live, and out of the ones > -n, no more than ~n3 die.
on Apr 9th, 2005, 10:42pm, Deedlit wrote:| Under definition 2, all you need to do is prove no one is using more information than they have - easy enough in this case, since you everyone know's everyone else's hat except for the first. |
|
But why is that? Surely, if all prisoners < x guess right, then x will too. But without induction / well-ordering, I don't see why anyone would have to guess right.
I'd like to believe this though, because suppose the prisoners are well-ordered, but they face backwards. Then you should be able to lose no more than their cofinality. Somewhat paradoxically, that could mean fewer people die if there are [aleph][omega] prisoners than if there are [aleph]1.
As for "Diamond," at least it's more creative than, say, "Martin's Axiom."
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Well-ordered hat execution
« Reply #7 on: Apr 10th, 2005, 7:43pm » |
Quote Modify
|
Just when I think I have this figured out, it throws another wrinkle at me. This is about the 4th time I have started to post, only to realize something in the middle that made me throw out what I had done and think about it some more.
If the prisoners know the outcome of the guesses of their predecessors, then I believe that there is no problem in the linearly ordered case with initial prisoner. Each prisoner knows what the sequence before him is regardless of the answers of the preceding prisoners (if they got it wrong and were killed, then he knows that their value was the opposite of what was said). This means that you can induct on the number of prisoners preceding whose hat color differed from the representative sequence (since this is only a finite # of prisoners, it is well-ordered).
If there is no initial prisoner, or if prisoners do not know the fate of those before them - just their guesses, then I believe that the problem is undecidable. Certain strategies definitely succeed in saving some prisoners, but others exist that are better if they work. But unfortunately, whether or not they would work cannot be decided from the implied axioms.
Eigenray is correct in this: it is not enough to show that a given prisoner only answers on the basis of his own knowledge. The strategy in question assumes that the information he receives from earlier prisoners is true. If more than a finite number of the answers were false, then the prisoner will not be able to pick the right equivalence class and right representative. And even if the number of bad answers is finite, they still may cause him to adjust his own answer in the wrong way.
It is this assumption that his predecessors answered correctly that undermines any proof. One can also assume that his predecessors answered wrong, leading him to answer wrong as well, with no contradiction.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Well-ordered hat execution
« Reply #8 on: Apr 10th, 2005, 9:08pm » |
Quote Modify
|
on Apr 10th, 2005, 9:43am, Eigenray wrote:But why is that? Surely, if all prisoners < x guess right, then x will too. But without induction / well-ordering, I don't see why anyone would have to guess right.
|
|
Under definition 2, which is the same as Icarus' definition, you don't need too - it's simply assumed.
Quote:
Eigenray is correct in this: it is not enough to show that a given prisoner only answers on the basis of his own knowledge. The strategy in question assumes that the information he receives from earlier prisoners is true.
|
|
Well, it isn't necessarily correct or incorrect, just how we choose to extend the problem. I prefer to be agnostic about it since either version could be interesting - this isn't an applied problem, after all!
Quote:| It is this assumption that his predecessors answered correctly that undermines any proof. One can also assume that his predecessors answered wrong, leading him to answer wrong as well, with no contradiction. |
|
It doesn't necessarily undermine any proof - with the right strategy, it might be that no other choice of hats will match the guesses given.
|
| « Last Edit: Apr 10th, 2005, 9:15pm by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Well-ordered hat execution
« Reply #9 on: Apr 11th, 2005, 5:50pm » |
Quote Modify
|
It looks like under definition 2, you can solve Q, R, and Z with just one person executed!
Again, we choose a random type representative for each class, and if the chosen sequence differs at prisoners a1 < a2 < ... < an, then we have prisoner n a1 - a2 - ... - an - 1 give the answer opposite that of the type representative. Everyone else answers correctly. The individual strategy is as follows: if everyone behind you guesses according to the type representative, then you just need to check if your number satisfes the above expression, based on the who's in front of you; if so, give the opposite answer, otherwise give the same. If someone behinds you guesses opposite, check if the first opposite answer satisfies the above; if not, you must have an opposite hat as well.
Now that I think about it, this will work for any linear order; we can't choose the informing person constructively like we did above, but the following should work. Divide the set of prisoners into two classes, both unbounded at the lower end. By the axiom of choice, for each odd set of prisoners we can choose a lower prisoner from the first class, and for each even set of prisoners we can choose a lower prisoner from the second class. So we just need a single informer, for any linear order!
So that takes care of definition 2 - just as well, since you guys don't seem to like it.  Definition 1 looks pretty hard, however; I suppose it could be undecidable, or there could be some clever type of strategy to make it work. 
|
| « Last Edit: Apr 11th, 2005, 6:20pm by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Well-ordered hat execution
« Reply #10 on: Apr 11th, 2005, 10:45pm » |
Quote Modify
|
Inspired by Eigenray's diamond problem, here are a few more. As in Eigenray's problem, the prisoners are arranged in an ordinal, and each person guesses the hats of the previous prisoners.
For which ordinals alpha is it necessarily true that:
1. there are two prisoners with compatible guesses. (they guess the same hat for everyone behind both of them)
2. for any beta < alpha, there are two prisoners > beta with compatible guesses.
3. there is an unbounded subset of prisoners with compatible guesses.
4. there is a stationary subset of prisoners with compatible guesses.
It seems easier to come up with sufficient conditions than necessary.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Well-ordered hat execution
« Reply #11 on: Apr 12th, 2005, 5:21pm » |
Quote Modify
|
on Apr 11th, 2005, 5:50pm, Deedlit wrote:| So that takes care of definition 2 - just as well, since you guys don't seem to like it. |
|
It's not the definition of a strategy that is the problem. It is the proof of this stragegy which depends on an unjustified assumption. Namely, that the prisoners will "begin" by knowing the right representative. Each prisoner, in deciding their own answer, assumes that previous prisoners answered according to the appropriate choice of representative (and adjusted for the strategy). This is necessary for the current prisoner to know what the correct representative is.
If you assume that previous prisoners knew the right representative, then this prisoner will as well, and everything is consistant.
If, on the other hand, you assume that the previous prisoners failed to come up with the right representative, the current prisoner will not be able to either. Again, everything is consistant.
Induction gets out of this situation by providing one case that definitely works. But you have no such case. You are simply assuming that it is true.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Well-ordered hat execution
« Reply #12 on: Apr 12th, 2005, 5:59pm » |
Quote Modify
|
I'll quote your version of definition 2 since it is written more nicely than mine:
on Apr 9th, 2005, 5:37pm, Icarus wrote:If the prisoners are in a general linear order, then their indexes will not necessarily be ordinals. Let L be the index set, so 2L is the set of all maps from L into {0,1} (0=black hat, 1=white hat). A strategy is a map P: 2L --> 2L with the property that for all a, b c[ 2L, y c L, if a(z) = b(z) for all z other than y, then P(a)(y) = P(b)(y).
|
|
The question I asked was, "What strategy gives the fewest number of prisoners executed in the worst case scenario?" I claimed there was a strategy in which at most one prisoner was executed, then presented that strategy. That is, I presented a map P: 2L --> 2L with the domain meaning the color of the hats and the range meaning the color of the guesses, in which at most one person was executed. Then I showed that the above condition was satisfied. That's really all there is to it.
I don't see that there is anything above to quibble about mathematically - it's pretty straightforward. What you seem to be arguing is that the above definition doesn't conform with your intuition of what could be considered a realizable "strategy" for the prisoners. That's perfectly reasonable; I wouldn't argue with it, and haven't. But your problem is with how we chose to interpret it formally (in this version), not the solution to the formal problem.
Why didn't I just make definition 1, if that is the obvious "right" definition? The thing is, definition 1 doesn't really alleviate your concerns - even though we know there is only one choice for each prisoner that will make everything work out in the end, there's no way to know in advance what the choice should be. So again, the prisoners must "begin" by knowing the right representative - it's just an artifact of the prisoners not being well-ordered. There's no perfect definition, so I went ahead and made two.
I suppose one could then reject the entire problem, saying it's pointless. That's not my view - there's still an interesting mathematical problem inside, and whether it is couched as a real-world problem that doesn't really make sense doesn't matter so much to me.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Well-ordered hat execution
« Reply #13 on: Apr 12th, 2005, 7:04pm » |
Quote Modify
|
on Apr 12th, 2005, 5:59pm, Deedlit wrote:That is, I presented a map P: 2L --> 2L with the domain meaning the color of the hats and the range meaning the color of the guesses, in which at most one person was executed. Then I showed that the above condition was satisfied.
...
What you seem to be arguing is that the above definition doesn't conform with your intuition of what could be considered a realizable "strategy" for the prisoners. |
|
Not at all. My argument is cold-hard logic, not intuition. And it has nothing to do with what is a realizable strategy (no strategy is "realizable" in any sense that I know of, as the problem itself is not realizable). My point is that your argument "that the above condition is satisfied" is flawed. That is, you have failed to show the existance of a P satisfying the condition. Your "proof" requires an assumption that is not justified by either standard axioms of set theory, or information given explicitly or implicitly in the problem.
It is not that your definition of P is bad. It is just that it's existance is actually independent of the "axioms" - the information available. There are two separate "mathematical theories" for this problem - one in which your P exists, and one in which it does not. Both are consistent. I know this situation is familiar to you! You have discussed elsewhere such matters as the Continuum Hypothesis, which - as you know - can be taken as true or as false. The existance of your P is like the CH in this.
Definition 2 has problems because it requires the prisoner to know something that he cannot be guaranteed to know. That is, what the actual sequence of hats before him is. All he knows is his predecessor's guesses. The best way around this problem, in my opinion, is simply to state that each prisoner knows what happened to his predecessors - whether they guessed right or wrong. Then he can deduce what the sequence of hats was - regardless of whether anyone before him got it right. Then your argument works.
But if the prisoners are unaware of the outcomes for earlier prisoners (e.g.,the executions are carried out in masse after everyone has their turn), they have only the previous guesses to go on. Without some additional lever, these could be either right or wrong. If they are wrong and the strategy depends on them being right (like yours does), then his answer may be wrong too.
Definition 1 does not have this problem. The strategy depends only on the guesses of the earlier prisoners, which we are given that each prisoner does know. So if you can find a definition 1 solution, you will be on firmer ground.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Well-ordered hat execution
« Reply #14 on: Apr 12th, 2005, 9:59pm » |
Quote Modify
|
on Apr 12th, 2005, 7:04pm, Icarus wrote:
My argument is cold-hard logic, not intuition. And it has nothing to do with what is a realizable strategy (no strategy is "realizable" in any sense that I know of, as the problem itself is not realizable).
|
|
In that case, the argument should have nothing to do with whether there are prisoners using forbidden "knowledge", only with the the problem of finding the specified map. I haven't gleaned an argument like that from your previous posts.
Quote:
My point is that your argument "that the above condition is satisfied" is flawed. That is, you have failed to show the existance of a P satisfying the condition. Your "proof" requires an assumption that is not justified by either standard axioms of set theory, or information given explicitly or implicitly in the problem.
|
|
Perhaps you could state what this assumption is? All I can think of is that you mean I am assuming that the prisoners "know" what the previous prisoners have on their heads. But again, this is a problem of interpretation - it has nothing to do with the formal problem using definition 2.
Quote:
It is not that your definition of P is bad. It is just that it's existance is actually independent of the "axioms" - the information available. There are two separate "mathematical theories" for this problem - one in which your P exists, and one in which it does not. Both are consistent.
|
|
I'm not getting this. My definition of P is completely straightforward, given the choices already made. The "iffy" part is perhaps the choice of type representatives, the division of the linear order into even and odd classes, and the mapping from finite sets to elements of the appropriate class lower than all elements of the set. These all require the axiom of choice to define. Once we have done this, the definition of P is simple - we look at how the choice of hats differs from the type representative, map this finite set to the appropriate lower element, and define P(x) to be x with that one element switched. Nothing here that can't be done in ZFC.
If the problem is with the proof that P satisfies the desired property, I don't see that either. The proof is straightforward - I'll say it again, phrased a little differently.
We wish to show that there are not two choices of hats, x and y, such that x and y are the same beyond a particular prisoner, P(x) and P(y) are the same below that prisoner, and P(x) and P(y) differ for that prisonner. The key observation is that P(x) differs from x at precisely one prisoner, and the prisoner is behind all prisoners whose hats differ from the type representative. Thus, if any of the guesses differ from the type representative, we know what hats the previous prisoners are wearing - the first person who differed is actually wearing the same hat as in the TR (type representative) and the others who differed are wearing the opposite hat of the TR. Thus we know every hat except for the prisoner's, and that is determined by which class the first differing prisoner belongs to; and we also know that the prisoner is assigned to guess correctly. So there is only one possible guess for the prisoner. On the other hand, if the prisoner doesn't hear any differing guesses, then we know that every hat behind the prisoner, and also his own, must match the TR. So every hat is determined, and therefore whether or not the current prisoner is the one who is supposed to switch. All this seems perfectly straightforward; I'm not seeing any similarity to CH or any other independent statement!
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Well-ordered hat execution
« Reply #15 on: Apr 12th, 2005, 10:19pm » |
Quote Modify
|
on Apr 12th, 2005, 7:04pm, Icarus wrote:
Definition 2 has problems because it requires the prisoner to know something that he cannot be guaranteed to know. That is, what the actual sequence of hats before him is. All he knows is his predecessor's guesses. The best way around this problem, in my opinion, is simply to state that each prisoner knows what happened to his predecessors - whether they guessed right or wrong. Then he can deduce what the sequence of hats was - regardless of whether anyone before him got it right. Then your argument works.
But if the prisoners are unaware of the outcomes for earlier prisoners (e.g.,the executions are carried out in masse after everyone has their turn), they have only the previous guesses to go on. Without some additional lever, these could be either right or wrong. If they are wrong and the strategy depends on them being right (like yours does), then his answer may be wrong too.
|
|
Now this is why I said that your problem was with the definition of strategy, and not the mathematical problem determined by it! Perhaps your previous objection is unrelated to what you just wrote above, but that's not what I'm gathering from your posts.
When you say that definition 2 requires a prisoner to "know" what the sequence of hats before him is, remember that definition 2 doesn't say anything about a prisoner's "knowledge". So we have to formalize what we mean by "knowledge" before I can answer this. I'm not clear on what you claim to be an indication that a prisoner "knows" something, but I can describe the intuition that inspired defintion 2. If, under a particular strategy and for a particular prisoner, the relation between a certain set of information and the prisoner's guesses doesn't associate the same information to two different guesses, then we can reasonably say that the prisoner doesn't have to "know" anything more than that information. In this case, whenever a prisoner hears a certain set of guesses and sees a certain set of hats, there is only one possible guess the prisoner can make - so you can't say the prisoner has to "know" something else.
Of course, you can still object that the prisoners, as a group, somehow arrived at the given strategy when it doesn't follow from the individual strategies of the prisoners. That's fine - you don't like definition 2. That's not something I can argue with. But this is a subjective opinion, on how well a formal mathematical problem conforms with an English language description. I can't reconcile this with some of your statements about cold-hard logic, having nothing to do with definition 2, etc.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Well-ordered hat execution
« Reply #16 on: Apr 13th, 2005, 7:55pm » |
Quote Modify
|
I suppose you are correct that the problem is with in the definition of the strategy. Definition 2 only provides a provably valid strategy when the prisoners know the actual mapping of hats preceding them. This is an assumption built into the definition: P is dependent on the entirety of the mapping of hats h, except for the diagonal values (Py(h) does not depend on h(h)). So Py(h) can be dependent on h(x) for x < y.
But, if we assume that prisoners are not aware of the results of the guesses before their own (whether they were right or wrong), they have no way of obtaining this information. In this case, any viable strategy cannot have prisoner y's guess depending on the hat color for prisoner x, if x < y, as y has no guaranteed way of determining what x's hat color was.
In your proffered map P, Py(h) is dependent on values of h(x) for x<y. Thus, like definition 2 generally, it applies to the "know what happens before you" case only.
But as a solution for the Definition 2 case, I accept that it does work.
For the more general problem, where prisoners are aware only of the guesses of those before, only definition 1 is consistant with the problem.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Well-ordered hat execution
« Reply #17 on: Apr 13th, 2005, 8:48pm » |
Quote Modify
|
That's a reasonable assessment. The weird thing is that there's a difference between what people do individually and what the collective group does. Any finite group of prisoners can assert that they don't know the prisoners' hats behind them and haven't used that information, but in definition 2, somehow the collective group has to know. In definition 1, there's only one solution, but somehow they collectively have to grope their way there.
I guess that's more than enough discussion of this, but I haven't really gotten any further on the actual problem, so nothing else to talk about. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print