Enigmatic Code

Programming Enigma Puzzles

Teaser 2784: Three lives

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]

Advertisements

One response to “Teaser 2784: Three lives

  1. Jim Randell 14 February 2016 at 11:58 am

    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) = 2 G(n) + 1

    which gives:

    G(n) = 2^n – 1

    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 Python site) recursively examines the possibilities. It runs in 51ms.

    from enigma import irange, cached, printf
    
    # return the maximum number of guesses required
    # ns - numbers remaining (in order)
    # m - number of lives remaining
    # g - number of guesses so far
    @cached
    def solve(ns, m, g=0, d=0):
      n = len(ns)
      # only one life remaining (or only one number):
      if m == 1 or n == 1:
        # we have to start with the smallest number and work up
        return g + n
      # two or three numbers need up to two guesses (start with the "middle" one)
      # (we don't really need this case, but it speeds things up a bit)
      if n < 4:
        return g + 2
      # more than one life remaining, we can guess any of the numbers
      rs = list()
      for (i, x) in enumerate(ns):
        low = high = -1
        # if we guess low we don't lose a life
        if i < n - 1: low = solve(ns[i + 1:], m, g + 1, d + 1)
        # if we guess high we lose a life
        if i > 0: high = solve(ns[:i], m - 1, g + 1, d + 1)
        # record the worst case
        rs.append(max(low, high))
      # show the outcomes at depth 0
      if d < 1: printf("{ns} -> {rs}")
      # choose the best worst case
      return min(rs)
    
    from sys import argv
    N = (20 if len(argv) < 2 else int(argv[1]))
    L = (3 if len(argv) < 3 else int(argv[2]))
    
    r = solve(tuple(irange(1, N)), L)
    printf("[{N} numbers, {L} lives] min guesses = {r}")
    

    Solution: The “certain number” is 5.

    This diagram shows a decision tree for winning the game in 5 guesses (or fewer).

    Teaser 2784 - Solution

    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 n guesses and 3 lives, L(3, n), is given below:

     n   G(n)  L(3,n)
    
     1     1      1
     2     3      3
     3     7      7
     4    15     14
     5    31     25
     6    63     41
     7   127     63
     8   255     92
     9   511    129
    10  1023    175

    The formula is:

    L(3, n) = C(n, 1) + C(n, 2) + C(n, 3) = n(n² + 5)/6

    See OEIS A004006, where the puzzle is phrased as:

    If you have a tall building and 3 plates and you need to find the highest story, a plate thrown from which does not break, what is the number of stories you can handle given n tries?

    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:

    L(k, n) = C(n, 1) + C(n, 2) + … + C(n, k)

    [*] There was some confusion on the Sunday Times Teasers discussion 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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: