Minimum number of questions?

Question

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.

Answer 1

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.

Answer 2

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$$