Wednesday, November 16, 2011

7. Given the numbers 1 to 1000, what is the minimum number of guesses needed to find a specific number if you are given the hint of higher or lower for each guess you make?

The minimum number of guesses required to determine a specific number depends in part on luck of the person guessing and the strategic approach of the person guessing.

In theory, the minimum number of guesses required could be as low as 1 guess if the person is extraordinarily lucky.

But the person will not likely be so lucky, so the person will guess strategically.

If the person guessing is risk averse, he might guess 500 and in response to the information that the correct number is higher or lower, he might constantly make his next guess the halfway point of the range he is trying to isolate. For example, his first guess might be 500 midway between 1 and 1000. He will be told higher or lower. Either way his second guess will be the midpoint between 1 and 500 or 501 and 1000. If he continues with this pattern of safely guessing the midpoint for the range he has isolated, he could guess as many as 9 or 10 times to determine the specific number.

How so? 1000/2 = 500/2 = 250/2 = 125/2 =62.5 = 31.25 etc.

Is 9 or 10 the minimum number of guesses that is possible for another approach? No. It might be wiser to change one crucial step, the first step. If he makes his first guess 750 or 250 rather than 500 he reduces the number of guesses required by at least 1. Why? He has started the guessing game with an asymmetrical position. It's not a random guess but a risk taken on the first move that can have tremendous rewards. If he guesses 750 and he is told higher in response, he has reduced his range of numbers significantly and even if he follows the method above exactly as before he has reduced his number of guesses by 1 or 2 at least. If he is unlucky and he is told "lower" in response" he hasn't lost very much. It's early in the game and the risk he took was worth taking as the first move in guessing. He is not likely to have increased the number of times he will have to guess. It is a low-risk, high-potential-return strategy.

No comments:

Post a Comment