### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,123)
- misc (2)
- project euler (2)
- puzzle (31)
- site news (43)
- tantalizer (31)
- teaser (3)

### Site Stats

- 168,282 hits

Programming Enigma Puzzles

24 May 2014

Posted by on **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]

Advertisements

%d bloggers like this:

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.

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:

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

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:

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 1418by stating: “no two teams had the same score”).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.

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.

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.

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).

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.

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.

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

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

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).

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.

Yes, you are right, I’ll see if it can be rescued.