Enigmatic Code

Programming Enigma Puzzles

Enigma 1359: The weaker sex

From New Scientist #2518, 24th September 2005

Some married couples (including my husband and me) entered a “round-robin” squash tournament at our local club. In such a tournament each individual plays each of the others once.

At the end of the tournament my husband had won a prime number of games and so had I. As you might expect, women did much better than men: the number of games won by the worst-performing female was over three times the number of games won by the best-performing male.

How many married couples entered the tournament? In how many games did a man beat a woman?

[enigma1359]

Advertisements

One response to “Enigma 1359: The weaker sex

  1. Jim Randell 31 December 2013 at 8:52 am

    This Python 3 program uses analysis to narrow down possible scoring patterns, then constructs a pattern to show the solution is achievable. It runs in 58ms.

    This program also uses the first() routine from the enigma.py library, which returns the first few items of an iterator (defaulting to 1 item) as a list. It is a simplification of itertools.islice().

    from itertools import count, combinations
    from enigma import T, irange, Primes, chunk, first, printf
    
    # if n is the number of couples (so 2n players) then the total number
    # of games played is t = T(2n-1)
    
    # we need to decompose t into 2n integers (the list of games won by
    # each player). the scores are in the interval [0, 2n-1], and we note
    # that there can only be one score of 0 or 2n-1, and if we generate the
    # wins in order, so the men come first, at least one of the first n
    # scores must be prime, and the nth integer (the lowest scoring women)
    # must be more than 3x the (n-1)th integer (the highest scoring man),
    # and at least one of the last n scores must be prime.
    
    # considering only the men vs. men matches there must be T(n - 1) of
    # them, and a man wins, so the men must have at least this many wins
    # between them (likewise for the womens matches, and there are n^2
    # mixed gender matches), so the number of games which a man beat a
    # woman is the sum of the men's wins less T(n - 1)
    
    # decompose total <t> into <n> increasing integers between <mn> and
    # <mx> with a >3x jump in scores at <j>
    # additionally: only the first integer can be zero
    def decompose(t, n, mn, mx, j):
      # are we done?
      if n == 1:
        if mn <= t <= mx:
          yield [t]
      else:
        for i in irange(mn, min(mx - 1, t)):
          # lower bound
          low = (3 * i + 1 if n == j + 1 else 1)
          for x in decompose(t - i, n - 1, max(i, low), mx, j):
            yield [i] + x
    
    # generate possible winners for each match given the scores
    # ss - list of remaining scores
    # ms - list of victors in each match
    # n - number of players
    # p - player we are considering
    def scores(ss, ms, n, p):
      if p == n:
        yield ms
      else:
        # how many matches have they left to win
        w = ss[0] - ms.count(p)
        if not(w < 0):
          # consider the unplayed matches for player p
          matches = list((p, q) for q in irange(p + 1, n))
          # choose their remaining wins
          for wins in combinations(range(len(matches)), w):
            # generate remaining scores
            yield from scores(ss[1:], ms + [m[int(i not in wins)] for (i, m) in enumerate(matches)], n, p + 1)
    
    # let n be the number of couples
    for n in count(1):
      # t is the total number of games
      t = T(2 * n - 1)
      # for finding prime scores
      primes = Primes(2 * n - 1)
      # w is the number of wins in same gender matches 
      w = T(n - 1)
      # count number of solutions
      r = 0
      # consider decompositions of the total number of games into scores
      for s in decompose(t, 2 * n, 0, 2 * n - 1, n):
        # split the scores into male and female players
        (m, f) = chunk(s, n)
        # the male players must have at least w wins
        if sum(m) < w: continue
        # and there should be prime scores in each gender group
        if all(any(x in primes for x in h) for h in (m, f)):
          # find one possible sequence of wins
          ss = first(scores(s, [], 2 * n, 1))
          if len(ss) > 0:
            printf("scores={s}, man beats woman in {b} matches", b=sum(m) - w)
            r += 1
    
      printf("[n={n}, {r} solutions]")
      if r:
        break
    

    Solution: There were 5 couples in the tournament (10 individual players). There were no games in which a man beat a woman.

    The following diagram shows the winner in each of the matches. The male players are numbered from 1 to 5, and male vs. male matches are shown in blue. The female players are numbered from 6 to 10, and female vs. female matches are show in pink. The remaining matches, shown in orange, are male vs. female matches (and are always won by the female player). The column on the right hand side shows the number of matches won by each player.

    Enigma 1359 - Solution

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: