0

If I write down a double digit number (10-99) and you have to guess the number by asking me the least number of questions regarding it, how will you do it?

For example: You could start by asking is the number 10? 11? 12? and so on, if I wrote down 99 then you would need 90 tries to do it, by following this method.

But if you asked me 'Is the number odd'? then you could follow up with similar questions as the above above method in relatively less number of tries, since you would only ask me if the number is 11? 13? 15? and so on.

What is the best series of questions you would ask?

NOTE: There can be more than 1 correct answers to this one.

Regards.

Rosie F
  • 8,621
  • 2
  • 18
  • 50
bjoshi
  • 17
  • 2
  • 2
    Are your answers going to be yes or no? If not i could just ask you what the number is which would mean i could get answer in one question – Maxqueue Jun 13 '16 at 16:12
  • 1
    Are these numbers integers? Because if you choose $e+\pi+\sqrt{2}+\phi+2$, I think this is going to be a lot more difficult than if you choose $11$. – Milo Brandt Jun 13 '16 at 16:20

4 Answers4

5

There are $90$ possible numbers, so, if the questions are yes-no, a set of $7$ well-chosen questions is enough, as $90<2^7$. For example, I could begin with "Is the number less than 55?" and the answer narrows the number down to a $45$-number range $10\dots54$ or $55\dots99$ as appropriate. Similar binary chopping will home in on the number.

Rosie F
  • 8,621
  • 2
  • 18
  • 50
3

Since there's no restriction on whether I have to ask closed-ended questions or not, I can guess your number in just one question:

What is your number?

And even if the questions had to be closed-ended, I could still cut it down to one by asking a single 90-choice question:

Is your number 10, 11, 12, ..., or 99?

If we further restrict the closed-ended questions to "yes-or-no" type questions, I can use multiple modes of unanswerability to give five choices for each question, in which case I still only need to ask three questions to get the number from you, rather than the seven that would be traditionally required for dichotomous questions that split the search space in half each time:

  1. I have a number in mind: it’s either 14 or 15, but I’m not saying which. If you multiply together (your number modulo 5 plus 1) and its smallest prime factor, then roll an ordinary 6-sided die and add the result, will the total be at least as big as than the number I’m thinking of?

  2. I have a number in mind: it’s either 14 or 15, but I’m not saying which. If you multiply together (the floor of your number divided by 5, modulo 5 plus 1) and its smallest prime factor, then roll an ordinary 6-sided die and add the result, will the total be at least as big as than the number I’m thinking of?

  3. I have a number in mind: it’s either 14 or 15, but I’m not saying which. If you multiply together (the floor of your number divided by 25, modulo 5 plus 1) and its smallest prime factor, then roll an ordinary 6-sided die and add the result, will the total be at least as big as than the number I’m thinking of?

Given that each of the above questions tells for a number between 1 to 5, I subtract 1 from them and plug them back into a three-digit base-5 number to get my answer.

Community
  • 1
  • Why not add 88 other modes of unanswerability and get the result in a single answer? – Trenin Jun 13 '16 at 17:14
  • @Trenin Can you come up with 88 modes of unanswerability? –  Jun 13 '16 at 17:16
  • Just an example. 1. I will know the answer tomorrow. 2. I will know the answer the day after tomorrow. 3. I will know the answer in 3 days. etc. In your question, you can then promise to reveal information at certain times. – Trenin Jun 13 '16 at 17:18
  • If you can write the necessary questions to employ those modes, then post it as your own answer for all the effort involved. –  Jun 13 '16 at 17:20
  • It pretty much writes itself, but it is no better than the "What is your number?" question which also has 90 modes. – Trenin Jun 13 '16 at 18:26
  • E.g. Statement 1: Please answer in the form "I will know in $X$ days." Statement 2: "If your number is $Y$, I will tell you my favourite colour in $Y$ days." Question: "What is my favourite colour?" – Trenin Jun 13 '16 at 18:28
  • This interesting digression compelled me to notice and upvote Differentiate between the numbers from 1 to 5 with one single yes/no question. Also suggested a kind of yes/no question where the time taken to answer indicates the magnitude of the secret number, such as "are there an odd number of primes less than your number?" – humn Jun 13 '16 at 19:44
  • "If we further restrict the closed-ended questions to 'yes-or-no' type questions" we won't get answers to our multi-modal questions, or we might simply get the response "I don't know" for all modes regardless of their actual values, leading us to a (most likely) incorrect answer. – Jonathan Allan Jun 13 '16 at 22:12
2

Assuming ONLY yes no questions only binary search would be fastest result. So first question would be if number was less than 55. Then whether yes or no divide the new range in half and ask same question. For example if number was less than 55 you could ask if number was less than 32 and so on...

Maxqueue
  • 992
  • 4
  • 8
0

Assuming that the dichotomic way to search for an exact element from a set, I propose any set of questions that devide, at each time, the resulting set at the half.

So multiple answers are possible. The one given by Rosie F and Maxqueue is an example of a dichotomic way, but there still much different other examples.

Sorry for my bad english.

imAProgrammer
  • 104
  • 4