Enigmatic Code

Programming Enigma Puzzles

Enigma 1501: Five sets at Wimbledon

From New Scientist #2663, 5th July 2008

A men’s singles match at Wimbledon is won by the first player to win three sets.  A set is won by the first player to win six games unless the score reaches 5-5; in that case, in the first four sets the set will be won 7-5 or 7-6 (but no set in our match was won 7-6), and in the fifth set play goes on until one player is two games ahead. The longest fifth set in Wimbledon history was won 28-26. Players serve in alternate games.

Our Wimbledon match went to five sets. The number of games in each set was different; the number of games won by the server in each set was different; the percentage of games won by the server in each set was different but was always an integer. Over the whole match exactly half of the games were won by the server.

What was the score in the final set, and how many games in that set were won by the server?

Note: In Wimbledon 2010 the Isner-Mahout match went to 70-68 in the final set (and broke the scoreboard).

[enigma1501]

Advertisements

One response to “Enigma 1501: Five sets at Wimbledon

  1. Jim Randell 22 October 2012 at 7:18 pm

    The following Python program runs in 127ms, and generates all 288 possible matches that satisfy the conditions of the problem. I found this quite a challenging program to get right and make sure it constructs exactly the right set of matches. (Although to get the solution to the problem it is not necessary to enumerate all possible matches, but I like to do constructive solutions where possible).

    from collections import defaultdict, namedtuple
    from enigma import irange, printf, sprintf
    
    # has A won the set? (7-6 doesn't happen in this problem)
    def won(a, b):
      return (a > 5 and a - b > 1) # or (a == 7 and a > b)
    
    # record informatation about a set
    # a - games won by A
    # b - games won by B
    # n - total number of games in the set
    # w - games won by the server
    # p - percentage of games won by the server
    Set = namedtuple('Set', ('a', 'b', 'n', 'w', 'p'))
    
    setn = set() # non-final sets
    setf = set() # final sets
    
    # accumulate scores for up to 54 games
    # scores maps <score> => set of <server wins>
    scores = { (0, 0): set([0]) }
    for n in irange(0, 54):
      r, s = defaultdict(set), n % 2
      for (a, b), wins in scores.items():
        # is the set won?
        if won(a, b) or won(b, a):
          # find integer percentages of server wins
          ss = set()
          for w in wins:
            p, f = divmod(100 * w, n)
            if f > 0: continue
            ss.add(Set(a, b, n, w, p))
          if max(a, b) < 8:
            setn.update(ss)
          if abs(a - b) > 1:
            setf.update(ss)
            continue
        for w in wins:
          r[(a + 1, b)].add(w + 1 - s) # if A wins
          r[(a, b + 1)].add(w + s) # if B wins
      scores = r
    
    # if B served first, compute new w and p
    def swap(s):
      return Set(s.b, s.a, s.n, s.n - s.w, 100 - s.p)
    
    # choose sets for a match
    # n - total number of games
    # w - total number of games won by the server
    # a, b - sets for A and B
    # sets - the sets in the match
    # sn, sw, sp - numbers of games, server wins, percentages seen so far
    # r - accumulate results
    def choose(n, w, a, b, sets, sn, sw, sp, r):
      # check things looks OK
      if a + b < 5 and (a > 2 or b > 2): return
      # are we done?
      if a + b == 5:
        if 2 * w == n:
          printf("{a}-{b} {sets} {w}/{n}", sets=' '.join(sprintf("[{s.a}-{s.b} {s.w}/{s.n} {s.p}%]") for s in sets))
          s = sets[-1]
          r[(s.b, s.a, s.w) if a < b else (s.a, s.b, s.w)] += 1
        return
      # choose an outcome for the next set
      for s in (setn if a + b < 4 else setf):
        if n % 2: s = swap(s)
        # check the number of games, server wins and percentages are different
        if s.n in sn or s.w in sw or s.p in sp: continue
        sa, sb = (0, 1) if s.a < s.b else (1, 0)
        choose(n + s.n, w + s.w, a + sa, b + sb, sets + [s], sn + [s.n], sw + [s.w], sp + [s.p], r)
    
    r = defaultdict(int)
    choose(0, 0, 0, 0, [], [], [], [], r)
    
    for k, v in r.items():
      printf("final set: {k[0]}-{k[1]}, server wins: {k[2]} => {v} solutions")
    

    Solution: The score in the final set is 11-9. 13 games in the final set were won by the server.

    The prohibition of 7-6 sets is not needed to solve the puzzle. The code as presented does not consider winning sets with this score, but you can add a clause to the won() function to allow them, if you wish. (This assumes that serving rules are the same for tiebreak games as for other games, which I think may not be the case in real life, and so could explain why the setter chose to exclude them from the problem).

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: