From: Fred Lunnon <fred.lunnon@gmail.com> I cannot understand how this idea is supposed to work. Suppose we have 16 coins, heads = 1, tails = 0, numbered 0..15, and the prisoners agree coins 0..6 to communicate the Hamming(7, 4) code as shown at http://en.wikipedia.org/wiki/Hamming%287,4%29 The warder selects coin 0 , then turns all coins heads.
How is prisoner A to convert this 1111111 to a message (correctable to) 0000000, using only a single turn? WFL
--no, prisoner A merely converts it to a message WITHIN THE 000..00 COSET of the hamming code, i.e. due to the fact that 0000=0000 in your example, here just within the hamming code itself. In your example, prisoner A actually can just do nothing, I think. My idea is that prisoner A's message to B is encoded in the answer to "which coset of the Hamming code is the (after modification by A) bitstring in?" I believe Goucher's solution of the problem is equivalent to mine, by the way, but taking advantage of the so-called "syndrome" coset-identifier elegant trick which only works for Hamming codes in a specific format, but does not work for general error correcting codes. My general idea will solve this whole class of problems provided you have a suitable error correcting code which can tile the full space of codewords via disjoint translates (aka cosets). (To solve my "*extended* mensan problem" is, however, more involved, or anyhow you in general would need to know more about the coset "graph structure." It might be that, for this extended problem, merely looking up codes in tables of good codes like a moron, is not going to be good enough.) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)