Best Answer witzar, 08 August 2013 - 05:54 PM

Spoiler for

Go to the full post
Let's work in binary.

Let n=abcd be a 4-digit number.

Let e be the parity of abc.

Let f be the parity of abd.

Let g be the parity of acd.

(Parity of sequence of bits is 1 if the sequence contains odd number of 1's, and 0 otherwise.)

Let's ask 7 questions (about a trough g), obtaining 7 digit vector abcdefg, in response.

Now we can check if e, f, and g in the response match the parity of appropriate bits in response.

Let n=abcd be a 4-digit number.

Let e be the parity of abc.

Let f be the parity of abd.

Let g be the parity of acd.

(Parity of sequence of bits is 1 if the sequence contains odd number of 1's, and 0 otherwise.)

Let's ask 7 questions (about a trough g), obtaining 7 digit vector abcdefg, in response.

Now we can check if e, f, and g in the response match the parity of appropriate bits in response.

If BMAD decides to lie about a, then we'll notice errors in e,f,g.

If BMAD decides to lie about b, then we'll notice errors in e,f.

If BMAD decides to lie about c, then we'll notice errors in e,g.

If BMAD decides to lie about d, then we'll notice errors in f,g.

If BMAD decides to lie about e, f or g, then we'll notice a single error in e or f or g respectively.

If BMAD decides not to lie at all, we'll notice no error.

Observe that no mater what he does, the set of noticed errors will be unique,

thus letting us know what did BMAD lie about (if at all)

and letting us restore true values of abcd(efg).