| 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.
|
| 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
|