Skip to content

Guesses needed to find a number up to 1000

Question

A friend secretly chooses an integer from 11 to 10001000. You make guesses, and after each wrong guess the friend tells you whether the secret number is above or below it. What is the smallest number nn of guesses that lets you be certain of identifying the number, whatever it is?

Short answer

10. Use binary search, guessing the middle of the remaining range each time. With kk guesses you can distinguish at most 2k−12^k-1 numbers, and 29−1=511<1000≤1023=210−12^9-1=511<1000\le 1023=2^{10}-1, so 1010 guesses suffice and 99 do not.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free