Guess a number part 5. Alice Lies!

Here is a set of 15 non-adaptive questions that guarantee that Bob correctly identifies Alice's number.

• For questions 1 to 10, question $i$ asks whether the bit in the $2^{i-1}$ place is 1.
• Question 11: Is the number of ones in the binary representation odd?
• For questions 12 to 15, question $i$ is: If you lied to one of the first 11 questions, then is there a 1 in the $2^{12-i}$ place of the binary representation of the index of the question to which you lied.

The first ten questions would identify a number between 1 and 1000 if answered correctly.

Question 11 helps to identify whether the lie (if any) has already occurred.

Since Alice can lie at most once, if the answer to question 11 is consistent with the answers to questions 1 to 10, she has not lied yet. In this case her answers to the remaining questions can be ignored and the first ten questions identify the number.

If the answer to question 11 is not consistent with the previous answers, then she has lied to one of the questions (including 11) and therefore she must have answer questions 12 to 15 truthfully.

But questions 12 to 15 identify the index of the incorrectly answered question. (This a number between 1 and 11, which can be identified with 4 bits) So now, if the index is 11 the first ten answers are correct, and if the index is between 1 and 10, we simply negate the answer at that index. Now we have the first ten questions correctly answered and can identify the number.

This is an example of an error-correcting code , used in storing and transmitting binary data. A simple 15-bit Hamming code can transmit up to 11 bits of data and correct any 1-bit error.

This coding can also correct an error that occurs after transmission, so Alice doesn't need to know where the error is (where she intentionally lied). And since the code can transmit 11 bits and we need only 10, we have room for an extra question.

Here is an example. For all questions, consider the binary representation of Alice's number with the bits labeled bit1 through bit10 . Each bit is either 0 (even) or 1 (odd). Bits can be summed with each other, for example, (1 + 1 + 0 + 1 + 0) equals 3 (odd).

• Question 1: Is bit1 odd?

• Question 2: Is bit2 odd?

• Question 3: Is bit3 odd?

• Question 4: Is bit4 odd?

• Question 5: Is bit5 odd?

• Question 6: Is bit6 odd?

• Question 7: Is bit7 odd?

• Question 8: Is bit8 odd?

• Question 9: Is bit9 odd?

• Question 10: Is bit10 odd?

• Question 11: Do you think I'm a bit odd?

• Question 12: Is the sum ( bit1 + bit2 + bit4 + bit5 + bit7 + bit9 ) odd?

• Question 13: Is the sum ( bit1 + bit3 + bit4 + bit6 + bit7 + bit10 ) odd?

• Question 14: Is the sum ( bit2 + bit3 + bit4 + bit8 + bit9 + bit10 ) odd?

• Question 15: Is the sum ( bit5 + bit6 + bit7 + bit8 + bit9 + bit10 ) odd?

Please note that each bit is covered by one "data" question (1 through 10) at least two of the "parity" questions (12 through 15). Bob will use answers to the data questions ("data bits") to reconstruct the original binary representation of Alice's number and the answers to the parity questions ("parity bits") to check for errors (lies).

If all the parity bits match the reconstructed number, then there were no lies (except possibly question 11, which Bob can ignore), and the reconstructed number must be correct.

If there is exactly one mismatched parity bit, it can't be due to an error in any of the data bits because it would have caused at least two mismatches. So the error must be in the parity bit itself and the reconstructed number must be correct.

If there are two or more mismatches, Bob can uniquely identify the data bit which is covered by each combination of parity bits. For example, if the answers to questions 12 and 15 don't match the reconstructed number, then bit5 must be in error. Reversing this bit will yield the original number.

One can easily construct Hamming codes of any length using the table presented in the Wikipedia article.