2
$\begingroup$

This is an interesting puzzle which I've been racking my brain to solve for some time. I've found different variations of this puzzle but it does not seem like this one has been asked before. Here it goes:

I'm thinking of three different numbers from 1, 2, ..., 15. You know that the largest number is greater than 10. What is the minimum number of yes/no questions you need to ask to guess those three numbers? I can only answer in yes or no.

$\endgroup$
0

2 Answers 2

8
$\begingroup$

If the largest number is $N$, then there are

$\frac{(N-1)\cdot (N-2)}{2}$

possibilities for the two smaller numbers. Summing the possibilities for the smallest two numbers when the largest is each of 11,12,13,14, and 15 gives a total of

$\frac{10\cdot9}{2}+\frac{11\cdot10}{2}+\frac{12\cdot11}{2}+\frac{13\cdot12}{2}+\frac{14\cdot13}{2}=335$

possible solutions for all three numbers. An efficient means of choosing a solution from a number of possibilities is to discard approximately half the possibilities with each yes/no question. This allows the questioner to distinguish between $2^k$ possibilities in $k$ questions. (Note that if there are exactly $2^k$ possibilities to start with you need a question that discards exactly half the possibilities).

For your set of possibilities, the question

"Is the largest number either 14 or 15?" (This reduces the set of 335 possibilities into a set of 166, if the answer is "No", or 169 if the answer is "Yes").

divides the possible answers into two almost equal sets. Whatever the answer, you can use the same strategy to get an answer within no more than

9

questions.

$\endgroup$
1
  • 7
    $\begingroup$ Just to get rid of that "should be able" there, the structure of the question is not constrained in any way, so you can just name half of the possibilities at each stage, and ask "is one of these the answer?" $\endgroup$
    – Bass
    Nov 13, 2021 at 9:04
3
$\begingroup$

The number of combinations of 3 different digits among 15 digits is 3 choose 15.
The number of combinations where all digits are smaller than 10 is 3 choose 10.
So number of combinations where at least 1 number is greater than 10 is:

$$\binom{3}{15} - \binom{3}{10} = 335$$

$$\lceil log_2(335) \rceil = 9$$

$\endgroup$
1
  • $\begingroup$ You may add a backslash to 'log' to make it appear an upright-font function name. $\endgroup$
    – CiaPan
    Nov 16, 2021 at 16:44

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.