[math-fun] Mensa Correctional Facility, reply to Fred Lunnon
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)
It's unclear to me what exactly "coset" means in this context; but I now understand your idea to be communicating the `freedom' coin index k via an n-bit syndrome of a codeword extending over 2^n coins --- while attaching an extra `data bit 0' to the standard Hamming code? If the warder initially supplies a codeword (syndrome = 0) and the coins are numbered 0..63 say, then prisoner A flips coin k ; fine, unless k = 0 , when he must violate the constraint by not flipping. If the initial syndrome is j <> 0 , presumably flipping individual coins in turn causes the final syndrome to run similarly through all possible other values, including the desired k <> j --- though I can't see a neat algorithm taking j -> k . The j = k problem might be overcome by using Hamming with n+1 check bits; but now when j <> 0 the syndromes generated are (presumably) no longer restricted to range 1 <= k <= 2^n , clobbering prisoner B. Note that Adam Goucher's solution always gives prisoner A some coin to flip, whatever the initial configuration. Beautiful problem! WFL On 4/16/15, Warren D Smith <warren.wds@gmail.com> wrote:
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)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Fred Lunnon -
Warren D Smith