**From The Sunday Times, 31st January 2016** [link]

I think of a whole number from 1 to 20 inclusive and Andy has to try to guess the number. He starts with three lives and makes successive guesses: after each guess I tell him whether it is right or too low or too high. If it is too high he loses one of his lives. To win the game he has to guess my number before his lives run out. He has developed the best possible strategy and can always win with a certain number of guesses or fewer. In fact no-one could be sure of winning with fewer guesses than that “certain number”.

What is that “certain number”?

[teaser2784]

### Like this:

Like Loading...

*Related*

Without the complication of “lives” the maximum amount of numbers that can be distinguished with

nguesses [*] is given by:which gives:

So for 20 numbers the best strategy we can hope for will require 5 guesses in the worst case.

This Python program (a slight modification of the version I put up on the

Puzzling In Pythonsite) recursively examines the possibilities. It runs in 51ms.Solution:The “certain number” is 5.This diagram shows a decision tree for winning the game in 5 guesses (or fewer).

The numbers in curly brackets indicate the possible candidates for the “secret” number. The numbers in round brackets indicate the number of lives remaining.

The tree shown starts with a guess of 11, but you can start with any number from 6 – 11.

Using the code above you can specify the amount of numbers to choose from and the number of lives on the command line.

With 3 lives we can distinguish up to 25 numbers with up to 5 guesses, and in this case the first guess should be 11.

In fact the greatest amount of numbers we can distinguish with

nguesses and 3 lives,L(3, n), is given below:The formula is:

See OEIS A004006, where the puzzle is phrased as:

This is an interesting variation because on the final throw whether the plate smashes or not gives you different outcomes, whereas in the guessing game a final guess may be needed that can only have one outcome in order for the guesser to state the secret number and win the game.

Similarly:

—

[*] There was some confusion on the

Sunday Times Teasersdiscussion site about what constituted a “guess”, but in the context of a guessing game I think it is fairly clear that it means a statement by the guessing player that suggests a value for the “secret” number. If the question had been phrased in terms of plate throwing instead of number guessing the confusion might not have arisen.