Brainteaser 1839: It’s a knockout
From The Sunday Times, 14th December 1997 [link]
Sixteen teams, A-P, entered a knockout football competition. In none of the matches did any team score more than five goals, no two matches had the same score, and extra time ensured that there were no draws.
The table shows the total goals, for and against, for each team:
My own team, K, was knocked out by the team who were the eventual champions.
Who played whom in the semi-finals, and what were the scores.
This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.
[teaser1839]
Frits are discussing. 
John Crabtree and 
S2T2 
Jim Randell 11:44 am on 11 August 2020 Permalink |
When we look at the table we can spot teams that might have been knocked out in the first round. The number of goals for and against must be different (no draws) and neither must be more than 5. We can then choose 8 such teams, and their values in the table give the scores in the matches. We then choose 8 of the remaining teams to be their opponents and see if we can construct a new table for the next round of the tournament (which will have half as many matches). And so on until we reach the last 2 teams.
This Python 3 program runs in 1.2s.
Run: [ @repl.it ]
from enigma import subsets, diff, ordered, flatten, join, printf # the total goals scored/conceded gs0 = dict( A=(5, 6), B=(14, 0), C=(15, 8), D=(2, 4), E=(1, 3), F=(0, 5), G=(4, 6), H=(1, 4), I=(1, 2), J=(12, 12), K=(6, 5), L=(0, 1), M=(4, 5), N=(1, 5), O=(2, 3), P=(7, 6), ) # do the list of <ls>, <ws> make a set of matches using goals scored/conceded in <gs>? # return list of (<winner> + <loser>, (<scored>, <conceded>)) # and a new version of <gs> for the next round def matches(gs, ls, ws): ms = list() d = dict() for (w, l) in zip(ws, ls): ((fw, aw), (fl, al)) = (gs[w], gs[l]) (f, a) = (fw - al, aw - fl) if f < 0 or a < 0: return (None, None) ms.append((w + l, (al, fl))) d[w] = (f, a) return (ms, d) # allowable score: # no side scores more than 5 goals, and no draws score = lambda x, y: not(x > 5 or y > 5 or x == y) # play out a tournament # k = number of matches in this round # gs = total number of goals scored in the remaining rounds # ms = match outcomes in each round # ss = scores used so far def tournament(k, gs, ms=list(), ss=set()): # how many matches? if k == 1: # there should be 2 teams (x, y) = gs.keys() ((fx, ax), (fy, ay)) = (gs[x], gs[y]) if fx == ay and ax == fy and score(fx, ax): yield ms + [[(x + y, (fx, ax)) if fx > ax else (y + x, (fy, ay))]] else: # teams that can be knocked out in this round teams = list(k for (k, (f, a)) in gs.items() if score(f, a)) # choose the losers for ls in subsets(teams, size=k): # choose the winners from the remaining teams for ws in subsets(diff(gs.keys(), ls), size=k, select="P"): (ms_, gs_) = matches(gs, ls, ws) if not gs_: continue ss_ = set(ordered(*xs) for (ts, xs) in ms_) if ss_.intersection(ss): continue yield from tournament(k // 2, gs_, ms + [ms_], ss.union(ss_)) # there are 8 matches in the first round for ms in tournament(8, gs0): # check K is knocked out by the champions champ = ms[-1][0][0][0] if not(champ + 'K' in (ts for (ts, xs) in flatten(ms))): continue # output the tournament for (i, vs) in enumerate(ms, start=1): printf("Round {i}: {vs}", vs=join((f"{t[0]}v{t[1]} = {x}-{y}" for (t, (x, y)) in sorted(vs)), sep="; ")) printf()Solution: The semi-finals were: B vs K = 3-0; C vs J = 5-3.
So the final was: B vs C = 2-0, and B were the champions.
The strategy given above finds two possible tournaments, but only in one of them is K knocked out by the eventual champions.
LikeLike
Frits 8:13 pm on 18 August 2020 Permalink |
@Jim
Did you also solve the puzzle manually?
It is not so difficult to determine who is playing whom in the semi-finals.
The scores are not easy to determine.
LikeLike
Jim Randell 12:00 pm on 19 August 2020 Permalink |
@Frits: I didn’t do a manual solution for this one. But I imagine the fact there are only 15 possible scores for the 15 games must make things a bit easier. (This is something I didn’t use in my program).
LikeLike