Teaser 2431: [Football league]
From The Sunday Times, 26th April 2009 [link]
Teams A, B, C… (up to some letter) play in a football league. Last season, they finished in alphabetical order. This season, the league consisted of the same teams, but last season’s losers were the champions, and B finished below C, but not in the bottom three. One third of the teams finished higher this season than last; no two moved the same number of places. So, if one team went up four places, no other team will have gone up or down by four places. In particular, just one team had the same position in both seasons.
Starting with the champions, list the order of the teams this season.
This puzzle was originally published with no title.
[teaser2431]
John Crabtree are discussing. 
Frits, 
GeoffR and 
S2T2 
Jim Randell 8:21 am on 3 June 2026 Permalink |
If exactly one third of the teams moved up, then the number of teams must be divisible by 3, and if they are each allocated a letter of the alphabet there can be no more than 26.
B finished below C, but not in the bottom three teams, so there must be at least 5 teams.
So the possible number of teams is: 6, 9, 12, 15, 18, 21, 24.
This Python program looks for the smallest possible number of teams.
It labels the teams from 1 .. n, so last year’s position is the same as the label. It then tries all possible allocations for this year’s positions, and checks to see if all the conditions are met.
It runs in 126ms. (Internal runtime is 55ms).
from enigma import ( Enumerator, irange, subsets, multiset, compare, update, diff, str_upper, item, join, map2str, printf ) # check that pos: map team -> position satisfies the requirements def check(n, pos): # for each team collect the up/down and the gap (updown, gap) = (multiset(), multiset()) for (k, v) in pos.items(): d = k - v updown.add(compare(d, 0)) gap.add(abs(d)) # ups = n/3, non-movers = 1, no duplicate gaps return (updown.count(1) * 3 == n and updown.count(0) == 1 and not gap.is_duplicate()) # solve for teams 1 .. n (= A .. ?) def solve(n): # choose values for teams B and C (1 < C < B < n - 2) for (C, B) in subsets(irange(2, n - 3), size=2): pos1 = { n: 1, 2: B, 3: C } # allocate the remaining positions ks = diff(irange(1, n), pos1.keys()) for vs in subsets(diff(irange(1, n), pos1.values()), size=len, select='P'): pos = update(pos1, ks, vs) if check(n, pos): yield pos # consider multiples of 3 for n in irange(6, 24, step=3): sols = Enumerator(solve(n)) for pos in sols: # construct the order of the teams order = tuple(str_upper[k - 1] for (k, v) in sorted(pos.items(), key=item(1))) # output solution printf("{n} teams -> {order} [pos = {pos}]", order=join(order), pos=map2str(pos)) # stop at first n with solutions if sols.count > 0: breakSolution: The order of the teams (first to last) is: I, H, G, C, B, F, E, A, D.
Fortunately the solution occurs with 9 teams, because this approach gets much slower as the number of teams increases. (I used a more sophisticated version of this approach to check teams up to 18, but it would take too long to check 21 and 24).
LikeLike
Jim Randell 4:37 pm on 5 June 2026 Permalink |
Here is a solution that uses the exact multiset cover solver [[
mcover()]] from the enigma.py library to consider situations with 6 – 24 teams.For each team and possible position it constructs a set of tokens giving the team name, the position, the amount of movement, the direction of movement.
So, for example in the situation with 9 teams, team I has only one possible position (it must end up first), so we add the following candidate:
The other teams have multiple candidates, so for Team D,we add candidates like this:
Once all the candidates are set up we use the [[
mcover()]] solver to find a set of team/positions that give: 1 of each team, 1 of each position, 1 of each gap, n/3 teams moving up, 1 team staying in the same position, the rest of the teams moving down.The program is able to check all situations with 6 – 24 teams, without additional analysis, in 9.3s, and verifies that the result given above is the only solution.
from enigma import ( irange, multiset, mcover, compare, ediv, str_upper, sprintf as f, map2str, printf ) # solve the puzzle for n teams def solve(n): # values are: # A .. n = team name # p1 .. pn = 1st - nth position this year) # g0 .. g{n - 1} = positions moved (abs) # +|-|0 = up/down/same # # then we need to find values that give us: # 1 of each team # 1 of each position # 1 of each gap value # n/3 up, 1 same, rest down # construct the map of <team>+<pos> -> <values> m = dict() def value(k, p, g, s): m[f("{k}{p}")] = multiset.from_seq([k, f("p{p}"), f("g{g}"), s]) # last team (= team n) must move from last to pos 1 k = str_upper[n - 1] value(k, 1, n - 1, '+') # fill out possible positions for teams A .. n-1 for i in irange(1, n - 1): k = str_upper[i - 1] # team B cannot finish if the bottom 3 (not team C in the bottom 4) M = (n - 4 if k == 'C' else n - 3 if k == 'B' else n) for g in irange(-(n - 2), +(n - 2)): p = i + g if not (p < 2 or p > M): value(k, p, abs(g), compare(g, 0, vs="+0-")) # set up the target multiset: tgt = multiset() # each team appears once tgt.update_from_seq(str_upper[k - 1] for k in irange(1, n)) # each position is occupied once tgt.update_from_seq(f("p{i}") for i in irange(1, n)) # each gap is occupied once tgt.update_from_seq(f("g{i}") for i in irange(0, n - 1)) # n/3 ups; 1 non-mover; the rest are down k = ediv(n, 3) tgt.update_from_dict({'+': k, '0': 1, '-': n - (k + 1)}) # reject situations where B is higher up the table than C def reject(ss): d = dict((x[0], int(x[1:])) for x in ss) try: if d['B'] < d['C']: return True except KeyError: pass return False # find exact covers for ss in mcover(m, tgt, reject): # record teams by their position d = dict((int(x[1:]), x[0]) for x in ss) # output teams in order printf("{n} teams -> {d}", d=map2str(d, enc="")) # consider possible numbers of teams for n in irange(6, 24, step=3): solve(n)It we stop looking after the first solution is found (like my first program) the internal execution time is only 2.6ms.
LikeLiked by 1 person
John Crabtree 1:49 pm on 4 June 2026 Permalink |
Let there be 3n teams.
The maximum number of places gained is (3n – 1) + (3n – 3) + …(n + 1) with n terms.
The minimum number of places lost is (3n – 2) + (3n – 4) + …(n) + sum[0 to (n -1)].
And so n >= n(n-1)/2, ie n<=3
If n = 1 or 2, the sum of the changes in places is odd. And so n = 3, with places gained = places lost = 18.
The changes in the places are then forced: champions I up 8 to 1; H up 6 to 2; G up 4 to 3; A (not B) down 7 to 8; D (not B or C) down 5 to 9; B down 3 (max) to 5 and C down 1 to 4; E down 2 to 7; and F stays at 6.
LikeLike