# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1322: Geometric runs

From New Scientist #2481, 8th January 2005

In cross-country races with teams of six runners, the team scores are calculated by adding together the finishing positions of the first four runners in each team, the lowest-scoring team being the winner. Individuals never tie for any position.

The fifth and sixth runners to finish in each team do not contribute to the team score, but if they finish ahead of scoring runners in other teams they make the positions of those runners and their teams’ scores that much worse.

In a race involving seven teams of six runners, the scores of the first four teams formed a geometric progression, as did the scores of the last four teams.

What were the scores of the first and last teams?

This puzzle completes the archive of Enigmas from the beginning of 2005 up to the end of 2013 (and the end of Enigma), which is 459 puzzles. There are also 193 puzzles available from the start of Enigma (in 1979) to the beginning of 1983, which together with a random puzzle from 2000 currently makes up the 653 Enigma puzzles on the site.

[enigma1322]

### 12 responses to “Enigma 1322: Geometric runs”

1. Jim Randell 24 May 2014 at 9:17 am

This Python program looks for possible scores that are in the required geometric progressions, and then, once it finds a possible sequence of scores it tries to find an actual assignment of positions to make up the sequences. This program runs in 2m14s.

```from enigma import irange, diff, chunk, uniq, cached, printf

# there are 7 teams of 6 runners
N = 7 * 6

# possible scoring positions (the final 2 runners can never score)
ns = tuple(irange(1, N - 2))

# generate possible scores that are in geometric progressions
def generate():

# lowest possible team score
lo = sum(ns[:4])
# highest possible team score
hi = sum(ns[-4:])
# highest possible total score
total = sum(ns) - sum(ns[i] + ns[i + 1] for i in irange(4, N - 6, step=6))
printf("[lo={lo} hi={hi} total={total}]")

# possible scores for the 1st placed team
for s1 in irange(lo, min(hi, total // 7)):
# possible scores for the 2nd placed team
for s2 in irange(s1 + 1, min(hi, (total - s1) // 6)):
# s1, s2, s3, s4 are in geometric progression
(s3, r) = divmod(s2 * s2, s1)
if r or s3 > hi: continue
(s4, r) = divmod(s3 * s2, s1)
if r or s4 > hi: continue
t1 = s1 + s2 + s3 + s4
if t1 + s4 * 3 > total: continue

# possible scores for the 5th placed team
for s5 in irange(s4 + 1, min(hi, (total - t1) // 3)):
# s4, s5, s6, s7 are in geometric progression
(s6, r) = divmod(s5 * s5, s4)
if r or s6 > hi: continue
(s7, r) = divmod(s6 * s5, s4)
if r or s7 > hi: continue
t2 = s5 + s6 + s7
if t1 + t2 > total: continue

yield (s1, s2, s3, s4, s5, s6, s7)

# decompose n into m numbers from ns
def decompose(n, m, ns):
if m == 1:
if n in ns:
yield [n]
else:
for (i, x) in enumerate(ns):
if x > n: break
for ds in decompose(n - x, m - 1, ns[i + 1:]):
yield [x] + ds

# can we allocate the remaining positions to the teams? there may
# be many ways to do this, but we only need to find one that works.
# we order the teams by the position of their last scoring runner,
# and then allocate the remaining runners in order
def allocate_remaining(ns, ps):
# add the final 2 runners back in
ns = ns + (N - 1, N)
r = [None] * len(ps)
for (i, x) in zip(sorted((j for (j, _) in enumerate(ps)), key=lambda j: ps[j][-1]), chunk(ns, 2)):
if not(x[0] > ps[i][-1]): return
r[i] = x
return r

# ns - numbers to allocate
# ss - team scores to achieve
# ps - positions for teams allocated so far
# ds - decompositions of team scores
def allocate(ns, ss, ps=[], ds=None):
if not ss:
if allocate_remaining(ns, ps):
yield ps
else:
if ds is None:
# find decompositions for all the scores
ds = dict()
for s in uniq(ss):
ds[s] = list(decompose(s, 4, ns))
else:
# reduce the current decompositions
sns = set(ns)
ds = dict((s, list(v for v in ds[s] if sns.issuperset(v))) for s in uniq(ss))
# try the score with the fewest decompositions
m = min(ds.keys(), key=lambda k: len(ds[k]))
ss2 = list(ss)
ss2.remove(m)
for p in ds[m]:
for x in allocate(diff(ns, p), ss2, ps + [p], ds):
yield x

for ss in generate():
printf("[checking {ss} ...]")
for ps in allocate(ns, ss):
printf("positions = {ps}")
break
```

Solution: The team in 1st place scored 27. The team in last place scored 125.

The scores (from 1st to 7th place) are: 27, 36, 48, 64, 80, 100, 125.

The first four terms form a geometric progression with a common ratio of 4/3. The final four terms form a geometric progression with a common ratio of 5/4.

There are many possible ways for the finishing positions to give the scores above. Here’s one of them:

1st. 1, 2, 3, 21, (26, 27) = 27 points.
2nd. 4, 5, 7, 20, (23, 24) = 36 points.
3rd. 6, 8, 9, 25, (29, 30) = 48 points.
4th. 13, 16, 17, 18, (19, 22) = 64 points.
5th. 10, 11, 28, 31, (32, 33) = 80 points.
6th. 14, 15, 35, 36, (37, 38) = 100 points.
7th. 12, 34, 39, 40, (41, 42) = 125 points.

There are only two possible sequences of scores that form the required geometric progressions. The other one is:

16, 24, 36, 54, 72, 96, 128.

But it is not possible to assign positions to achieve this sequence.

If, however, we allow geometric progressions with a common ratio of 1 (i.e. where some of the teams have the same score), then we can find further solutions. For example, from the additional 99 candidate sequences, the following sequences of scores work:

12, 24, 48, 96, 96, 96, 96.
13, 26, 52, 104, 104, 104, 104.
24, 36, 54, 81, 81, 81, 81.
40, 40, 40, 40, 60, 90, 135.
58, 58, 58, 58, 58, 58, 58.
59, 59, 59, 59, 59, 59, 59.
60, 60, 60, 60, 60, 60, 60.
61, 61, 61, 61, 61, 61, 61.
62, 62, 62, 62, 62, 62, 62.
63, 63, 63, 63, 63, 63, 63.
64, 64, 64, 64, 64, 64, 64.
65, 65, 65, 65, 65, 65, 65.
66, 66, 66, 66, 66, 66, 66.

Since you don’t get a unique answer this way I think we can assume that geometric progression with a common ratio of 1 are not what the puzzle setter had in mind.

I’ve not marked the puzzle as flawed, even though this situation could easily have been avoided in the phrasing of the question (as it was in Enigma 1418 by stating: “no two teams had the same score”).

• Jim Randell 5 June 2014 at 5:20 pm

Here’s a program that takes a different approach, and solves the problem in 265ms.

It constructs the sequence of runners labelled by teams, which it does recursively by keeping track for each team of the remaining score needed and the number of scoring runners remaining. For each position the teams with remaining scores are considered, when the 3rd runner is positioned the position of the 4th runner (the final scoring runner) is determined and is assigned (if possible). The 5th and 6th runners are then placed on the list of non-scoring runners. After scoring runners have been considered for a position then if there are any valid non-scoring runners available one of those is placed in the position.

It also uses a Python exception to pass the first solution found out of the main solver, as I found this was faster than using yield.

The code to determine the possible sequences of scores is the same as my previous version.

```from enigma import irange, printf

# generate possible scores that are in geometric progressions
def generate():

# possible scoring runners
ns = tuple(irange(1, 40))

# lowest possible team score
lo = sum(ns[:4])
# highest possible team score
hi = sum(ns[-4:])
# highest possible total score
total = sum(ns) - sum(ns[i] + ns[i + 1] for i in irange(4, 36, step=6))
printf("[lo={lo} hi={hi} total={total}]")

# possible scores for the 1st placed team
for s1 in irange(lo, min(hi, total // 7)):
# possible scores for the 2nd placed team
for s2 in irange(s1 + 1, min(hi, (total - s1) // 6)):
# s1, s2, s3, s4 are in geometric progression
(s3, r) = divmod(s2 * s2, s1)
if r or s3 > hi: continue
(s4, r) = divmod(s3 * s2, s1)
if r or s4 > hi: continue
t1 = s1 + s2 + s3 + s4
if t1 + s4 * 3 > total: continue

# possible scores for the 5th placed team
for s5 in irange(s4 + 1, min(hi, (total - t1) // 3)):
# s4, s5, s6, s7 are in geometric progression
(s6, r) = divmod(s5 * s5, s4)
if r or s6 > hi: continue
(s7, r) = divmod(s6 * s5, s4)
if r or s7 > hi: continue
t2 = s5 + s6 + s7
if t1 + t2 > total: continue

yield (s1, s2, s3, s4, s5, s6, s7)

# an exception to return the first solution found
class Solved(Exception):
def __init__(self, message, positions):
Exception.__init__(self, message)
self.positions = positions

# sum of the next n available positions from p
def sum_next(ps, p, n):
sn = [0]
s = 0
try:
while True:
while ps[p] > 0:
p += 1
s += p
sn.append(s)
if len(sn) > n: break
p += 1
except IndexError:
pass

return sn

# ps - positions
# p - next position to allocate
# ss - (score, runners) for each team
# ns - non-scoring runners to be allocated
def _solve(ps, p, ss, ns):
# are we done?
if p == 43:
raise Solved("solution found", ps)
# is this position already allocated?
elif ps[p] > 0:
_solve(ps, p + 1, ss, ns)
else:
# try to allocate scoring runners
if ss:
# sum of the next few positions
sn = sum_next(ps, p, 4)
# go through the teams starting with the ones that need lower positions
for t in sorted(ss.keys(), key=lambda k: (ss[k][0] // ss[k][1], -ss[k][1])):
(s, n) = ss[t]
# is this score still possible?
if sn[n] > s: return
# the remaining score is...
r = s - p
ps2 = list(ps)
ss2 = ss.copy()
# allocate the 3rd and 4th runners at the same time
if n == 2:
# can the 4th runner be allocated?
if not(p < r < 41 and ps[r] == 0): continue
# assign the 3rd and 4th runners
ps2[p] = ps2[r] = t
# all scoring runners assigned
del ss2[t]
# 5th and 6th runners can be allocated
# record (team, number of remaining runners, highest scoring position)
ns2 = ns + [(t, 2, r)]
_solve(ps2, p + 1, ss2, ns2)
else:
# assign the runner (1st or 2nd)
ps2[p] = t
# reduce the score and remaining runners
ss2[t] = (r, n - 1)
_solve(ps2, p + 1, ss2, ns)
# allocate a non-scoring runner (if any are available)
for (i, (t, n, r)) in enumerate(ns):
if p > r:
ps2 = list(ps)
ps2[p] = t
ns2 = list(ns)
if n == 1:
del ns2[i]
else:
ns2[i] = (t, n - 1, r)
_solve(ps2, p + 1, ss, ns2)
break

# solve for the specified scores, returning the first solution found
def solve(scores):
try:
_solve([0] * 43, 1, dict((i, (s, 4)) for (i, s) in zip(irange(1, 7), scores)), [])
except Solved as e:
return e.positions
else:
return None

# check all possible sequences of scores
for scores in generate():
printf("[checking {scores} ...]")
ps = solve(scores)
if ps:
printf("positions={ps}", ps=ps[1:])
for t in irange(1, 7):
rs = list(i for (i, p) in enumerate(ps) if p == t)
printf("team {t}: {rs} score = {s}", s=sum(rs[:4]))
printf()
```
2. arthurvause 27 May 2014 at 10:00 pm

My variation, which chooses the smallest possible non-scoring team positions (fifth and sixth) for each combination of scoring positions. It finds an example set of team positions in a respectable 250ms.

```from itertools import combinations, permutations

# best and worst scores
best, worst  = 1+2+3+4,  37+38+39+40

progressions = set()
for d,n in combinations(range(1,7),2):
for m in xrange(1,11):
if m*d**3 >= best and m*n**3 <=worst:
print "candidate geometric progressions of 4 teams", progressions

scores=set()
for p,q in permutations(progressions,2):
if p[3]==q[0]:

def TeamPositions(positions,s,n):
for c3 in combinations(positions & set(range(1,s[n]-5)),3):
fourth=s[n]-sum(c3)
if fourth in positions and fourth>max(c3):
fifths = [x for x in positions- set(c3+(fourth,)) if x>fourth]
if len(fifths)>0:
fifth=min(fifths)
sixths = [x for x in positions- set(c3+(fourth,fifth)) if x>fifth]
if len(sixths)>0:
sixth=min(sixths)
c=tuple(sorted(c3))+(fourth,fifth,sixth)
if n==6:
yield [c]
else:
for p in  TeamPositions(positions-set(c),s,n+1):
yield [c]+p

for s in scores:
print "\nExample position for team scores",s

for teams in TeamPositions(set(range(1,43)),s,0):

used = set()
for team in teams:
print team, "score",sum(team[:4])
for rider in team:
assert(len(used)==42)
break

```
• arthurvause 28 May 2014 at 2:44 pm

I realised that my code above doesn’t exhaustively check that there are no solutions for the scores 16, 24, 36, 54, 72, 96, 128, as only non-scoring postions immediately following the fourth scoring position are checked.

To remedy this, here is another version that checks for any set of scoring postions, and if one is found checks for scoring +non-scoring positions.

The code mecomes a bit messier, but in fact runs slightly faster at 187ms, and verifies that there isn’t any combination of scoring positions for 16, 24, 36, 54, 72, 96, 128.

```from itertools import combinations, permutations

# best and worst scores
best, worst  = 1+2+3+4,  37+38+39+40

progressions = set()
for d,n in combinations(range(1,7),2):
for m in xrange(1,11):
if m*d**3 >= best and m*n**3 <=worst:
print "candidate geometric progressions of 4 teams", progressions

scores=set()
for p,q in permutations(progressions,2):
if p[3]==q[0]:

# find a set of scoring and optionally non-scoring positions for the seven teams
def TeamPositions(positions,s,n,NonScoring):
for c3 in combinations(positions & set(range(1,s[n]-5)),3):
fourth=s[n]-sum(c3)
if fourth in positions and fourth>max(c3):
if NonScoring:
fifthssixths = sorted([x for x in positions- set(c3+(fourth,)) if x>fourth])
if len(fifthssixths)>=2:
fifth,sixth = fifthssixths[0],fifthssixths[1]
c=tuple(sorted(c3))+(fourth,fifth,sixth)
else:
return
else:
c=c3+(fourth,)
if n==6:
yield [c]
else:
for p in  TeamPositions(positions-set(c),s,n+1,NonScoring):
yield [c]+p

for s in scores:
print "\nExample position for team scores",s

for test in TeamPositions(set(range(1,43)),s,0, False):
print "scoring positions exist for",s
print "trying scoring + non-scoring positions..."
for teams in TeamPositions(set(range(1,43)),s,0,True):

used = set()
for team in teams:
print team, "score",sum(team[:4])
for rider in team:
assert(len(used)==42)
print ""
break
break
```
• Jim Randell 1 June 2014 at 10:50 am

Hi Arthur. Thanks for posting your code.

I’ve been looking at this puzzle again to try and see if I can generate a definitive list of solutions where geometric progressions with a common ratio of 1 are allowed, but one bit of your code that I don’t quite follow is the part where non-scoring runners are allocated.

It looks like the algorithm allocates them as it goes along after it allocates the scoring runners for a team. Then it chooses the next two available positions as the non-scoring positions for that team. But how do we know that these positions won’t be required to make up the score of a team whose positions haven’t been determined yet? I think it may be possible that this means the algorithm could fail to find an allocation of positions where one exists. (Although obviously it does find positions that solve the problem).

• arthurvause 2 June 2014 at 9:37 am

Yes, that is correct, allocating the non-scoring postions for each team as it goes along might exclude a possible solution, hence the second version, which checks only scoring positions first, to verify that there are no scoring positions for team scores 16, 24, 36, 54, 72, 96, 128.

The algorithm isn’t ideal, as it doesn’t find all solutions, and would not have worked at all if there had been valid scoring postions for 16, 24, 36, 54, 72, 96, 128, or if there weren’t team positions for 27, 36, 48, 64, 80, 100, 125 with non-scoring positions immediately following the fourth team member.

It was really just an attempt to find a solution quickly. I can’t see a way of performing a rigorous check in a fast time.

In fact I was wondering how anyone could have found a solution to the problem without the aid of a computer program.

• Jim Randell 2 June 2014 at 10:26 am

I think once you’ve found the two possible sequences – 16, 24, 36, 54, 72, 96, 128 and 27, 36, 48, 64, 80, 100, 125 – we can eliminate the first one by summing the terms and comparing them with the triangular numbers T(4), T(8), T(12), …

T(4) = 10 ≤ 16
T(8) = 36 ≤ 40 = 16 + 24
T(12) = 78 > 76 = 16 + 24 + 36

So it is not possible for the first three teams to score 16, 24, 36 (= 76 points) as the sum of the positions of 12 scoring runners has to be at least 78.

So, we’re left with 27, 36, 48, 64, 80, 100, 125 as the only possible solution. So if the question has an answer we can determine it without finding an example of the finishing positions.

I like constructive solutions, so I wrote a program to determine a possible assignment of finishing positions, but it does run slower than I would like.

3. Brian Gladman 20 June 2014 at 7:26 pm

I only noticed this one recently and decided to try it as Jim has given it four stars.

```from itertools import combinations, count
from fractions import Fraction

# A 4 term geometric progression (a, a.(n/d), a.(n/d)^2, a.(n/d)^3),
# where n / d is a rational fraction in its lowest terms,  will have
# integer values only if a is a multiple of d. So a 4 term geometric
# progression is a multiple of (d^3, d^2.n, d.n^2, n^3). The minimum
# first term is 10 (1+2+3+4) and the maximum last term is 154 (37+38
# +39+40) so (n/d)^3 <= 154 / 10 and hence 2.n < 5.d. And n^3 <= 154
# so n < 6.
def geometric_seqs():
# generate possible four term sequences
t = ((d ** 3, d ** 2 * n, d * n ** 2, n ** 3) for n in range(1, 6)
for d in range(1, n) if 2 * n < 5 * d)
# now join two such sequences into one seven term sequence
for a, b in combinations(t, 2):
# the last term of the first equals the first term of the last
if a[-1] == b[0]:
c = a + b[1:]
# now apply a possible multiplier to the whole sequence
for m in count(1):
if m * c[-1] > 154:
break
if m * c[0] >= 10:
yield tuple(m * x for x in c)

# return partitions of the integer 'n' into 'l' different
# integers in increasing order
def int_part(n, l, v = []):
lv = len(v)
# if we have l - 1 parts and the remainder is largest
if lv == l - 1 and n > v[-1]:
# return the partition
yield v + [n]
else:
# otherwise remove another part (larger than previous)
if not lv or n >= (l - lv) * (v[-1] + 1):
for i in range(v[-1] + 1 if lv else 1, n + 1):
yield from int_part(n - i, l, v + [i])

def solve(seq, ns, tt, l):
# if all teams have been allocated winning positions
if l == 7:
yield tt
else:
# find four possible winning positions for team 'l'
for ip in int_part(seq[l], 4):
# if they are so far unallocated, allocate them and
# move on to the next team
if set(ip) < ns:
yield from solve(seq, ns - set(ip), tt + [ip], l + 1)

# the set of scoring positions
scores = set(range(1, 41))
# run through the possible geometric sequences
for seq in geometric_seqs():
# find a valid set of scoring positions for the seven teams
for s in solve(seq, scores, [], 0):
# find the non scoring positions
rem = scores
for v in s:
rem -= set(v)
print('Team scores:        {}'.format(seq))
print('Winning positions : {}'.format(s))
print('No-score positions: {}'.format(tuple(sorted(rem))))
break
```
• Brian Gladman 20 June 2014 at 8:01 pm

The documentation in the first ten lines contains some errors – these lines should be replaced with:

```from itertools import combinations, count

# The geometric progression {a, a.(n/d), a.(n/d)^2, a.(n/d)^3}, where
# n/d is a rational value in its lowest terms,  has integer values if
# d^3 divides a.  It is hence a multiple of (d^3, d^2.n, d.n^2, n^3).
# The minimum first term is 10 (1+2+3+4) and the maximum last term is
# 154 (37+38+39+40) so (n/d)^3 <= 154 / 10 and hence 2.n < 5.d;  also
# n^3 <= 154 so n < 6.
```
• Brian Gladman 20 June 2014 at 8:28 pm

And to play with more than one geometric sequence (for example with some values the same), line 60 needs to be changed to ‘scores.copy()’ (this is really a bug).

• Jim Randell 20 June 2014 at 11:40 pm

Hi Brian. Thanks for posting your code. I haven’t gone through it in detail, but I think you might need something like the allocate_remaining() routine in my first program to check that the non-scoring runners can be allocated given the positions of the scoring runners.

When I run your program it gives the scoring positions for the teams with 100 and 125 points as [16, 17, 27, 40] and [18, 32, 36, 39], but there are only two runners (in positions 41 and 42) that can be the non-scoring runners for both of these teams, so that particular arrangement won’t be possible.