# 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]

### 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: • 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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.