8 ms·
Impossible Escape?
- bevarum 12y agowhew... I look forward to sharing this one - thanks
- rthomas6 12y agoThe description at the beginning doesn't say the two prisoners are allowed to communicate and agree on rules for information transmission before being led into the room.
- h1ckb 12y agoYes 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."
- DEinspanjer 12y agoOr it could just be assumed that both you and your friend read Hacker News. :)
- deleted 12y ago[deleted]
- deleted 12y ago[deleted]
- TrainedMonkey 12y agoPretty awesome, you can change only one bit of information, but you have 64 choices (6 bit selectivity) for which bit to swap and that is what solution utilizing to manipulate up to 6 bits of information at once.
- lisper 12y agoA minor quibble: the rules imply that you have to flip a coin. If the layout happens to already have all the right parities with respect to the magic square then you're screwed. [UPDATE: this it wrong, but since three people have already responded explaining why I thought I would try to head off additional replies at the pass.]
- cecilpl 12y agoNo, because then you can just flip the coin that doesn't affect the parity of any of the bits.
- mrmaddog 12y agoNope—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.
- lisper 12y agoOh, right. (Duh.)
- chias 12y agoNot 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.
- spdustin 12y agoI'd tell my friend to feel for the warm coin, and I'd hold the coin I'm intended to flip as long and as tightly as possible before flipping it.
- JonathonW 12y agoOne 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.
- spdustin 12y agoDoesn't have to touch the board. Just the coins. It's semantic distinction, sure, but if the jailer is capricious enough to envision this challenge, he should be impressed by a solution's cleverness.
- TrainedMonkey 12y agoJailer notices that and waits for an hour before letting your friend in, all coins are room temperature by that point.
- Spl3en 12y agoAnother 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.
- sarciszewski 12y agoHeh. Timing side-channel for the win. :D
- arghbleargh 12y agoHere'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.
- Chinjut 12y agoHm... 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.
- ddlatham 12y agoThanks 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.
- ddlatham 12y agoAnd to generalize: 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.
- maxerickson 12y agoAn earlier take on it: https://ocfnash.wordpress.com/2009/10/31/yet-another-prisoner-puzzle/ https://ocfnash.wordpress.com/2009/10/31/yet-another-prisone...
- ocfnash 12y agoWait, 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?
- blueflow 12y agoReally interesting. Does anyone knows some literature about solution-finding strategies like this?
- deleted 12y ago[deleted]
- martingordon 12y agoHere's a similar puzzle that can be used as a fun bar trick: Given a standard deck of 52 cards, a third party chooses any five from the deck and hands them to your accomplice. Your accomplice chooses four of the five and gives them to you, with which you identify the fifth card. What's the strategy? Solution (In Rot-13, http://rot13.com/index.php http://rot13.com/index.php): N fvzcyr beqrevat bs sbhe pneqf qbrfa'g jbex, fvapr 4! bayl nssbeqf lbh 24 pbzovangvbaf (cyhf gur sbhe lbh unir). Jvgu svir pneqf naq bayl sbhe fhvgf, lbh xabj bar bs gur fhvgf zvtug or qhcyvpngrq. Lbh pna hfr gur svefg pneq gb fhccyl bayl fhvg vasbezngvba, ohg gur erznvavat guerr pneqf bayl nssbeq 6 pbzovangvbaf (cyhf 1-4 vs lbh unccra gb qenj pneqf zngpuvat gur gnetrg'f fhvg). Gur frperg vf gb pubbfr juvpu bs gur gjb pneqf gb unaq bire. Jvgu 13 pneqf va rnpu fhvg, gur znkvzhz qvfgnapr orgjrra nal gjb pneqf (nyybjvat sbe jenc nebhaq) vf 6. Ol nterrvat gb nyjnlf unaq bire gur fznyyre/ynetre bs gur gjb pneqf va gur fnzr fhvg nf lbhe fhvg vqragvsvre, lbh pna hfr gur erznvavat guerr gb vaqvpngr gur qvfgnapr hc/qbja sebz gung pneq. Sbe rknzcyr, tvira: 3,5 Pyhof, 8 Fcnqrf, 10 Qvnzbaqf, X Urnegf Qhcyvpngr fhvg vf pyhof, fb jr'yy unaq bire gur fznyyre bs gur gjb (3 Pyhof). Gur qvfgnapr orgjrra 3 naq 5 vf 2, fb jr unaq bire gur gur erznvavat guerr va gur frpbaq ybjrfg beqrevat bs gur pneqf (v.r., 132: 8 Fcnqrf, X Urnegf, 10 Qvnzbaqf).
- kevan 12y agoAvpr gb frr gur Cvtrbaubyr cevapvcyr va npgvba gurer.
- stumacd 12y agoJbhyq 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?
- martingordon 12y agoYes, that's correct. I thought I had that in the post but it may have just been a draft version. I use nycunorgvpny because it's easy to remember.
- Kiro 12y ago
- DominikR 12y agoIf I understand this correctly (please correct me if I'm wrong) it would imply that one could encode an arbitrary number of bits by flipping only one bit on such a board with a random state, as long as the board is sufficiently large. You could for example encode book X by flipping one bit on some space, or a different book Y by flipping some other bit instead on another space on the exact same board, which is a fascinating thought to me. So if I take this description on orders of magnitude from Wikipedia: "5 000 000 bits – Typical English book volume in plain text format of 500 pages × 2000 characters per page and 5-bits per character." This would mean that the board would need to have a size of 2^5000000 spaces to successfully do this for texts of up to 500 pages x 2000 chars per page.
- Chinjut 12y agoSure. 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.)
- schoen 12y agoIt'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 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!
- tunesmith 12y agoWasn't there some project about trying to find the independent bits of information among all the people in the world? So that if you answered a 33-question (2^33 is about 8.5 billion) true/false survey, your answers would be distinct from anyone else's. Well I guess you could do it with longitude, latitude, and timestamp of birth, but I think it was supposed to be a personality survey.
- plugss 12y agoPardon my ignorance, but could someone explain the parity aspect of this puzzle to a less enlightened mind?
- aethertap 12y agoIt'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.
- jmhobbs 12y agoWhy not just agree to the coin closest to the top-left corner?
- deleted 12y ago[deleted]
- tunesmith 12y agoFor those confused about the parity display number, the two things to keep in mind are: 1) The regions are the blue areas, not the white areas 2) Even though the parity chart displays 2^0, 2^1 etc left to right, the parity number itself is the other direction like normal binary. So, the bottom half region is the left-most number.
- nicknash 12y agoI think this blog post is also quite a nice write-up of this puzzle, and it includes generalizations: https://ocfnash.wordpress.com/2009/10/31/yet-another-prisoner-puzzle/ https://ocfnash.wordpress.com/2009/10/31/yet-another-prisone...
- deleted 12y ago[deleted]
- amelius 12y agoNice, but I find the following statement a bit misleading. > Is it possible to communicate six bits of information by the flip of a single coin? Considering the fact that you can choose among 2^6 coins.
- deleted 12y ago[deleted]