2
$\begingroup$

In an episode of Odd Squad, the squad are left with five yes/no questions to get a three digit code out of a villain. Luckily for them, they have sufficient questions to guess the first number by splitting a number line and then the villain's predictable pattern (of always counting backwards) allows them to solve the code with their final question, the answer being 321.

Earlier in the episode they use a similar method, again splitting a number-line in half and asking if it's above or below the middle number (e.g. if the number is 6 on a line between 0-10, asking if the number is above 5(yes), then below 7(no), before finally guessing 6(yes).

Assuming the combination was a random number between 000 and 999, what is the minimum number of yes/no questions that would be need to be available in order to confidently solve any possible combination either using the technique above or one of your own devising.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Is there more to this than binary search? If not, I feel like this will have been asked here before. $\endgroup$
    – hexomino
    Commented Mar 12, 2022 at 18:22
  • 2
    $\begingroup$ For example, the accepted answer to this question gives a general strategy. $\endgroup$
    – hexomino
    Commented Mar 12, 2022 at 18:24
  • 2
    $\begingroup$ @Richard Binary search is optimal for binary (yes/no) questions. $\endgroup$
    – noedne
    Commented Mar 12, 2022 at 18:27
  • 2
    $\begingroup$ Think of it this way, for any set of possible answers "yes" will eliminate a certain proportion and "no" will eliminate the rest. That means one of either "yes" or "no" will eliminate, at most, half of the answers and you have to account for the worst case scenario. $\endgroup$
    – hexomino
    Commented Mar 12, 2022 at 18:33
  • 2
    $\begingroup$ @Richard You can ask any kind of questions you like to perform binary search, and it will be optimal as long as you can evenly divide the number of yes/no answers. The example of asking "higher or lower/equal" is just an easy way to do this for a range of numbers. $\endgroup$
    – noedne
    Commented Mar 12, 2022 at 18:38

2 Answers 2

Reset to default
2
$\begingroup$

Since we are looking for a guaranteed strategy, we must always consider the worst case scenario. For us, it is that the answer to our yes/no question will eliminate the fewest options possible. So to optimise our strategy, we should always choose a question where the worst case is the best for us. If we always ask "is the answer bigger than the median", the worst case will be just as good as the best case (or in the case with an odd number of options, as close as possible), so that strategy must be optimal.

This strategy will take $\left\lceil{\frac{\log N}{\log 2}}\right\rceil$ questions, also known as "the length of the binary number representing the number of different possibilities". This comes as no surprise, because we could also have asked "is the Xth bit in the binary representation of the answer 1 or 0" for all X starting from 1 and continuing until we have covered all possibilities.

As for the case where the options range from 0 to 999, we know that $2^9=512$ and $2^{10}=1024$, so we are going to need

10 questions.

The name for this approach (in either of the forms described) is binary search.

Improve this answer
$\endgroup$
1
$\begingroup$

Another path to the same solution: Suppose there is a strategy that always wins in 9 questions. In this strategy, if the answers are YYYYYYYYY, the solver guesses (one number). If the answers are YYYYYYYYN, solver guesses (a second number). ...

For every number from 000 to 999, there has to be some sequence of Y/N that leads to the guesser choosing that number. But there are 1000 numbers they might have to guess, and only 512 sequences of 9 Y/N. So there's no such strategy.

(Also, there are 120 different three digit numbers with decreasing digits, and only 32 sequences of 5 Y/N, so they got lucky.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is a great approach. For anyone interested in further reading, it's called the pigeonhole principle. $\endgroup$
    – Bass
    Commented Mar 14, 2022 at 14:32

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.