S2T2

Jim Randell 7:57 am on 18 March 2025 Permalink Reply
Tags: by: Nick MacKinnon ( 52 )   

• 

  Jim Randell 7:57 am on 18 March 2025 Permalink | Reply

  Each team has played 2 matches, so the possible outcomes are:

  w+w = 6 points
  w+d = 4 points
  w+l = 3 points
  d+d = 2 points
  d+l = 1 point
  l+l = 0 points

  So, if each of the teams has a different number of points, there can be no more than 6 teams in the league. And we are told there are at least 5 teams.

  There were quite a lot of conditions to keep track of, so I opted to use a MiniZinc model, and then look for a unique solution given the number of teams in the league (using the minizinc.py wrapper).

  The following Python/MiniZinc program runs in 649ms.

  from enigma import (irange, subsets, str_upper, sprintf, printf)
  from minizinc import MiniZinc
  
  # find solutions for <n> teams
  def solve(n):
    model = sprintf(r"""
  
    include "globals.mzn";
  
    set of int: Teams = 1..{n};
  
    % record goals scored in the matches
    % 0 = unplayed
    % >0 = goals scored + 1
    array [Teams, Teams] of var 0..10: x;
  
    % no team plays itself
    constraint forall (i in Teams) (x[i, i] = 0);
  
    % unplayed games are unplayed by both sides
    constraint forall (i, j in Teams where i < j) (x[i, j] = 0 <-> x[j, i] = 0);
  
    % each team has played exactly 2 games (= positive values)
    constraint forall (i in Teams) (sum (j in Teams) (x[i, j] > 0) = 2);
  
    % each team has scored the same number of goals (over both games)
    function var int: goal(var int: X) = if X > 0 then X - 1 else 0 endif;
    function var int: goals(var Teams: i) = sum (j in Teams) (goal(x[i, j]));
    constraint all_equal([goals(i) | i in Teams]);
  
    % points are in alphabetical order
    function var int: pt(var int: X, var int: Y) = if X > 0 /\ Y > 0 then 3 * (X > Y) + (X = Y) else 0 endif;
    function var int: pts(var Teams: i) = sum (j in Teams where j != i) (pt(x[i, j], x[j, i]));
    constraint forall (i in Teams where i > 1) (pts(i) < pts(i - 1));
  
    % score in B vs E match was 3-2 (so values are 4, 3)
    constraint x[2, 5] = 4 /\ x[5, 2] = 3;
  
    % all winning goal margins are 1
    constraint forall (i, j in Teams where i != j) (x[i, j] > x[j, i] -> x[i, j] = x[j, i] + 1);
  
    solve satisfy;
    """)
  
    m = MiniZinc(model, solver="minizinc -a --solver chuffed")
    for s in m.solve():
      yield s['x']
  
  # output matches for <n> teams, solution <x>
  def output(n, x):
    for i in irange(0, n - 1):
      for j in irange(i + 1, n - 1):
        (a, b) = (x[i][j] - 1, x[j][i] - 1)
        if a == b == -1: continue
        printf("{i} vs {j} = {a} - {b}", i=str_upper[i], j=str_upper[j])
    printf()
  
  # find possible points totals for 2 matches scoring 0, 1, 3.
  tots = set(x + y for (x, y) in subsets([0, 1, 3], size=2, select='R'))
  printf("tots = {tots}")
  
  # consider leagues with at least 5 teams
  for n in irange(5, len(tots)):
    ss = list(solve(n))
    k = len(ss)
    printf("[{n} teams -> {k} solutions]")
    if k == 1:
      for x in ss:
        output(n, x)
  

  Solution: The results are: A vs C = 2-1; A vs F = 3-2; B vs D = 2-2; B vs E = 3-2; C vs F = 4-3; D vs E = 3-3.

  The points are:

  A = 6 points (2 wins)
  B = 4 points (1 win + 1 draw)
  C = 3 points (1 win)
  D = 2 points (2 draws)
  E = 1 point (1 draw)
  F = 0 points

  With 5 teams there are 3 possible sets of matches, so this does not provide a solution:

  A vs C = 1-0; A vs E = 3-2; B vs D = 1-1; B vs E = 3-2; C vs D = 4-3;
  A vs C = 2-1; A vs D = 4-3; B vs D = 3-3; B vs E = 3-2; C vs E = 5-4
  A vs D = 1-0; A vs E = 2-1; B vs C = 0-0; B vs E = 3-2; C vs D = 3-3

  LikeLike