Teaser 2721: Milliner’s hat-trick
From The Sunday Times, 16th November 2014 [link] [link]
A football tournament has four groups each of four teams, with the teams in the same group playing each other once. So far the teams have each played two games and in each group the distribution of points is different. Also, in each group just one pair of teams are level on points and their positions have been determined by their “goals scored”. Milliner has scored four (including a hat-trick), Orlando two, and nine other players have scored one goal each. Despite his success, Orlando’s team is not the top of their group.
What are the results of the two games that Milliner’s team have played? And the two games that Orlando’s team have played?
[teaser2721]
S2T2 
Jim Randell 6:33 am on 19 July 2022 Permalink |
The puzzle is not explicit on the scoring system used (i.e. 2 points for a win, or 3 points for a win), although it turns out it doesn’t matter which is used, the answer to the puzzle is the same in both cases.
In each group each team has played 2 of their 3 matches. So there have been 4 matches played (and there are 2 matches left to play). So among the 4 groups there have been 16 matches played in total.
The minimum possible number of goals scored among the 4 matches in a group is 2. So the maximum possible number of goals scored is 15 − 3×2 = 9. (Although it may be possible to reduce this theoretical maximum value, which would speed up the program).
For each group, this Python program considers the scores for teams A (1st), B (2nd), C (3rd), D (4th), such that each team has played 2 matches, and two of the teams are tied on points, but have different “goals for” values.
It then chooses 4 different points distributions (one for each of the groups), and from the previously examined scores it chooses 4 sets of scores that have 15 goals scored in total, and ensures there are possible teams for both Milliner and Orlando.
The program runs in 361ms.
Run: [ @replit ]
from collections import defaultdict from enigma import ( Football, irange, subsets, tuples, cproduct, peek, delete, update, find, unzip, reverse, map2str, join, printf ) # scoring regime (2 or 3 points for a win) football = Football(games='wdlx', points=dict(w=2, d=1)) # labels for the teams teams = (A, B, C, D) = tuple("ABCD") # keys for the matches ks = list(x + y for (x, y) in subsets(teams, size=2)) # allocate <t> goals among the matches <ms>, return scores <ss> def allocate(t, ms, ss=dict()): # are we done? if not ms: if t == 0: yield ss else: # calculate the number of surplus goals n = t - sum(v == 'w' for v in ms.values()) if n < 0: return # choose the next match to allocate goals to (k, v) = peek(ms.items()) if v == 'x': # not played yield from allocate(t, delete(ms, [k]), update(ss, [(k, None)])) elif v == 'w' or v == 'l': # a win (or loss), calculate scores (x, y) for x in irange(1, n + 1): for y in irange(0, min(x - 1, n - x + 1)): s = ((x, y) if v == 'w' else (y, x)) yield from allocate(t - x - y, delete(ms, [k]), update(ss, [(k, s)])) elif v == 'd': # a draw, calculate scores (x, x) for x in irange(0, n // 2): yield from allocate(t - x - x, delete(ms, [k]), update(ss, [(k, (x, x))])) # check goals scored by team <t> in a match from scores <ss> is <n> or more def scored(t, ss, n): for (k, v) in ss.items(): if v is not None: i = find(k, t) if i != -1 and v[i] >= n: return True # map: <pts> -> <total goals> -> (<match scores>, <milliner>, <orlando>) values d = defaultdict(lambda: defaultdict(list)) # consider possible match outcomes for ms in football.games(repeat=len(ks)): ms = dict(zip(ks, ms)) # compute the table for each team table = dict((t, football.extract_table(ms, t)) for t in teams) # each team has played twice if not all(table[t].played == 2 for t in teams): continue # points are increasing, with exactly 2 teams having the same points pts = tuple(table[t].points for t in teams) if len(set(pts)) != 3: continue if not all(x >= y for (x, y) in tuples(pts, 2)): continue # allocate goals to the matches for t in irange(2, 9): for ss in allocate(t, ms): # extract the goals (for, against) for each team goals = dict((t, football.extract_goals(ss, t)) for t in teams) # check teams with same points have different "goals for" values if any(p1 == p2 and not (goals[t1][0] > goals[t2][0]) for ((t1, p1), (t2, p2)) in tuples(zip(teams, pts), 2) ): continue # find teams for Milliner: team must have a match with >= 3 goals scored # and have >= 4 goals scored in total tM = list(t for (t, (f, _)) in goals.items() if f > 3 and scored(t, ss, 3)) # find teams for Orlando: must have >= 2 goals, and not be top tO = list(t for (t, (f, _)) in goals.items() if t != 'A' and f > 1) # record this set of scores d[pts][t].append((ss, tM, tO)) # collect scores from <ss> for teams in <ts> (from the team's perspective) def collect(ss, ts): for t in ts: rs = list() for (s, f) in unzip(football.extract(ss, t)): if s is None: continue rs.append(reverse(s) if f else s) yield tuple(sorted(rs, reverse=1)) # choose 4 different points distributions for ps in subsets(d.keys(), size=4): # choose the number of goals scored in each group for ts in cproduct(d[p].keys() for p in ps): # there should be 15 goals in total if sum(ts) != 15: continue # choose the actual scores in each match for ss in cproduct(d[p][t] for (p, t) in zip(ps, ts)): # check for possibilities for Milliner and Orlando if not any(tM for (_, tM, _) in ss): continue if not any(tO for (_, _, tO) in ss): continue # output a solution (groups = scores, pts, M, O; M's team; O's team) (Ms, Os) = (set(), set()) for (i, ((s, tM, tO), p)) in enumerate(zip(ss, ps), start=1): printf("Group {i}: {s} {p} {tM} {tO}", s=map2str(s, enc=""), tM=join(tM, enc="[]"), tO=join(tO, enc="[]")) Ms.update(collect(s, tM)) Os.update(collect(s, tO)) for M in sorted(Ms): printf("M's team: {M}", M=join(M, sep=", ")) for O in sorted(Os): printf("O's team: {O}", O=join(O, sep=", ")) printf()Solution: The results for Milliner’s team are: a 3-1 win, a 1-0 win. The results for Orlando’s team are: a 2-0 win, a 0-1 loss.
M’s team is a group leader. O’s team is second in their group.
With “2 points for a win” (and 1 for a draw) there are three possible sets of scores:
We can examine what happens with “3 points for a win” by changing the initialisation at line 8. And we find in this case there are four possible sets of scores:
LikeLike