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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.