I think Jim's solution is the optimal symmetrical solution, where each prisoner uses the same algorithm, but there might be better asymmetric strategies. A configuration C is a map C : {prisoners} -> {R, B} A guessing strategy is a map S:{configurations} x {prisoners} -> {R, B}, with the constraint that if C1(Q) = C2(Q), for all Q != P, then S(C1, P) = S(C2, P) (this expresses the fact that you can't see your own hat) Given a strategy S we have a "guessed-right" subset G of {configurations} x {prisoners}, where (C,P) is in G whenever S(C,P) = C(P) The size of G, for any strategy, is exactly half of |configurations| * |prisoners|, since when C1 and C2 only differ by prisoner P's hat, the constraint on strategies means that exactly one of (C1, P) and {C2, P) is in G. So we can divide the domain of S into pairs, each containing exactly one element of G. Since we can't change the total number of correct guesses (summed over all configurations and all prisoners), the way to maximize the number of configurations with 51 or greater correct guesses would be to have winning configurations with as close as possible to 51 correct guesses, and losing configurations with as close to 100 incorrect guesses as possible. Jim's solution does perfextly on the latter criterion; when the prisoners lose, every prisoner guesses wrong, which is perfect. But it does poorly on the first criterion; when there are 95 blue hats, for example, then 95, rather than 51, prisoners guess right, which is wasteful. If there were fewer prisoners who guessed right in these configurations, then there would be more correct guesses available for other configurations, allowing the possibility of fewer losing configurations.i If the prisoner's strategy is symmetric, then the number of correct guesses with 5 blue hats is either 0, 5, 95, or 100, which is why I think Jim's is the best symmetric solution. But an asymmetric one, where only 51 prisoners answer correctly with (at least some) 95-5 configurations, will leave more correct guesses available for other configs, possibly allowing us to decrease the number of "all-fail" configs. So I'm not convinced that Jim's solution is optimal when we include asymmetric strategies. Asymmetric strategies can be very complicated; not only do different prisoners have different algorithms, put a prisoner's guesses may depend not only on the hat count, but on exactly which prisoners have blue hats. I think I can prove that randomness doesn't help, that is, that the best nondeterministic strategy is no better than the best deterministic strategy. A nondeterministic strategy is map S:{configurations} x {prisoners} x P -> {R, B}, where P has a measure on it with total measure 1. P is the set f all possible "die rolls", or whatever other randomization technique the prisoners employ. The "Can't see your own hat" restriction in this case is just that for each p in P, the map S restricted to p satisfies the above restriction. Each element p in P has an associated set of success configurations (where 51 or more prisoners are correct). and the overall success probability of S is just the integral over P of the success probability of the strategy restricted to p. So the average value can never be greater than the maximum value, and there is some particular die roll we can choose in advance which does at least as well as the randomized strategy does overall. Andy On Mon, Jun 19, 2017 at 12:03 PM, James Davis <lorentztrans@gmail.com> wrote:
Me too. I was thinking that 51 answers that agree with the majority is enough, but we need 51 answers that are accurate to their own hat.
In a 51-49 split, the 51 folks who see 49-50 are those who would get the right answer under your strategy, but not necessarily the modified. The 49 folks who see the 51-49 split as 51-48 are *still* getting the wrong answer under the simple or modified strategy (Hence Dan's idea about switching). Since 51-49 or 49-51 is about twice as likely as 50-50, it seems tricky to make a rule that gives 50-50 a chance of success without dropping the success of 49-51 below 50%.
On Mon, Jun 19, 2017 at 10:56 AM, James Propp <jamespropp@gmail.com> wrote:
Why strike it? It convinced me! What's the fallacy?
Jim
On Monday, June 19, 2017, James Davis <lorentztrans@gmail.com> wrote:
Oops, strike that first paragraph! I'm inclined to agree with Propp.
On Mon, Jun 19, 2017 at 4:12 AM, James Davis <lorentztrans@gmail.com <javascript:;>> wrote:
I believe that this is best possible, but I don't have even the beginnings of a proof.
Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance of success on a 50-50 split, and only decreases the failure on a 49-51 overall split from 100% to ~100%, so I think the overall success is around 96% as the problem suggests.
It's interesting that the solution smacks of a (reverse) gambler's fallacy. Even more, if the problem slightly favored one color, you often put the prisoners in the paradoxical position of having to play an individually losing/irrational strategy that somehow works en masse.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com