Previous Entry Share Next Entry
Colored Hat Solution -- and further discussion
Bar Harbor
alexx_kay
Solution to my recent Colored Hat Puzzle:

Assign each hat color one of the digits from 0-9. Any given set of hats must add up to some number. The total must end in a specific digit, also from 0-9. The prisoners each agree to assume a different final digit. One of the prisoners will be correct in their assumption, the other nine will not. When you see the other nine prisoners' hats, add up their numbers and see what the last digit of this (partial) sum is. Then, using your own assumption as to what the final digit should be when your hat is included in the final sum, do some simple arithmetic to determine the necessary number (and thus color) of your own hat.

This solution can be generalized to N prisoners if the prisoners all know (or can quickly learn) either the concept of modulo arithmetic, or arithmetic in arbitrary number bases. With exactly 10, however, only simple 'standard' arithmetic is needed.

Note that the odds of any *particular* person surviving are the same using this strategy as if they had guessed randomly, 1 in 10. This strategy just divides up the possibility-space in such a way that it guarantees exactly one survivor.

So, given that such a strategy exists, *should* you use it? The strategy puts a lower bound on the possible outcomes, but also an upper bound. Choosing randomly *could* let all ten of you survive (though very unlikely). Using this strategy guarantees that nine of you will die -- a very poor outcome.

If all prisoners are patriotic spies who desperately want one of them to survive to deliver the Death Star plans to the Rebel Alliance, then sacrificing the other nine makes some sense.

If two of the prisoners are a married couple who want to survive if *and only if* their spouse does also, then they definitely don't want to follow this strategy. I was talking this over with herooftheage, who came up with an elegant strategy that such a couple could follow in order to obtain their desired result. Can you? Does it work for a polyamorous relationship of 3? Or more?

I note that the statement of conditions does not say that the arrangement of hats will be random, only that it *might* contain a wide range of possibilities. Assuming I wasn't in the patriotic spy scenario, I would definitely assume that the hats would have a pattern, and base my guess on my own pattern-matching abilities. It's possible that the mad logician who has us imprisoned actually intends that and will deliberately provide us with a pattern. Alternately, he may not intend there to be a pattern, but leave the logistics of hat placement in the hands of a minion who isn't a random number generator.
Tags:

  • 1
huh. Reminds me of error correcting codes. Which I guess it is, in a way.

I was nowhere near a solution...
(Frozen) (Thread)

This seems needlessly complicated to me. If the desired outcome is survival of at least one prisoner, and there are as many hat colors as there are prisoners, why is the strategy not ' everyone pick a different color'?
(Frozen) (Thread)

because you're not guaranteed that anyone will be wearing the color hat they pick. The reason the solution is complicated is because though, in toto, the group has all the information about the hats, it has to use an algorithm to take advantage of that collective knowledge.
(Frozen) (Parent) (Thread)

Right, of course. Should have thought that through a little better!
(Frozen) (Thread)

If two of the prisoners are a married couple who want to survive if *and only if* their spouse does also

Solution:[Spoiler (click to open)]Same as before, but both spouses use the same number. 1/N chance they both go free, 1/N chance no one goes free, (N-2)/N chance exactly one other prisoner goes free. Can be expanded to the point where all prisoners or no prisoners go free.
(Frozen) (Thread)

[thinks a bit...] You are correct! That's not the answer I was thinking of, but it certainly works.

herooftheage's answer for 1 2-person couple was, much more elegant, and involved no math, but only worked for 2.
(Frozen) (Parent) (Thread)

More elegant, no math, only works for 2... probably this: [Spoiler (click to open)]Each guesses the color they see on their spouse. Also has a 1/N chance of success.

I just heard on the radio an ad for the All or Nothing lottery (you win if you match all the numbers or none of them). So what if we change the problem to say all prisoners go free if none of them guess right. Is there a strategy to do that with better odds than 1/(N^N)?
(Frozen) (Parent) (Thread)

Wait, my math was wrong. Random guessing would have a ((N-1)/N)^N chance.
(Frozen) (Parent) (Thread)

Yep.

I can beat your (corrected) odds if it is "All or Nothing", and I think that would be a nifty variant of the puzzle. For strictly Nothing, I don't see a way to improve on random chance.
(Frozen) (Parent) (Thread)

I meant strictly Nothing, but All or Nothing is an interesting variant. Let's use this rule: "All prisoners go free if they all guess correctly or all guess incorrectly. If there is at least one correct guess and at least one incorrect guess, all prisoners die."

I have strategies that always set the prisoners free for N=2 and N=3 (impossible to die in N=1).
(Frozen) (Parent) (Thread)

I'm pretty sure that the prisoners can always all go free for arbitrary values of N, if they have the concepts from the previous puzzle understood :-)
(Frozen) (Parent) (Thread)

I now have a solution so they always go free for N=4, but N=5 is not working.

Oh wait, you're thinking of the solution I myself gave for the polyamory version. Once again I'm going out of my way to make the problem much harder than it needs to be. (My solutions weren't using any math, and didn't even need to order the colors.)
(Frozen) (Parent) (Thread)

Confirmed.

I like this version of the puzzle better, because the insane logician ends up rewarding/punishing the whole group based on their performance. The originally posed version kills nine of them even if they get the 'right' answer, which seems needlessly wasteful.
(Frozen) (Parent) (Thread)


Am I correct in assuming that everyone here has heard the 100 Prisoners, 100 boxes with there names puzzle, or should I repeat it?
(Frozen) (Thread)

I don't recall it from that description, though I may well have seen it before.
(Frozen) (Parent) (Thread)

100 Prisoners, 100 boxes (numbered on the outside) each with a prisoner's name in it. Each prisoner individually goes into the room with the boxes and opens up to 50 boxes, then leaves and the room is reset. If EVERY prisoner finds their own name, they all go free, otherwise back to prison life (I hate the arbitrary death penalty these thing usually have). Prisoners can confer beforehand (but not after). Maximize their chances.

Picking randomly is a very low chance (1 in 2^100). Optimal strategy is MUCH better (around 20% IIRC).
(Frozen) (Parent) (Thread)

I can see a simple strategy to guarantee *worse* than random performance, so it stands to reason that a better-than-random strategy should exist. Haven't got it yet, though...
(Frozen) (Parent) (Thread)

Really? Other than doing stupid things like not opening all 50 different boxes?
(Frozen) (Parent) (Thread)

If everyone opens the *same* fifty boxes, half of them are guaranteed to fail, so the overall odds become 0%.
(Frozen) (Parent) (Thread)

Right. Of course.
(Frozen) (Parent) (Thread)

You have a reference on this solution? What you have here is the steps, and an assertion that it works. That's not the same as a proof.
(Frozen) (Thread)

By which I mean, not that I doubt you, but the assertion doesn't scratch my mathematician's itch. And I suspect reading someone else's analysis would be faster than trying to break it down myself.
(Frozen) (Parent) (Thread)

It's been long enough since I had to show every single step in order to get credit, that I'm well out of the habit. But here goes:

To me, "Any given set of hats must add up to some number. The total must end in a specific digit, also from 0-9." seems pretty obvious from the basic properties of base 10 arithmetic. Given that there are only 10 possibilities for the final digit, and also 10 prisoners, if each prisoner bases their guess on a different one of those 10 possibilities, so that each possibility is assumed by exactly 1 prisoner, then "One of the prisoners will be correct in their assumption, the other nine will not."

Given an assumption about the last digit of the total, and observation of the partial sum of nine observed hats, only one possible color-number, when added to the observed partial total, will yield the assumed last digit. If you can't handle subtraction, you can try brute force addition at that point, to see which color-number yields the assumed final digit, and which should therefore be your guess.

Does that help?
(Frozen) (Parent) (Thread)

Yes. And I see where my own thought block on the riddle was.

I had implicitly assumed not only that exactly one would be correct, but that that one would *know* he or she was correct when guessing, which isn't actually part of the stated puzzle. The problem was not about individuals knowing things and deducing an answer, but about a brute-force exploration of all possibilities.

This problem is... very Russian :)
(Frozen) (Parent) (Thread)

The casual validation I used before reading the official answer went like this, and perhaps it would be a good alternate formulation.

We code each color 0-9, and each person 0-9. Each person sums the colors they see, multiplies by 9, and adds their own number, i.e. person 0 adds 0. Their final answer is that number mod 10.

If we start with all hats as color 0, every person will see colors that sum to 0, multiply 0 by 9, and so result in simply responding with their own offset value, 0-9. For person 0, this answer will be correct, and for each subsequent person the distance from the correct answer will be their offset, so a complete set of error distances exists.

Now, if you increase the value of any one hat by m, you do two things: first, you change the error value of that individual by -m (i.e. if you turn person 0's hat to 7, they are now -7 from their correct answer); second, you change the sum everyone else sees by +m. Since the sums are multiplied by 9, and since we are taking mod 10, changing the visible sum by +m changes the result value (and consequently error distance) by -m. So both the changed individual and all the others have their errors adjusted by -m.

So, any adjustment to a single hat's value will result in a shift of individual's error distances, but maintain a complete distribution of errors. And since all combinations can be produced by single hat value adjustments, no combination can get rid of one person with error value 0. Also, no combination can save more than one person.
(Frozen) (Parent) (Thread)

...I'm sure there's a trivial solution, perhaps the same algorithm, that ensures *every* conspirator gets killed?

Useful if you don't want the information to get out...whatever it is.
(Frozen) (Thread)

I see a sort-of-cheat trivial solution: everyone says "octarine", or some other color that isn't part of the given set.

Playing fair, I actually don't see any way to ensure that everyone gets killed. All possible strategies appear to yield an 'expected' 10% survival rate (using the probability/economics meaning of 'expected'), they just rearrange how that expectation is parceled out.
(Frozen) (Parent) (Thread)

Hmm, I suspect to guarantee death everyone needs to know the color of their own hat with perfect accuracy, and the system of equations has too many unknowns for that...
(Frozen) (Parent) (Thread)

  • 1
?

Log in

No account? Create an account