Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm no good at probability and statistics as this question will soon demonstrate. My question is this, I have an instructor who proved that he could guess a number between 1-100 using the divide and conquer approach. For example, I choose 7.

He: 50

Me: High

He: 25

Me: High

He: 12

Me: High

He: 6

Me: Low

He: 9

Me High

He: 8

Me High

He: 7

See, its not possible for it to take more than 7 guess if your halfway smart. My question is whats the math behind this, and how could I figure the number of guess for like 1-1000, whats the formula?

Thanks!

share|improve this question
3  
What you want to understand for this is the ceiling of base two logarithms. –  Baby Dragon Feb 20 '13 at 3:01

1 Answer 1

up vote 8 down vote accepted

Hint: $2^7=128>100$. That is, you can simply guess in the middle and bisect until you get to the solution.

In general, just find the smallest power of $2$ greater than the max number in your set. For $1000$, you should be able to get it in $10$ guesses, because $2^{10} = 1024$.

share|improve this answer
    
I see! Thanks. + 1 –  JABFreeware Feb 20 '13 at 3:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.