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]

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.

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