Here's an interesting small extension of the problem: prove that it is not possible to guarantee survival if 64 is replaced by some number that is not a power of 2.
Let's take a stab at the case with 3 squares/coins.
When the second prisoner comes in she will say that the magic square is 1, 2, or 3 based only on the state of the 3 coins. There are 8 possible states for 3 coins, so whatever strategy is devised must partition the 8 end states into the 3 outcomes. Since 8 is not divisible by 3, that means 1 outcome will be assigned at most 2 states.
Those 2 states can only by reached by 6 possible input states (since each input state can only reach 3 output states - one for each possible coin flip). That means there are 2 remaining possible input states that cannot reach the given outcome. So for any possible strategy the jailer can choose the output with only 2 states and one of the 2 input states that cannot reach it to foil the strategy.
There are 2^n possible end states to partition into n outcomes. So there must be at least 1 outcome given by at most 2^n/n end states. If n is not a power of 2, then 2^n is not divisible by n, so there must be one outcome with strictly fewer than 2^n/n states, call it m. However that outcome can only be reached mn input states. Since m < 2^n/n, we have that mn < 2^n. That means there are input states which cannot reach the given outcome. So for any possible strategy the jailer can choose the outcome with fewest possible end states, and then an input state that cannot reach that end state making it impossible for the second prisoner to reach that outcome.
Hm... solvability of the problem for a board of size n is equivalent to labeling the nodes of the n-cube with n colors in such a way that any node's neighbors take on all n colors (thus, each node will have one neighbor of each color). This means the number of pairs (A, B) of adjacent nodes such that B has any particular color must be the same as the number of ways to just choose A, which is 2^n. This is also the number of ways to choose B of a given color, times the n many ways to choose a neighbor for B. This means the number of nodes of any particular color is 2^n/n. As this must be an integer, we must have that n divides 2^n, and thus, n must itself be a power of 2.
