Guess that number!
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 4 th time you make a guess and are too low, or the 1 1 th 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.
Image credit: mynokiathemes.blogspot.com .
The answer is 1364.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
@Calvin Lin This is a repost of a problem I had previously deleted but was later added to the logical reasoning challenges.
Log in to reply
Updated. Thanks!
Nicely done.
Define N ( H , L ) = 0 if N < 0 or H < 0
Now consider:
M
(
H
,
L
)
=
N
(
H
−
1
,
L
−
1
)
+
1
,
M
(
0
,
L
)
=
1
M
(
H
,
0
)
=
1
you can rewrite the above occurrence in the following form:
M
(
H
,
L
)
=
M
(
H
,
L
−
1
)
+
M
(
H
−
1
,
L
)
Visually, we are assigning points to a grid by, for each point, taking the sum of the point to the left and above. This is highly suggestive of something like Pascal's triangle. Indeed,
M
(
H
,
L
)
=
(
H
H
+
L
)
satisfies the recurrence for M above with the given base cases because, by Pascal's Identity,
(
H
H
+
L
−
1
)
+
(
H
−
1
H
+
L
−
1
)
=
(
H
H
+
L
)
and it can easily checked that the choose function satisfies the given base cases.
So, by resubstitution,
N
(
H
,
L
)
=
(
H
+
1
H
+
L
+
2
)
−
1
.
Every time you take a guess, you divide the problem up into two new problems... One where you reduce your number of "too low" guesses by 1, and one where you reduce your number of "too high" guesses by 1. And, the number of N is either all the ones above your guess or all the ones below your guess. So, the recursive equation can be defined as follows:
Let N ( H , L ) = The maximum number you can accomplish this in given that you can get only get H "too high"s and L "too low"s, then...
N ( 0 , L ) = L + 1
N ( H , 0 ) = H + 1
N ( H , L ) = 1 + N ( H − 1 , L ) + N ( H , L − 1 )
Using this, N ( 1 0 , 3 ) = 1 3 6 4