Sunday Times Teaser 2784 – Three Lives

by Ian Kay

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”?

This requires an adjustment of the well known binary splitting algorithm (which is often used as an exercise in computer science courses because it is very easy to get the details wrong and end up with a version that seems to work but doesn’t). I have implemented this algorithm quite a few times over the years and have frequently fallen foul of its subtleties so I hope I have got it right this time!

It is very similar in structure to Jim’s version below and I have adopted his command line interface so that the performance of the two versions can be compared.

2. Without the complication of “lives” the maximum amount of numbers that can be distinguished with n guesses is given by:

G(1) = 1
G(n + 1) = 2G(n) + 1

which gives:

G(n) = 2^n – 1

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

This Python program recursively examines the possibilities (and you can specify a different amount of numbers or lives on the command line):

(It uses the cached() function from the enigma.py library to speed up the execution.

For the problem in the puzzle text the first guess can be any number between 6 and 11.

It turns out that with 3 lives we can distinguish up to 25 numbers using a strategy of up to 5 guesses. In this case the first guess should be 11.