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.

metahackerI was nowhere near a solution...

tamarinneherooftheagetamarinnekgbooklogIf two of the prisoners are a married couple who want to survive if *and only if* their spouse does alsoSolution:[

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.alexx_kayherooftheage's answer for 1 2-person couple was, much more elegant, and involved no math, but only worked for 2.

kgbooklogSpoiler (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

noneof them guess right. Is there a strategy to do that with better odds than 1/(N^N)?kgbooklogalexx_kayI 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.

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

alexx_kaykgbooklogOh 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.)

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

corwyn_apAm I correct in assuming that everyone here has heard the 100 Prisoners, 100 boxes with there names puzzle, or should I repeat it?

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

alexx_kaycorwyn_apalexx_kaycorwyn_apumbranumbranalexx_kayTo 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?

umbranI 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 :)

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

metahackerUseful if you don't want the information to get out...whatever it is.

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

metahacker