3
$\begingroup$

My student Tatiana thinks of two positive integers, not necessarily different, none greater than 1000. I wish to determine her numbers, and for this she allows me any number of questions to which she will answer truthfully "yes" or "no".

  1. At most how many questions do I need to be certain of determining both numbers?

  2. What if she is also allowed to honestly respond to my questions "I don't know"?

$\endgroup$

2 Answers 2

2
$\begingroup$

There are $1000^2$ choices for the initial numbers, and $\lceil\log_2(1000^2)\rceil=20$, so you'll need 20 guesses in the first case, simply by eliminating about half the guesses each time. Specifically, encode the first number $m$ and the second number $n$ into the binary number $1000m+n$ which is distinct for each $(m,n)$ and we'll pad the number to $20$ digits. Therefore, the $i$th question will be "Is the $i$th digit 1?" which will determine the binary number.

Similarly, $\lceil\log_3(1000^2)\rceil=13$, so you'll need 13 guesses by encoding $1000m+n$ into trinary, and ask "If the $i$th digit is $2$, respond 'yes', else if the $i$th digit is $0$, respond 'no', otherwise respond 'I don't know'". Note that if this kind of prompt is not allowed then the second scenario is effectively the same as the first scenario.

$\endgroup$
1
  • $\begingroup$ I think your trinary question can be rephrased as an actual yes/no question (rather than an imperative) like this: rot13(Vf gur $v$gu qvtvg 2 be ner obgu bs gur sbyybjvat gehr: gung gur $v$gu qvtvg vf 1 naq gung V unir 25 pragf va zl cbpxrg?) $\endgroup$
    – tehtmi
    Jan 22 at 22:06
0
$\begingroup$

There are $500,500$ pairs of numbers that Tatiana could choose. Given that this is a little less than $2^{19} = 524,288$, one would assume that $19$ questions are both sufficient and necessary.

Is this true?

Yes. Simply order the possible pairs in such a way that Tatiana can compute the position of her chosen pair, then do a binary search for that position.

The bonus question gives the possible answer "I don't know".

For such an answer to assist us, it would have to yield us information. For that to happen, we should be able to deliberately insert ambiguity of some kind into our questions, such that whether a question makes sense depends on Tatiana's choice of numbers.

One possible way to do this is in a statement like the following:
"I am using 'or' to mean either the inclusive 'or' or, exclusively, the exclusive 'or'; is [condition A] or [condition B]?" (If the structure of this statement is confusing, there are workarounds, such as specifying a choice of 'or' ahead of time and writing it down in secret.)
If neither A nor B is true, then A OR B and A XOR B are both false, and Tatiana can honestly answer 'No'. Likewise, if exactly one of A and B is true, then both A OR B and A XOR B are true, and Tatiana can honestly answer 'Yes'. However, if both A and B are true, then the answer to the question depends on its intended interpretation, which you know and she doesn't.

Choosing A and B appropriately allows you to do a ternary search for the position of Tatiana's chosen pair, which should take no more than $12$ questions since $3^{12} = 531,441$.

$\endgroup$
3
  • $\begingroup$ The pair count of 500500 (= 1001 choose 2) seems off for two reasons: firstly, zero is (for most intents and purposes) neither positive nor negative, so there are only 1000 choices for each number. Secondly, there are exactly 1000 choices for both numbers, because the numbers are not necessarily different. $\endgroup$
    – Bass
    Jan 20 at 11:42
  • $\begingroup$ If the order of the numbers is unimportant, then there are 1000 ways to choose the same number twice, plus C(1000,2) = 499500 ways to choose two different numbers, so 500500 total. If the order is important, then yes, there are 1000000 ways. $\endgroup$
    – Ed Murphy
    Jan 20 at 12:05
  • $\begingroup$ True, I was thinking of the numbers having an identity. $\endgroup$
    – Bass
    Jan 20 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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