Enigmatic Code

Programming Enigma Puzzles

Enigma 1286: Mixed singles

From New Scientist #2444, 24th April 2004 [link]

Some players entered a “round robin” tennis tournament, where each player plays each of the others once, with each match resulting in a win for one of the players. At the end of the tournament I noted how many matches each of the players had won. The men were pretty pathetic, winning only one match each. Even so, Alan beat Barbara in their match. On the other hand, Christine beat David: had that result been reversed all the women would have won the same number of matches.

How many men and how many women entered the tournament?

Note: I am still waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment. The latest estimate is that I’ll have a connection by the end of October 2014.

[enigma1286]

Advertisements

2 responses to “Enigma 1286: Mixed singles

  1. Jim Randell 13 October 2014 at 2:20 pm

    This Python 3 program constructively produces possible tables that satisfy the constraints of the problem. It runs in 51ms.

    I’ve assumed that Alan (A) and David (D) are men and Barbara (B) and Christine (C) are women.

    from itertools import count
    from enigma import irange, T, diff, printf
    
    from copy import deepcopy
    
    # a class for the table
    # the entry at [i][j] is 1 if <i> beats <j> (0 otherwise)
    class Table(object):
    
      # an empty n x n table
      def __init__(self, n):
        self.g = list()
        for i in irange(0, n - 1):
          r = [None] * n
          r[i] = 0
          self.g.append(r)
    
      # set [i][j] to v (1 for a win, else 0)
      def set(self, i, j, v):
        self.g[i][j] = v
        self.g[j][i] = 1 - v
    
      # get the value at [i][j]
      def get(self, i, j):
        return self.g[i][j]
    
      # get the row for player <i>
      def row(self, i):
        return self.g[i]
    
      # iterate over the rows of the table
      def __iter__(self):
        yield from self.g
    
      # make a table like this one, except [i][j] = v
      def update(self, i, j, v):
        s = deepcopy(self)
        s.set(i, j, v)
        return s
    
    # check the configuration
    # n - number of players
    # m - number of men
    # w - number of women
    # t - number of games
    def check(n, m, w, t):
    
      # overall there are t wins, the men win m matches
      # leaving t - m to be distributed amongst the women
      # one of which scores one more than the rest
      # so t - m - 1 must be divisible by w
      (x, r) = divmod(t - m - 1, w)
      if r > 0: return
    
      # make a grid
      g = Table(n)
    
      # A (player 0) beat B (player n - 1)
      g.set(0, n - 1, 1)
      # and A is a man, so loses all his other matches
      for i in irange(0, n - 1):
        if g.get(0, i) is None:
          g.set(0, i, 0)
    
      # as A lost all his other matches he is beaten by D (player 1),
      # who is also a man, so D loses all his other matches,
      # including to C (player n - 2)
      for i in irange(0, n - 1):
        if g.get(1, i) is None:
          g.set(1, i, 0)
    
      # complete the table
      yield from complete(g, m, x, n - 2)
    
    # find possible completions for the table
    # g - the partially filled out table
    # m - the number of men (first m rows)
    # x - how many wins for each woman (the remaining rows)...
    # C - ... except row C which has x + 1 wins
    def complete(g, m, x, C):
      # find a row that needs completing
      for (i, r) in enumerate(g):
        if None not in r: continue
        # find an empty value
        j = r.index(None)
        # and fill it out
        for v in (0, 1):
          g2 = g.update(i, j, v)
          r2 = g2.row(i)
          if r2.count(None) == 0:
            # if we've completed a row
            if i < m:
              # a man must have exactly one win
              if r2.count(1) != 1: continue
            else:
              # a woman must have exactly x wins (or x + 1 wins for C)
              if r2.count(1) != (x + 1 if i == C else x): continue
          yield from complete(g2, m, x, C)
        break
      else:
        # we're done
        yield g
    
    def solve():
      # there are at least 2 men (A, D) and 2 women (B, C)
      for n in count(4):
        # the number of matches
        t = T(n - 1)
        # determine the number of men <m> and women <w>
        for m in irange(2, n - 2):
          w = n - m
          # check this is possible
          for g in check(n, m, w, t):
            printf("n={n} m={m} w={w} t={t}")
            # output the table
            for (i, r) in enumerate(g):
              printf("player {i}: {r} wins={s}", s=r.count(1))
            # terminate after the first result
            return
    
    solve()
    

    Solution: There were 2 men and 4 women in the tournament.

    Here’s a diagram of the possible matches played, a square with a 1 in it indicates that the player in that row beat the player in that column:

    Enigma 1286 - Solution

    • Jim Randell 13 October 2014 at 2:24 pm

      Analytically we can see that m men play T(m – 1) matches amongst themselves, and each of them must be won by a man.

      We are told that there are at least 2 men, and one of them wins a match against a woman. So there can be at most m – 1 matches amongst the men.

      So, we are looking for m where m ≥ 2 and T(m – 1) ≤ m – 1.

      The only possible value is m = 2.

      So the two men are A and D, and D beats A when they play. They each lose the rest of their matches.

      The only remaining variable is w, the number of women (w ≥ 2).

      There are T(w + 1) matches in total, 2 of them won by men and the remaining T(w + 1) – 2 must be 1 more than a multiple of w.

      T(w + 1) – 2 = kw + 1
      ⇒ k = (w + 3 – 4/w) / 2

      So, in order for k to be a whole number it follows that w must be a divisor of 4 (w ≥ 2). The only possible values are 2 and 4.

      w = 2 ⇒ k = 3/2
      w = 4 ⇒ k = 3

      Hence there are 2 men and 4 women (6 players in total). The men win 1 game each, the women win 3 games each, except for Christine who wins 4.

      It is now easy to construct a set of possible matches, as follows:

      If the men are A, D, and the women are B, C, X, Y. Then:

      A beat B, and loses the rest of his matches (D, C, X, Y). (1 win).

      D beat A, and loses the rest of his matches (B, C, X, Y). (1 win).

      X already has 2 wins (against A and D), let’s suppose they also beat Y, and lose against B and C to give the required 3 wins.

      Y has 2 wins (against A and D), and lost against X. So needs one more win against B or C. Let’s say Y beats B for 3 wins.

      B has wins against D and X, and has lost to A and Y, so needs to win against C to get 3 wins.

      All matches are now specified and C has wins against A, D, X, Y and lost against B to give 4 wins, as required.

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: