If I think of a number between 1 and 1,000, guessing it in 10 yes-no questions is easy... so that's not the puzzle!

Guessing it in 10 yes-no questions, that must be all asked in advance, is also relatively easy... so that's not the puzzle either!

How many questions would you need to guess my number, if you had to ask all questions beforehand, and I also could lie once?

As Charlie points out translate into binary seems the better system. We obtain a 10-digits number in which (probably) there is one digit wrong. So, to guess the wrong digit, we can ask him to form the 4-binary number in correspondence with the column of the 10-digits number where he has lie. This means another four questions; 14 in total.

But, before these four questions, we have to instruct him to introduce the following corrections:

If he lies on column 1 (beginning on the right) we beg him to compose number 15; if he lies on column 2, compose 14; column 4, 13 and column 8, 12. Only now we should begin to ask him about these last four digits. Why?

Because if he didn't lie on the 10-digits binary number he would had to compose column 0 (0,0,0,0). But he could lie now. In this case, as he could lie only once, he would compose (1,0,0,0) or (0,1,0,0) or (0,0,1,0) or (0,0,0,1). With precedent instructions we have free these numbers; otherwise we wouldn't be able to know if these 4-digits numbers means the column of the 10-digits number where he lies before, or if they are only the result of the fact that he didn't lie before and is lying now.

Now we know that if his answer points the number (1,0,0,0 or one of the other three), he is lying now and that he has tell the true 10 digits number before. If instead we obtain the 4-binary of 12, 13, 14, or 15 digital, we get the number of the column of the 10-digits binary where he lies before, and we can rectify the 10-digits number.

So 14 questions are sufficient.

 

Edited on April 14, 2005, 11:13 pm

Posted by armando on 2005-04-14 22:22:21