Information theory riddle about finding a gift in one of 16 boxes

Question

There are $16$ boxes, one of which contains the gift. We have $7$ persons, who can help us by answering on any yes/no question, but one of the persons is a liar, he may not tell us the truth. We have one question with each of $7$ persons. Our goal is to say definitely which one of $16$ boxes contains the gift.

(The problem is from information theory and I guess it is connected to some error correction code.)

Answer 1

As you expected and Hagen von Eitzen also pointed out, you could use an error-correcting code that encodes $4$ bits of information (the position of the gift) with $7$ bits (the yes-no questions you ask from the $7$ people) and is capable of correcting a single error. The $(7,4)$-Hamming code is one such code.

So, we could do as follows:

1. The code consists of $16$ distinct $7$-bit code words that are at Hamming distance at least $3$ from one another. Assign these code words to the boxes in a one-to-one fashion.

2. Ask the $i$'th person the following: Is the $i$'th bit of the code word of the box containing the gift $1$ (yes) or $0$ (no)?

3. The result is a $7$-bit word that is either a code word or differs at a single bit from one and only one of the code words. The gift is in the box identified by that code word.

Answer 2

We need to obtain 4 bits of information and can query 7 bits, but with one possible error. This smells a lot like Hamming code.