Or, you could just flip the coin that's rotated 180 degrees from the freedom coin. Tom Warren D Smith writes:
If there is a binary error correcting code on N=2^J bits such that (1) exactly N cosets of it constitute the whole set of 2^N possible bitstrings (2) any N-bit word is distance <=1 away from a codeword then you can solve the problem by changing a bit to move it into coset X, thus communicating the value of X to the other prisoner.
The questioners asked about J=4 and J=6 and a single-error-correcting Hamming code should do the job. Actually I do better. If N= 2^J - 1 (for example N=127, J=7), then Hamming codes have cardinality=2^(N-J-1) hence we can by my method provide J+1 bits of information to the other prisoner by flipping only at most one coin. But only J bits of info [in fact only log2(2^J - 1) bits] actually are needed.
Is there an actual use for this (not just in a silly puzzle)?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun