Coins on chess-board puzzle
in [Theory]
|
From: Tim Little on 22 Nov 2009 16:18 On 2009-11-22, dgates <dgates(a)somedomain.com> wrote: > I'm trying to work out how you would even do it if there were only 3 > squares, rather than 64 squares. As I see it, with 3 squares, there > are 8 possible numbers you can make There are only 3 possible numbers you can make, since you must change exactly one of the bits from the warden's number. Unfortunately you can't do it in that case - with 3 outputs to code from 8 possible bitstrings, one of the outputs must have at most 2 encodings. Without loss of generality, suppose one of them is 000. If the warden gives you 000 to start with, you *must* flip a bit to get to the other one - so they can only differ in one bit position. However, what if the warden gave you 111? You can't get to either of them by flipping one bit. You can do it if you are allowed to leave the board unaltered, and you can encode four outputs in that case. - Tim
From: Tim Little on 22 Nov 2009 16:27 On 2009-11-22, dgates <dgates(a)somedomain.com> wrote: > Hmm, if there's a solution that works for 50 prisoners and 25 photos, > then I suspect that some variation of it works for 4 prisoners and 2 > photos, so I'll put my mind to that first. [...] > they now have a 2-in-24 chance. What if I said they can improve it to 10-in-24? - Tim
From: dgates on 22 Nov 2009 19:35 On 22 Nov 2009 21:18:55 GMT, Tim Little <tim(a)little-possums.net> wrote: >On 2009-11-22, dgates <dgates(a)somedomain.com> wrote: >> I'm trying to work out how you would even do it if there were only 3 >> squares, rather than 64 squares. As I see it, with 3 squares, there >> are 8 possible numbers you can make > >There are only 3 possible numbers you can make, since you must change >exactly one of the bits from the warden's number. Oh, actually by "8 possible numbers you can make," I meant "8 possible numbers that can be made with 3-digit binary number." I figured some codes would have to be served by more than one number, hence my "modulo 4" thinking. I was figuring that the encoding would end up *something* like this: Magic Set binary Square Code Equals equal to 0 NA 1 1 or 5 2 2 or 6 3 3 or 7 >Unfortunately you can't do it in that case - with 3 outputs to code >from 8 possible bitstrings, one of the outputs must have at most 2 >encodings. Without loss of generality, suppose one of them is 000. >If the warden gives you 000 to start with, you *must* flip a bit to >get to the other one - so they can only differ in one bit position... Sure, so for magic square "1," you'd flip to 001, for "2," you'd flip to "010," and for magic square "3," then my system falls apart (but I figured I just needed to re-jigger the numbers. >However, what if the warden gave you 111? In my system then... for magic square "1," you'd flip to 101, for "2," you'd flip to "110," and for magic square "3," you'd flip to 011. >You can do it if you are allowed to leave the board unaltered, and you >can encode four outputs in that case. I definitely noticed that my system would work better if you're allowed to leave the board unaltered. And, even under those conditions, I also need to re-jigger the numbers. For example, from a starting point of 110, I can indicate magic square 2 or 3, but have no way to indicate magic square 1. This is probably the shell of an alternate puzzle -- maybe a variation on this one where the number of squares isn't a power of 2 and the players are allowed to leave a coin unflipped as a valid move.
From: dgates on 22 Nov 2009 19:41 On Sun, 22 Nov 2009 13:09:49 -0500, Ted Schuerzinger <fedya(a)hughes.spam> wrote: >On Sun, 22 Nov 2009 09:16:51 -0800, dgates wrote: > >> Let's say you were the first prisoner, and I were the second (and, >> while I know that 2^6 is 64, I don't know what "EXOR" means). What >> would you tell me to look for in order to decode your message to me? > >Assume that the squares are numbered in binary from 000000 to 111111. >Then for each of the six places (the units place to the 32s place) look >at the 32 squares that have 1s in that place. If an odd number of those >squares have 1s in their binary representation, then the parity of that >number is 1; if an even number of those squares have 1s, the parity is >0. When the jailer gives you the secret square, turn over the >appropriate coin to change all six parities to the binary representation >of the secret square. Ahh, I see. Yes, each square on the board can be part of several different of the 6 numbers. That kind of reminds me of a kids' magic trick where someone picks a number, you show him special cards, asking him which cards it's on, then you quickly calculate his number. The cards look like this: http://illuminations.nctm.org/lessons/6-8/binary/fig7.gif To calcluate the number quickly, you just add the top left number on all the cards the guy said yes to. It would be handy to have a little chart something like that (showing which positions represent the 8 and the 16 and so on) printed on a cheat sheet before the prisoners have to do their math in the little room. :-)
From: dgates on 22 Nov 2009 19:43
On 22 Nov 2009 21:27:13 GMT, Tim Little <tim(a)little-possums.net> wrote: >On 2009-11-22, dgates <dgates(a)somedomain.com> wrote: >> Hmm, if there's a solution that works for 50 prisoners and 25 photos, >> then I suspect that some variation of it works for 4 prisoners and 2 >> photos, so I'll put my mind to that first. >[...] >> they now have a 2-in-24 chance. > >What if I said they can improve it to 10-in-24? Yep, I read it, and it was amazing. I think I read a version of that puzzle on this newsgroup, but as a puzzle about 10 guys outside a theater trying to sort out their movie tickets or something, and it was amazing then as well. |