Enigmatic Code

Programming Enigma Puzzles

Enigma 176: Bye-bye tennis

From New Scientist #1321, 2nd September 1982 [link]

Our local tennis club has just had its annual knockout tournaments. All the male members played in the men’s singles, and all the female members played in the women’s singles. Luckily there was an even number of men and so they were able to form pairs and all take part in the men’s doubles. Similarly, all the ladies took part in the women’s doubles. The men and women paired off as far as possible for the mixed doubles, but some women had to miss this even because of a shortage of men. The total number of matches in all five competitions was just 11 more than the total number of byes necessary in all five competitions (some being necessary in each), and this total number of byes was 100 more than the total number of members in the club.

How many women and how many men in the club?

[enigma176]

Advertisements

One response to “Enigma 176: Bye-bye tennis

  1. Jim Randell 15 March 2014 at 8:14 am

    I assumed that the knockout tournament was a “single-elimination” tournament [ http://en.wikipedia.org/wiki/Single-elimination_tournament ]. The fun here was writing a neat function to determine the number of byes. I wrote a recursive function, so that it can be cached using the cached() function from enigma.py, which is fine for the relatively small number of participants in a tennis tournament. This Python code runs in 36ms.

    from itertools import count
    from enigma import irange, first, cached, printf
    
    # assuming a "single-elimination" tournament
    
    # if there are 2m male members of the club and 2f female members (we
    # are told the men and women can pair up for the doubles matches) then
    # each match results in one member being eliminated so there are 2m-1
    # mens matches and 2f-1 womens matches, there are m-1 mens doubles
    # matches and f-1 womens doubles matches.
    #
    # there are fewer men than women (m < f) so there are 2m mixed pairs,
    # hence 2m-1 mixed doubles matches.
    #
    # so the total number of matches in all five competitions is:
    # (2m - 1) + (2f - 1) + (m - 1) + (f - 1) + (2m - 1)
    # = 5m + 3f - 5
    
    # number of byes for a tournament with n competitors
    @cached
    def byes(n):
      return (0 if (n & (n - 1)) == 0 else byes(n + 1) + 1)
    
    # find possible pairs of (female, male) member counts
    def generate():
      # number of female pairs
      for f in count(2):
        # number of female members
        F = 2 * f
    
        # number of byes in womens singles and doubles
        f1 = byes(F)
        f2 = byes(f)
        # both must be non-zero
        if f1 == 0 or f2 == 0: continue
    
        # number of male pairs
        for m in irange(2, f - 1):
          # number of male members
          M = 2 * m
    
          # compute the total number of matches
          T = 5 * m + 3 * f - 5
    
          # number of byes in mens doubles, and singles
          m1 = byes(M)
          m2 = byes(m)
          # both must be non-zero
          if m1 == 0 or m2 == 0: continue
    
          # total number of byes (mixed doubles is the same as mens singles)
          B = m1 + f1 + m2 + f2 + m1
    
          # total number of matches is 11 more than the total number of byes
          if not(T == B + 11): continue
    
          # total number of byes is 100 more than the number of club members
          if not(B == F + M + 100): continue
    
          # number of female and male 
          printf("women={F} men={M} [f={f} m={m} T={T} B={B}]")
          yield (F, M)
    
    # we only want the first solution
    first(generate())
    

    Solution: There are 130 women and 34 men in the club.

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: