# The Number Guessing Game

Two people are playing an interesting form of a number guessing game, with the following rules:

1. One person is the guesser, and one person is the thinker.
2. The thinker thinks of a number from 1 to 2925 inclusive, and can't change it mid-game.
3. The guesser has 25 guesses to guess the number. If they take more than 25 guesses to guess the number, they lose. The guesser can't guess anything other than a number, or they lose.
4. Every time the guesser guesses, the thinker must (honestly) give one of three responses: your guess is too big, your guess is too small, or your guess is the correct number. If the number is correct, the guesser wins.
5. There's a catch. Every time the answer is "too big", the guesser loses a life. The guesser has three lives at the start of the game. If they have no lives left, they lose.

Is there a way for the guesser to always win this game? If not, how can they maximize their winning chances?

This seems to be

equivalent to the egg-throwing problem for which I posted a generic solution earlier. The 3 lives correspond to 3 eggs, and the 25 guesses correspond to 25 drops. In this case the player loses a life if their guess is too big, which is a perfect analogy for an egg breaking if dropped from a floor too high.

Using the same notation

as in the linked post, we are looking for $$stories(3,25)=\displaystyle{\sum_{i=1}^3}\binom{25}i=25+\frac{25\cdot24}{2}+\frac{25\cdot24\cdot23}{3\cdot2}=2625$$

As shown

in the linked answer, this method is optimal, so identifying one number out of 2925 is not possible with the given restrictions, but if the number is at most 2625, the guesser can find it with lives and guesses remaining.

So if

the thinker chooses the number uniformly, the guesser has $$\frac{2625}{2925}$$ chance to guess it correctly.

• I think the fact that you get told when your solution is spot-on may introduce a small perturbation here. – Gareth McCaughan Oct 23 '18 at 15:33
• That's a good point, @GarethMcCaughan, I missed that one. Feel free to further elaborate based on this idea. – elias Oct 23 '18 at 15:34
• I'm not 100% convinced, but my math matches yours, so I don't think the "your guess is correct" affects the overall chances. – Joel Rondeau Oct 24 '18 at 4:01
• According to the rules the guesser wins if and only if he gets a response of 'your number is correct', so it is not enough for him to know which number the thinker has thought of. Like, if there are 2 numbers, more than enough lives and 1 guesses left, the guesser has 50% to guess the correct number and win, even though he will know what the magic number was after the response in 100% of cases. Maybe this compensates for some of the differences with the egg-drop version, but it still needs to be addressed and discussed in details. – elias Oct 24 '18 at 8:34
• The math checks out. A general algorithm to maximise the utility of guesses would guess the halfway mark if there are 4 or more lives, and guess at intervals of summation to the number of guesses for 3 lives. For 2 lives, the algorithm would guess at intervals equal to the guess, and at 1 life, it will just guess increasing numbers. This is the maximum utility of a guess(given the max guesses and lives). I've brute-force tested the above logic in python, and indeed, it succeeds up to 2625. Coincidentally, if the guesser had 1 more guess or 1 more life, it would be solvable. – Arch2K Oct 25 '18 at 5:57

If it wasn't for the loosing of lives I would start in the middle, say 1462 and go half way up/down depending on the answer. But since we will be loosing lives each time, I would start at

117

and then work out the

1/25

number of the set that is remaining and try that one until I hit the correct number.

• Wouldn't that be your strategy if you would lose a life each time your guess is too small, instead of too big ? With the current rules, I suppose you wanna change $24/25$ into $1/25$ ? – Evargalo Oct 24 '18 at 7:13
• @Evargalo Oops ... correct thanks ... I've updated my answer to reflect that :) – Jim Creak Oct 25 '18 at 0:35