S2T2

Jim Randell 8:20 am on 3 June 2026 Permalink Reply
Tags: by: Nick MacKinnon ( 59 )   

• 

  Jim Randell 8:21 am on 3 June 2026 Permalink | Reply

  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: break
  

  Solution: 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 | Reply

    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:

    I1 → { I, p1, g8, + }

    The other teams have multiple candidates, so for Team D,we add candidates like this:

    D2 → { D, p2, g2, + }
    D3 → { D, p3, g1, + }
    D4 → { D, p4, g0, 0 }
    D5 → { D, p5, g1, − }
    …
    D9 → { D, p9, g5, − }

    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 in the bottom 3 (nor 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:
          return (d['B'] < d['C'])
        except KeyError:
          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

  • 

    Jim Randell 10:57 am on 6 June 2026 Permalink | Reply

    Here is some additional analysis that can be used to eliminate some of the cases under consideration, or provide a complete manual solution (also outlined below by John Crabtree).

    The positions of the teams in both years are 1 .. n, and the movement of each team is the difference in the positions.

    The sum of the n (signed) movements is therefore 0, so the upward movements must be balanced by the downward movements. (i.e. they have the same (absolute) sum).

    The largest possible movement is (n − 1) places, and no team moves the same (absolute) number of places. So with n teams all possible gaps from 0 to (n − 1) must be used, each exactly once.

    And these gaps can be collected into the “ups” and “downs”, each of which must have the same (absolute) sum. That value is then:

    t = tri(n − 1) / 2

    So, of the n values under consideration we can discard any where tri(n − 1) is not even.

    This leaves the following (n, t) values to consider:

    n = 9 → t = 18
    n = 12 → t = 33
    n = 21 → t = 105
    n = 24 → t = 138

    But we only have n / 3 “ups” we can use, one of which is the bottom team moving up (n − 1) places to the top to make the largest possible movement.

    We can try and see what the largest possible total for collection of n / 3 “ups” is.

    The second largest is achieved if the second to bottom team moves up to second place, this is a move of (n − 3) places.

    And the next largest is if the third to bottom moves up to third place, a move of (n − 5) places. And so on.

    So for each of our values the maximum possible sum of the “ups” (m) is:

    n = 9 → m = 8 + 6 + 4 = 18
    n = 12 → m = 11 + 9 + 7 + 5 = 32
    n = 21 → m = 20 + 18 + 16 + 14 + 12 + 10 + 8 = 98
    n = 24 → m = 23 + 21 + 19 + 17 + 15 + 13 + 11 + 9 = 128

    So, only n = 9 can achieve the required total, and then only by making the maximum possible arrangement of “up” moves.

    (More generally, the maximum possible sum is given by (2/9)n². And we need this to be at least as much as the required total tri(n − 1)/2. This is only possible when n ≤ 9).

    Hence any solution must involve 9 teams (A – I), where:

    I moves from 9th place to 1st place; a move of +8 positions
    H moves from 8th place to 2nd place; a move of +6 positions
    G moves from 7th place to 3rd place; a move of +4 positions

    This gives the required 18 “up” moves, which must be balanced by the remaining 6 teams with moves of: 0, −1, −2, −3, −5, −7 (which sum to −18).

    B must finish below C, but not in the bottom 3, which means B must drop 3 positions (to 5th), and C must drop 1 position (to 4th).

    A is the only remaining team that can drop 7 positions (to 8th).

    F is now the only team that can keep its position (remains 6th).

    And D is the only remaining team that drop 5 positions (to 9th), leaving E to drop 2 positions (to 7th).

    This provides a complete manual solution of the puzzle.

    LikeLike

• 

  John Crabtree 1:49 pm on 4 June 2026 Permalink | Reply

  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