Guessing a Mystery Number

Date: 05/23/2007 at 10:54:51
From: Akash
Subject: Searching for a number - one lie allowed

Hello,

Recently I came across this problem in which a guesser tries to 
find a number a hider has thought of.  It is known that the number 
lies amongst the first n natural numbers i.e., if the number is 
k, then k <= n.

The problem is the hider will lie once.  How do I find an algorithm 
which finds the hidden number? 

I was also wondering about the minimum number of steps required to
know the number.  With no lie I understand it is log2(n).
 

Date: 05/24/2007 at 09:53:51
From: Doctor Vogler
Subject: Re: Searching for a number - one lie allowed

Hi Akash,

Thanks for writing to Dr. Math.  I think that this is easier to 
analyze going in the other direction.  Given m questions, how much 
information can you get?

By your formula, I assume that all questions must be yes-or-no 
questions, like "Is the hidden number one of the following 
numbers: ...?"  Well, since there are 2 ways to answer each question, 
there are 2^m ways to answer m questions.  If the hider always tells 
the truth, then you can distinguish between 2^m possibilities by 
asking m questions.  Therefore, if there are n possibilities, then 
you ask m questions for the smallest m with

  2^m >= n.

Of course, then you have to construct the questions, but one easy way 
to do this is to ask whether the i'th bit in the binary representation 
of the hidden number is 1, for 0 <= i < m.

If the hider is allowed (respectively, required) to lie, then the 
problem is that each possibility (possible k, that is) can manifest 
itself in the answers of your questions in m+1 (respectively, m) 
different ways, since the hider might lie about any one question.  You 
don't want any of these to overlap, or you won't always be able to 
distinguish the correct answer.  That means that you can distinguish,
at most, (2^m)/(m+1) (respectively, (2^m)/m) different possibilities 
with m questions, when the hider can (resp. must) lie once.  
Therefore, if there are n possibilities, then you ask m questions for
the smallest m with

  (2^m)/(m+1) >= n.

Then you still have to construct the questions, and that will take
some thought, but this tells you exactly how many questions you need.

If you have any questions about this or need more help, please write 
back and show me what you have been able to do, and I will try to 
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/29/2007 at 06:41:12
From: Akash
Subject: Searching for a number - one lie allowed

Thank you sir.

It was interesting to notice the question you framed, which was:

ask whether the i'th bit in the binary representation of the hidden
number is 1, for 0 <= i < m.

I tried to figure out the type of questions I would ask from there but
got stuck again.  So, I need more help....

Thanks for the same in advance.

Date: 05/29/2007 at 18:37:54
From: Doctor Vogler
Subject: Re: Searching for a number - one lie allowed

Hi Akash,

This is sort of a cop-out way of answering your question, but it seems 
to me to be a valid answer anyway.  After each question, you could 
list off the numbers that are still possible and divide it into 
groups, and ask which group the number belongs to.

More precisely, you will have some (say X) numbers that fit the 
answers to all previous questions, and some (say Y) numbers that fit 
the answers to all previous questions except one.  If you have n 
questions left to ask, then there are X*(n+1) + Y possibilities 
remaining (here, I'm thinking of a possibility as the hidden number 
together with which question was lied about), which you need to divide 
in half; you want half of the possibilities to fit a "Yes" answer, and 
half to fit a "No" answer.  So you carefully make a list of some of 
these numbers and ask if it is one of the numbers in your list.  If 
the answer is no, then that rules out all of the Y numbers that made 
it onto your list and also moves the X numbers that made it onto your 
list into the Y table.  So if you put a of the X numbers and b of the 
Y numbers on the list, then a "No" answer will rule out

  a*(n-1) + b

possibilities, and leave you with

  (X-a)*n + (Y-b+a)

possibilities.  Since you want these as close as possible to equal, 
you want

  a*(n-1) + b = (X-a)*n + (Y-b+a)

or

  a*(n-1) + b = (X*n + Y)/2

(which are equivalent equations).  So I would take

  a = (X*n + Y)/(2(n-1)), rounded down to the nearest integer,

and then let b be the difference

  b = (X*n + Y)/2 - a*(n-1).

Then repeat for the next question.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/31/2007 at 02:13:36
From: Akash
Subject: Thank you (Searching for a number - one lie allowed)

Thank you very much doctor for your help.  It was nice going through
that "copping-out" way.  Have a great day.

Yours truly,

-Akash