On Mon, Jun 19, 2017 at 8:04 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
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.
This is a really nice way to visualize the problem.
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).
I'm missing some details of this calculation; is it that 59% will be adjacent to two losers, or to at least one loser? How did you calculate this? Anyway, my intuition is that finding the edge-disjoint paths from each winner to 2 losers should be pretty easy, because of how strongly connected the hypercube is. If you're looking for a path from A to B, and A and B differ in the bits in set S, then the shortest path is of length S, flipping one of the bits in S each time (like an easy word-ladder). This already gives us |S|! paths to try, so there are likely to be problems only near the beginning or the end, where there are only |S| choices for the first and last steps, |S|*|S-1| possible edges for the second and penultimate steps, and so forth. But if all the choices for the next bit to flip would travel over an already-used edge, there are many, many, only slightly longer alternatives. Instead of flipping bit X, flip bit Y, Y!= X, then flip bit X, then flip bit Y back again. There are a hundred length-3 paths to use if your length-1 path is unavailable, And if all hundred of these are unavailable, there are thousands of length-5 paths to try. In the same way that collisions between cars happen much more than collisions between planes, because there's "more room" in 3 dimensions than 2, it's very easy to "go around" an obstacle in 100-dimensional space. I know a lot of work has been done on random graphs. What percent of the edges do you have to remove from a hypercube graph before the rest of it becomes disconnected? This sounds like a relevant fact, and like the kind of question that random-graph theory has already answered. Andy