3
$\begingroup$

I am thinking of two different positive integers between 1 and 100 (both inclusive). At most how many questions do you need to ask to find my two numbers if I will answer your questions truthfully and honestly?

My answers can only be "Yes", "No", or "I don't know". (I am a fairly good mathematician and equipped with a calculator.)

How many questions would you need if I a have three numbers in mind rather than two?

$\endgroup$
3
  • $\begingroup$ The sentence I am a fairly good mathematician and equipped with a calculator looks pointless. For example, if I ask "is there an elliptic curve over $\Bbb Q$ which has Mordell-Weil rank larger than one of your numbers?" then how should I interpret your answer? I think what you want to say is that, for each question one can choose any subset of $\{1, \dots, 100\}^2$ and ask whether the pair of numbers lies inside the chosen subset. Then you are able to answer with "yes" or "no" because you are good enough to judge whether this is true. But then the answer "I don't know" doesn't make sense. $\endgroup$
    – WhatsUp
    Nov 13 '21 at 19:37
  • 1
    $\begingroup$ Assuming that "I don't know" is just a decorational option, the answer is obviously $\lceil \log_2\binom{100}2\rceil$ which I think doesn't make a very interesting puzzle. But I don't know what is the correct interpretation of the "fairly good mathematician" sentence and hence not sure whether there are creative usages of the "I don't know" option. $\endgroup$
    – WhatsUp
    Nov 13 '21 at 19:48
5
$\begingroup$

I think I got an idea of doing this, regardless of whether you are a "fairly good mathematician equipped with a calculator" or not. Thus I'm not sure whether it's the intended answer.

I take a piece of paper and start to write down all possible options on the paper. In this case, we have originally $\binom{100}2$ options.
I write the first $\frac 1 3$ options with a red pen. I write the second $\frac 1 3$ options with a blue pen. For the last $\frac 1 3$ options, I write each one with either red or blue pen. These are all done outside of your sight.
After writing down all options, I cover the last $\frac 1 3$ options with another piece of paper, so that they cannot be seen. I then show this piece of paper to you, tell you what I have done, and ask you this question:
"Is the correct answer written in red?"
According to whether the correct answer lies in the first, second or last $\frac 1 3$, your answer should be "Yes", "No" or "I don't know", respectively. This effectively reduces the number of possible options by a factor of $3$.
I then repeat the process until there is only one option left. The total number of questions needed is $\lceil \log_3 N\rceil$ if there are originally $N$ options.

This can be shown to be optimal, under certain restrictions on the type of questions that can be asked. Note that there must be some restrictions, otherwise questions such as "Will you answer this question with "no"?" are unanswerable.

$\endgroup$
5
  • $\begingroup$ so what is the exact number being asked for? $\endgroup$ Nov 13 '21 at 21:24
  • 1
    $\begingroup$ @FirstNameLastName $\left\lceil\log_3\!{100\choose2}\right\rceil=8$ $\endgroup$
    – Bass
    Nov 14 '21 at 2:21
  • $\begingroup$ agreed for 2 (and 3) that ceiling and log3 'commute' so to speak, but, for 5 it gives ceiling(log3(75287520))=17 whereas 16 questions suffice. $\endgroup$ Nov 14 '21 at 13:33
  • 1
    $\begingroup$ @FirstNameLastName $16$ questions can only make $3^{16} = 43046721$ different answers. How do you make $75287520$ different answers with only $16$ questions? $\endgroup$
    – WhatsUp
    Nov 14 '21 at 13:37
  • $\begingroup$ You are right, there was a silly bug in my script :-) $\endgroup$ Nov 14 '21 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.