You are asked to guess an integer between 1 and N inclusive.
Each time you make a guess, you are told either:
(a) you are too high,
(b) you are too low, or
(c) you got it!
You can guess as many times as you like, but are only allowed to guess too high 10 times and too low 3 times. That is, the 4th time you make a guess and are too low, or the 11th time you make a guess and are too high, you lose the game.
What is the maximum N for which you are guaranteed to be able to accomplish this?
Clarification: For example, if you were allowed to guess too high once and too low once, you could guarantee to guess the right answer if N=5, but not for N>5 . So, in this case, the answer would be 5.
start off as in the example, using some small values. You will see a pattern developing.
To guarantee being able to guess the integer between 1 and N inclusive, even with the given restrictions, we need to determine the maximum N that allows us to make a sufficient number of guesses.
Let's analyze the maximum number of possible guesses we can make before losing the game:
- We are allowed to guess too high 10 times, so we need to be able to eliminate at least 10 numbers.
- We are allowed to guess too low 3 times, so we need to be able to eliminate at least 3 numbers.
To eliminate the maximum number of possible numbers, we can alternate between guessing too high and too low. This allows us to eliminate both more than 10 numbers and more than 3 numbers:
- We can make 10 guesses that are too high, eliminating at least 10 numbers.
- Then, we can make 3 guesses that are too low, eliminating at least 3 numbers.
By alternating between too high and too low guesses, we can eliminate at least 10 + 3 = 13 numbers. Therefore, the maximum N for which we are guaranteed to be able to guess the integer is 13.
To summarize, the maximum N is 13.
To find the maximum value of N for which you are guaranteed to be able to accomplish this, let's analyze the worst-case scenario for each type of guess.
First, let's consider the worst-case scenario for guessing too high. In this case, we want to minimize the number of guesses we need to reach the correct answer. Since we are allowed a maximum of 10 guesses that are too high, we can divide the range of possible values (1 to N) into 11 equally-sized intervals. For example, if N is 100, each interval would be 10: [1-10], [11-20], [21-30], and so on. By doing this, we ensure that in the worst case scenario, we will need a maximum of one guess in each interval to find the correct answer, totaling 11 guesses.
Now, let's consider the worst-case scenario for guessing too low. In this case, we want to maximize the number of guesses we will need to reach the correct answer while staying within the limit of 3 guesses that are too low. We can achieve this by dividing the range of possible values (1 to N) into 4 equally-sized intervals. For example, if N is 100, each interval would be 25: [1-25], [26-50], [51-75], [76-100]. This way, in the worst-case scenario, we will need a maximum of one guess in each interval to find the correct answer, totaling 4 guesses.
To find the maximum N, we need to find the minimum value where the worst-case scenarios for both types of guesses coincide. In this case, it happens when the number of intervals for each scenario is the same, which is 11. Therefore, the maximum N for which you are guaranteed to accomplish this is the upper bound of the last interval.
So, the maximum N is the upper bound of the 11th interval, which is:
Upper bound = (Number of intervals - 1) * Interval size
Upper bound = (11 - 1) * Interval size
Upper bound = 10 * Interval size
In the scenario with the largest interval size for guessing too high (10), the maximum N would be:
Maximum N = 10 * 10
Maximum N = 100
Therefore, you are guaranteed to be able to accomplish this for N up to 100.