Impossible Escape?

Avpr gb frr gur Cvtrbaubyr cevapvcyr va npgvba gurer.

Jbhyq lbh nyfb arrq gb nffvta gur fhvgf n 'fgeratgu' va gur rirag gung gur svany 3 funerq n ahzore? Va lbhe rknzcyr, ubj jbhyq lbh jbex bhg gur qvfgnapr vs gur 3 pneqf gung lbhe sevraq tnir lbh jrer gur xvatf bs urnegf, qvnzbaqf naq fcnqrf?

What is this trick called?

V guvax V zvffrq fbzrguvat, ubj qb lbh xabj vs lbh unir gb nqq be fhofgenpg gur qvssrerapr?

Sbe rkrzcyr: 3,X Pyhof, 8 Fcnqrf, 10 Qvnzbaqf, X Urnegf

Fb V erzbir "3 Pyhof" naq qvssrerapr vf 3 (fb V beqre gur erznvavat pneqf va gur guveq beqrevat beqre 213) ohg +3 naq -3 obgu tvir n ybjre inyhr guna X (3 be 10).

Vf lbhe nppbzcyvpr nyybjrq gb beqre gur pneqf gurl unaq lbh va gur jnl gurl pubbfr?

Vs abg, guvf frrzf yvxr vg fubhyq or vzcbffvoyr: gurer ner (52 pubbfr 5) frgf gung gur guveq cnegl pna pubbfr, naq bayl (52 pubbfr 4) frgf gung lbh pna or tvira, fb ol gur cvtrbaubyr cevapvcyr, lbh pna'g znc rirel 4-frg gb n havdhr 5-frg. Ohg lbh pna znc na beqrerq 4-frg gb na habeqrerq 5-frg.

Ohg V serdhragyl svaq gung zl cebbsf bs vzcbffvovyvgl ba guvatf yvxr guvf ner jebat, fb...

Cbffvoyl bhgfvqr bs gur fcvevg bs gur chmmyr, ohg lbh pbhyq rapbqr gur qngn ol hfvat pneq bevragngvba naq jung unaq vf hfrq gb cnff vg.

Vs V cnff lbh n pneq snpr hc, gura gung vf 01, snpr qbja vf 00. Vs V cnff vg gb lbh jvgu zl evtug unaq, gung'f 10, yrsg unaq vf 00.

4^4, vf 256 ovgf bs qngn gb jbex jvgu.

Sure. This doesn't seem so surprising to me; after all, the number of possible answers you may choose from for the question "Which bit do you want to flip?" is precisely the same as the number of possible answers you may choose from for the question "Which book do you want to specify?". (That's not a proof of sufficiency, mind you (the proof is the construction of the appropriate Hamming code). It's just reason to not find the result particularly counterintuitive.)

It's kind of like a counterpart to Martin Gardner's amazing observation in aha! Gotcha that you can store books with a single mark on a stick (assuming you can measure tiny distances with superhuman accuracy):

http://board.flatassembler.net/topic.php?t=16574

It's not physically realizable: people in that particular comment thread point out problems about the size of an atom, but there's also the Planck length, which I believe people theorize is in some sense a minimum size for objects in our universe, and I calculated that there are only around 2¹¹⁶ of them in a meter, so you could only store 116 bits by making a single Planck length-sized mark on a meter stick. :-( :-(

But it's a super-cool idea!

No, because then you can just flip the coin that doesn't affect the parity of any of the bits.

Nope—just flip the upper left coin (000000), as that has no effect on any of the parities. Flip the bottom right hand corner if you need to switch all the bits.

Not so - it's a little hard to parse out of the prose, but the author does make an attempt to touch on this in the example of the 2-square chess-board. Anyway, in the full chessboard implementation described here, if the board is already at parity you flip the coin at the top-left.

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.

Thanks for the interesting question.

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.

One of the constraints of the problem is that your friend can't touch the board, so, unless he has IR vision, that could be problematic.

Jailer notices that and waits for an hour before letting your friend in, all coins are room temperature by that point.

Another side effect generated from the experience :

There is no time limit for flipping the first coin, so if the guard choses the first square, I would wait 1 min before flipping mine. 60th square ? I would wait an hour.

If my friend outside is able to know precisely when I enter / exit from the room, he is able to know the correct square.

It's a way to reduce a large number of bits to a single bit. Each region defined on the board comes to represent one bit of the answer, and that bit is determined by the "direct sum" (or exclusive-or) of all of the coin positions in the region. A direct sum is basically addition with no carry, and in this case it's done base two (so 1+1 = 0, 0+1 = 1, 0+0=0). You can also think of it as an even/odd relation: if the number of 1's is even, the result is zero. If it's odd, the result is one. If you change any single bit, you flip the result.

Once you can do that, all you need is to be able to cleverly define your regions so that you can find a single square that overlaps with any given subset of them. Flipping the coin in that square would then change the direct sum for each of the overlapping regions, and you have your answer. You first read off the bits as they lay on the board you're given, then you figure out which bits you need to flip to turn that into the pattern you want, then you find the square that overlaps with all of those bits and flip that coin.

The way the regions are laid out in this case makes it possible to do just that - you can find a square that will overlap with any combination of the regions from none of them to all of them.

Wait, that's my blog post from ages ago! Looking over it now, one thing that might be appreciated here are the generalisations. For example consider a similar puzzle except instead of a chessboard and 64 coins, you have a 6x6 board, with one die on each square. Instead of turning over a coin, you must add 1 (modulo 6) to the value of exactly one of the dice (and reorient it). What is your strategy?

The jailer chooses which is the "magic" square.

Yes it does "The jailer explains all these rules, to both you and your friend, beforehand and then gives you time to confer with each other to devise a strategy for which coin to flip."