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".
At most how many questions do I need to be certain of determining both numbers?
What if she is also allowed to honestly respond to my questions "I don't know"?
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.
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$.
