Sunday Times Teaser 3004 – Going Up

by John Owen

Published Sunday April 19 2020 (link)

In our football league, the teams all play each other once, with three points for a win and one for a draw. At the end of the season, the two teams with most points are promoted, goal difference being used to separate teams with the same number of points.

Last season’s climax was exciting. With just two games left for each team, there were several teams tied at the top of the league with the same number of points. One of them, but only one, could be certain of promotion if they won their two games. If there had been any more teams on the same number of points, then none could have guaranteed promotion with two wins.

How many teams were tied at the top of the league, and how many of the remaining matches involved any of those teams?

One Comment Leave one →

Brian Gladman permalink

My thanks to John Crabtree for offering and giving me a strategy for solving this teaser. Given that I dislike anything to do with football and football teasers, I have since spent an inordinate amount of time trying (and failing) to find a fast program to give the solution. The problem is that as the number of tied teams increases, the different number of ways these teams can play against each other (and other teams) increases rapidly and for each such arrangement we have to look at all win/loss combinations. This is time consuming but is fast enough for up to six tied teams, but at seven and beyond it becomes very slow. I have found some speed ups but all of them are essentially ‘cheating’ in that they simply bypass the final step, which is to find a number of tied teams for which no team that wins two matches can guarantee promotion. Its very unlikely that I will spend more time on this but Jim Randell has found the same issue in his solution where he indicates that he might do some more work on this.


from itertools import count, product

# credit to Jim Randell for some speed improvements

# update the dictionary of teams when a team is
# paired off with another team
def update(d, k):
  if k == 'x':
    return d
  dc = d.copy()
  if dc[k] == 1:
    del dc[k]
  else:
    dc[k] = 1
  return dc

# generate all arrangements of the matches between the
# teams given in the dictionary <td_tms> both between
# each other and between them and lower placed teams
def matches(td_tms, mchs=[]):
  if not td_tms:
      yield mchs
  else:
    a = list(td_tms)[0]
    tc = update(td_tms, a)
    for b in list(tc) + ['x']:
      if b > a and (b == 'x' or not mchs or a + b > mchs[-1]):
          yield from matches(update(tc, b), mchs + [a + b])

# for saving possible solutions
sol = None
# the number of tied teams
for n in count(2):  
  # a dictionary giving the number of matches per team with 
  # team names A, B, C, ...
  td_tms = {chr(ord('A') + i):2 for i in range(n)}
  
  # find all arrangements of the two final matches between 
  # the tied teams and between them and lower placed teams 
  # (all denoted by 'x')
  for mchs in matches(td_tms):
  
    # for this arrangement of matches, save (in cp) those 
    # teams for which two wins brings certain promotion;
    # save (in pp) those teams for which two wins brings
    # possible but not certain promotion
    pp_cp, none_certain = (set(), set()), False
    
    # consider possible outcomes for this match arrangement
    for rs in product(*mchs):

      # skip further consideration of this arrangement once 
      # no team is certain of promotion with two wins
      if pp_cp[0].issuperset(td_tms):
        none_certain = True
        break
  
      # find the teams with two wins
      tw = tuple(t for t in td_tms.keys() if rs.count(t) == 2)
      # if less than three teams have two wins, those with
      # two wins know that they will be promoted, otherwise
      # promotion is possible but not certain
      pp_cp[len(tw) < 3].update(tw)
    
    # check that A is the only team in this arrangement of 
    # matches for which there are match results in which 
    # two wins by them guarantee promotion and no match
    # results in which this doesn't guarantee promotion
    if pp_cp[1].difference(pp_cp[0]) == {'A'}:
      print(n, mchs)
      sol = mchs
      break

  if none_certain:
    # with this number of teams, no team can be certain of promotion with
    # two wins so the previous number of teams gives the solution
    if sol:
      print(f"\n{n - 1} tied teams in {len(sol)} remaining matches {sol}")
      break

from itertools import count, product

# credit to Jim Randell for some speed improvements

# update the dictionary of teams when a team is

# paired off with another team

def update(d, k):

if k == 'x':

return d

dc = d.copy()

if dc[k] == 1:

del dc[k]

else:

dc[k] = 1

return dc

# generate all arrangements of the matches between the

# teams given in the dictionary <td_tms> both between

# each other and between them and lower placed teams

def matches(td_tms, mchs=[]):

if not td_tms:

yield mchs

else:

a = list(td_tms)[0]

tc = update(td_tms, a)

for b in list(tc) + ['x']:

if b > a and (b == 'x' or not mchs or a + b > mchs[-1]):

yield from matches(update(tc, b), mchs + [a + b])

# for saving possible solutions

sol = None

# the number of tied teams

for n in count(2):

# a dictionary giving the number of matches per team with

# team names A, B, C, ...

td_tms = {chr(ord('A') + i):2 for i in range(n)}

# find all arrangements of the two final matches between

# the tied teams and between them and lower placed teams

# (all denoted by 'x')

for mchs in matches(td_tms):

# for this arrangement of matches, save (in cp) those

# teams for which two wins brings certain promotion;

# save (in pp) those teams for which two wins brings

# possible but not certain promotion

pp_cp, none_certain = (set(), set()), False

# consider possible outcomes for this match arrangement

for rs in product(*mchs):

# skip further consideration of this arrangement once

# no team is certain of promotion with two wins

if pp_cp[0].issuperset(td_tms):

none_certain = True

break

# find the teams with two wins

tw = tuple(t for t in td_tms.keys() if rs.count(t) == 2)

# if less than three teams have two wins, those with

# two wins know that they will be promoted, otherwise

# promotion is possible but not certain

pp_cp[len(tw) < 3].update(tw)

# check that A is the only team in this arrangement of

# matches for which there are match results in which

# two wins by them guarantee promotion and no match

# results in which this doesn't guarantee promotion

if pp_cp[1].difference(pp_cp[0]) == {'A'}:

print(n, mchs)

sol = mchs

break

if none_certain:

# with this number of teams, no team can be certain of promotion with

# two wins so the previous number of teams gives the solution

if sol:

print(f"\n{n - 1} tied teams in {len(sol)} remaining matches {sol}")

break

Sunday Times Teaser 3004 – Going Up

by John Owen

Published Sunday April 19 2020 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta