>It is indeed a formidable strategy. Nevertheless, it is not
>optimal. In fact, the optimal solution is rather simpler.
>Happy hunting.

Yes, now I see it. This is a fine example of what happens when I get fixated on a particular feature of the original solution (parity) and try to generalize the solution based on that feature. A better approach would have been to rethink ALL of my assumptions and try to find the proper generalization of the original solution. Of course it is a truism that there are many ways to generalize any particular concept; the trick is to find the most felicitous one.

In this case, counting "white hat parity" can be thought of as assigning a value of 1 to white hats and 0 to black hats, then counting the white hats modulo2. The proper generalization is obvious when the original solution is described in this way: Simply assign values 0 through 6 to the hats, and sum the values modulo 7.

The first prisoner does this with no outside knowledge, so he has a 1/7 chance of going free. After prisoner 1 is gone, focus on only the set of remaining prisoners. Each succeeding prisoner sums (modulo 7) the values of all the colors he SEES together with all the colors he HEARS. This accounts for all the hats except his own. Subtracting this modulo 7 from the value stated by prisoner 1 gives the value of the current prisoner's hat.

This is pretty clearly optimal, since every prisoner except the first is saved, and the first has only a 6/7 chance of being lost. I think I would have solved this faster if I had started with the 7 color problem instead of trying to work up to it from the 2 hat problem.

Thank you for yet another interesting puzzle.

--Stuart Anderson