5
$\begingroup$

$x, y, z$ are $3$ random integers from $1$ to $10$ inclusive. Now, you have to guess these numbers, and you are allowed to ask questions. Each question is of the form, 'Is $a\le x\le b, c\le y\le d,$ and $e\le z\le f$?', where $a, b, c, d, e, f$ are arbitrary integers from 1 to 10 inclusive. The answer to each question is either YES if ALL three conditions are fulfilled, or NO otherwise. Assume the answers are always truthful. Find the smallest number of questions needed to guarantee the knowledge of $(x, y, z)$.

So far, I have a solution that uses only $12$ questions:

Set A

  1. Is $1\le x \le 9, 1\le y \le 9, 1\le z \le 9$? If yes, go to set B, otherwise, continue
  2. Is $10\le x \le 10, 1\le y \le 10, 1\le z \le 10$? (This is equivalent to asking if $x=10$.)
  1. Is $y=10$? (Use the same form as above.)
  2. Is $z=10$? Move on to Set B.

Set B

  1. If $x\le 9$, is $1\le x \le 3?$ If yes, move on to set C.
  2. $4\le x \le 6?$ (If no, $7\le x \le 9$.) Move on to set C. Replace $1, 2, 3$ with $4, 5, 6$ or $7, 8, 9$ respectively.

Set C

  1. If $1\le x \le 3$, is $x=1?$
  2. $x=2$? (If no, $x=3$.)

Repeat sets B and C for all variables that are below $9$. It is easy to verify that the worst case scenario, at $(9,10,9)$, takes only $12$ questions.

However, I cannot continue on from this point. Please advise.

$\endgroup$
4
  • $\begingroup$ Standard "entropy" argument gives us that we need at least 10 questions (with 9 questions we have 512 possibilities of information we get, but 1000 different results, and that's not possible); and this bound would be attainable only if we would always "cut" set of possible answers to almost equal parts. We can get 12 questions doing just bin-search on each coordinate, so I personally think that 11 will be the answer. $\endgroup$
    – radekzak
    Feb 4, 2021 at 15:46
  • $\begingroup$ You can easily find each number in at most 4 guesses, working in them one at a time with questions of the form "is $1≤x≤5, 1≤y≤10, 1≤z≤10$?". The only issue is whether this can be reduced to 11, or (conceivably but unlikely) 10. $\endgroup$
    – MJD
    Feb 4, 2021 at 15:49
  • $\begingroup$ It is probably pretty easy to have the computer generate a strategy for 11 guesses with brute force. Using brute force to prove there is no 10 guess strategy seems less likely to work. $\endgroup$
    – MJD
    Feb 4, 2021 at 15:51
  • 3
    $\begingroup$ $10$ tests is possible, by first using three tests to reduce the problem to a 5 x 5 x 5 problem, and then using the strategy here. You will have to translate the language in that problem to this one. $\endgroup$ Feb 4, 2021 at 16:57

0

You must log in to answer this question.

Browse other questions tagged .