Programming Enigma Puzzles
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]
 | Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
 | Jim Randell on Enigma 773: Duodecimal |
 | Brian Gladman on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
 | ruudvanderham on Enigma 773: Duodecimal |
| Jim Randell on Enigma 773: Duodecimal |
Enigmatic Code 
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:
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.
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.
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.