Yeah, Andy has the right point of view here. I think that the prisoners can guess majority-correctly around 98% of the time. Think of the configuration space as the vertices and 1-dimensional edges of the 100-dimensional unit cube. A single vertex corresponds to one possible coloring of all prisoners' hats. Prisoner p gets to look at the other 99 hats, i.e. knows that the config is one of the two endpoints of one particular edge of the cube (an edge oriented parallel to the p'th basis vector). Therefore a strategy for the prisoners corresponds to assigning an *orientation* to each edge of the cube: the arrow on the edge tells the prisoner to guess the hat color they would have in the configuration the arrow points to. We want to orient all the edges so that most vertices have 51 arrows pointing at them, and the rest have ~100 arrows pointing away. If we didn't need to think about the connectivity of the cube, then of course this would be easy: for each group of fifty-one points, have one with 100 out-edges, and the other fifty with 51 in-edges and 49 out-edges. That would have the prisoners win 50/51 of the time. With an actual 100-dim cube, we surely can't quite attain that upper bound; for example the number of vertices is 2^100, which is widely known to not be a multiple of 51. But I have some hand-wavy intuition that says we should be able to get pretty close to it. Here's my plan. Pick a random 1/51 of the points to be the "losers" where we guess nearly all wrong. Now for each other point ("winner"), draw two paths connecting it to nearby losers. If it has two neighbors who are losers then this is really easy (and Bernoulli says that should be the case around 59% of the time). If you can't do this using just its immediate neighbors, then try to draw a path of length greater than 1 to a further-away loser, but don't use any already-used edges. Maybe this will be too hard with exactly ceiling(1/51) of the points being losers; those losers would need to end up with all 100 of their edges used by these paths. But if we increase the density of losers a bit, say from 1/51 = 1.96% to 2.5%, then on average each loser would only have around 80 of its 100 edges used by all the disjoint paths. It seems to me (hand-wavy!) that this is low-enough density that fitting all the paths in should be easy. Once we have this collection of edge-disjoint paths, we can easily build a strategy from it. For each edge on the path from a loser to a winner, orient all the edges to point from the loser end towards the winner end. Each winner now has two in-edges because of the two paths we drew connecting it to losers, plus some matched set of in/out pairs of edges because of other paths which passed through it, leaving an even number of not-yet-oriented edges. We can orient all of the remaining edges via Eulerian paths through the graph: the only places where these remaining paths would start/end are at the maybe-odd-degree losers, and so on all the winners, they preserve the property of having two more in-edges than out-edges. if we did go with 2.5% losers, then those vertices would each end up with around 10 people guessing correctly and 90 guessing wrong, while all the winners were 51-49 correct. The closer we can drive the loser density to 1/51, the closer the losers will get to all 100 people guessing incorrectly. How close you can come to optimal seems like a weird coding-theory-ish sort of question, but the fact that you can use arbitrarily long paths to connect winners to losers (as long as they all remain edge-disjoint) makes the codes point of view taste funny. --Michael On Mon, Jun 19, 2017 at 1:07 PM, Andy Latto <andy.latto@pobox.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.