How Many Questions You Need to Find a Number? I secretly chose an integer number from 1 to 1000. You are allowed to ask me any questions that have an integer number from 1 to 1000 as an answer. For example, "2*2=?" and "What number did you choose?" are both valid questions, but "Is your number greater than 500?" and "1000+1=?" are not. However, I cannot guarantee you that I will be truthful answering your question all the time. I only quarantee you that: 1). my answer will be an integer number from 1 to 1000; 2). I will alternate true and false answers. How many questions you need to ask me to find out my number? Dmitri Papichev Monday, June 20, 2005 3 1. What number did you choose? 2. What number did you choose? 3. 2+2=? With answer to your 3rd question I'd know if you were telling the truth the first time or the second time. Mithun Tuesday, June 21, 2005 Or if you switch those questions around, half the time you'll get it a question earlier: 1) 2 + 2 = ? 2) What is your number? 3) What is your number? BradC Tuesday, June 21, 2005 Can you do better than 3 questions? :) Dmitri Papichev Tuesday, June 21, 2005 Also, my goal is to hide the truth as long as possible :) - i.e. maximize the number of questions you need to ask. I can make a decision on whether to lie answering the first question after I hear the question. Dmitri Papichev Tuesday, June 21, 2005 1: 2+2=? 2a if you say four: what is a number you did not pick? 2b if you say something not four: what is your number?  WanFactory Tuesday, June 21, 2005 Good. Two is better than three. Can you do even better though? :) Dmitri Papichev Tuesday, June 21, 2005 Labyrinth style (one door always lies, one door always tells the truth), use the 1 * -1 = -1 kind of logic. "What number would you refuse to answer if I asked you with my next question what number you had picked?" Say the actual number is 37. Scenario 1 ======= If the current mode is true, they have to tell the truth that they would refuse to answer 37 with the next question (since they would then be in false mode). Scenario 2 ======= If the current mode is false, then the "if I asked you with my next question what number you had picked" part (basically getting them to answer the second question without having to explicitly ask it) would be 37.  So substituting this in to make it easier to understand, we're left with a false-mode question of "What number would you refuse to answer if I asked you _with my next question_ (IOW in truth mode) 'what number is 37?'".  To try and clarify, if this question were to get answered in truth mode, the answers would be anything not 37.  16, 521, whatever - all of those would be truthful answers to the question "What number would you refuse to answer ... 'what number is 37?'".  However, since we're in false mode, the only possible answer is the selected number, 37. I could probably have given a more clear explanation - blame my 3-month-old daughter for causing her daddy's lack of sleep :) James Manning Tuesday, June 21, 2005 Good. One question is hard to improve :) Now let's make the task more difficult. If I choose at my will - to lie or not answering your question - how many questions would you need? Dmitri Papichev Wednesday, June 22, 2005 It will take for ever if you chose not to answer any of the questions. Abyss Thursday, June 23, 2005 I said: "_to lie or not_ answering the question" I would always give some logically (if not factually) correct answer :) Dmitri Papichev Thursday, June 23, 2005 I am not able to understand the statement to lie or not answering the questions. perhaps i am missing something it would help if someone can enunciate on that to me. Abyss Thursday, June 23, 2005 laugh, I misunderstood this to: I thought it meant you could 1. lie OR 2. not answer the question I think it means: when I ask a question, the answer person can choose to lie or tell the truth but must still answer the question WanFactory Thursday, June 23, 2005 Sorry, guys. I think the way I write is influenced by the fact that English is not my first (or even second, for that matter) language. I try to speak English right but there is a limit of what a person with average language abilities can do :) I understand I should have said "I choose if to lie or not to lie answering the question" - would that be correct and clear? Dmitri Papichev Thursday, June 23, 2005 What would you refuse to tell me if: I asked you what number you picked and the truth-value of your response was opposite to the truth-value of your response to this question? WanFactory Friday, June 24, 2005 a great deal of Game Development Technical Materials http://www.freewebs.com/gamedev_res/ game res Friday, June 24, 2005 What number could you say if I asked you what number you picked? Suppose the answer was 42. If you decide to lie, then "if I asked what number you picked", you could say anything but 42 because you decided to lie. But since you have decided to lie, you must answer a number you could not say, and the only number you cannot say is 42. If you decide to tell the truth, you could only say 42. I think in general, you can get around liars and truth tellers with: What would you say if I asked you... WanFactory Friday, June 24, 2005 Yes, that's exactly right. Solved! :) Dmitri Papichev Friday, June 24, 2005   Fog Creek Home