Conference rusure::math

Observe that X can be represented as a 4-bit binary number x1x2x3x4.
Thus, we can reduce the problem to determining the values (0 or 1)
of x1, x2, x3, and x4.

Let '*' represent the exclusive or operator.

Define y1 = x2 * x3 * x4, y2 = x1 * x3 * x4, and y3 = x1 * x2 * x4.

For our seven questions, ask for the values of x1, x2, x3, x4, y1, y2,
and y3.  (Note that these can be phrased as yes/no questions such as
"Is your number 2, 3, 6, 7, 10, 11, 14, or 15?")  Call the answers
x1', x2', x3', x4', y1', y2', and y3'.

Now we can check whether each of the yk' "is ok", given the values
of the xi'.  We have three yk', and thus eight possible combinations
of correct/incorrect values, corresponding to no lie or a lie in any
one of the seven answers.  Define:

	"y1' ok" if y1' = x2' * x3' * x4'
	"y2' ok" if y2' = x1' * x3' * x4'
	"y3' ok" if y3' = x1' * x2' * x4'

Then the following table indicates which answer, if any, was a lie:

    y1' ok?    y2' ok?    y3' ok?    |    Wrong answer
    ---------------------------------+----------------
      Yes        Yes        Yes      |       None
      Yes        Yes        No       |       y3'
      Yes        No         Yes      |       y2'
      Yes        No         No       |       x1'
      No         Yes        Yes      |       y1'
      No         Yes        No       |       x2'
      No         No         Yes      |       x3'
      No         No         No       |       x4'

Knowing the correct values of x1, x2, x3, and x4, we can reconstruct
the original number.

The reasoning is fairly simple.  If yk' is ok, then all of the xi'
included in it (i =/= k) must be correct, since otherwise we would
have two lies -- one about one of the xi',and one about yk'.  Each
xi' is included in at least two yk's, and any two yk's between them
include all the xi's, so if just one yk' is not ok, then that yk'
must be the wrong answer.  If yk' is ok, but ym' and yn' are not,
then the wrong answer must be xk', which is included in ym' and
yn', but not in yk'.  Finally, if none of the yk's are ok, then
the wrong answer must be x4', which is included in all of them.

A restatement of the problem:  Construct a single-bit-error correcting code
to transmit 4 bits of information with 3 bits of overhead.

The solution given in .1 grows out of this way of viewing the problem
pretty directly.
							-- Jerry

Look in any elementary coding theory book under Hamming Code.  The check
bits can be chosen is such a way that their value will be the binary
representation of the number of the error bit (or zero if no error.)

Mike.

Good work guys!  These solutions are along the same lines that
Richard Lary used.  I enclose his solution in the next response.

From:	MARIAH::LARY 18-AUG-1983 12:02
To:	TURTLE::STAN
Subj:	RE: MATH PROBLEM


Ahh, Mr. Rabinowitz, it is easier than you think - the answer is to form
a (7,4) single-error-correcting code [on binary symbols] and the 4 information
bits give the answer.

If you don't know how to form a (2**n-1,n) Hamming code, there is a particularly
elegant way to think about it - number the bits in the code word from 1 to 7,
the error-correcting bits are bits 1, 2, and 4  [2**i] and equal the XOR of
those data bits which contain that power of 2 in the representation of their
index [the data bits are, of course, 3,5,6 and 7]. To "correct" a code word,
compare the recalculated XOR's with the error-correcting bits and the
3-bit number formed by the discrepancies is the index of the bit in error
[0 discrepancy means, of course, no errors]

Since the questions here are all "set membership" questions, the XOR of the
answers can be obtained from John by asking the question with the XOR'ed sets.

							Richie

A related problem was proposed by Stan Rabinowitz.

I choose an integer from 0 through 15. You ask me 7 yes or no questions.
I answer them all, but I am allowed to lie (I needn't, but I am allowed to.)
Once I start lying, I continue to lie.  Determine my number.


It may be possible to map this problem into the Hamming-code problem/solution.

The variation on the "guess the integer" problem where the respondant lies
continuously following the initial lie can be mapped onto the original problem
as follows:

Suppose the responses are represented by the binary sequence An; define the
binary sequence Bn as B1=A1, Bn=An.XOR.A(n-1) for n>1. If the sequence An is
subjected to an "error transformation" such that all An are inverted for n>E,
then the corresponding transformation on Bn is to simply invert B(E). Since the
mapping from An to Bn is invertible, you can ask questions that form a single-
error-correcting code in Bn and derive An from it. Thus the same number of
questions that solved the original problem will solve this variant.