Recent Comments
 | Jim Randell on Enigma 1105: Road ants |
 | geoffrounce on Enigma 35: Digits all wro… |
 | hakank on Puzzle 70: Football five teams… |
 | saracogluahmet on Enigma 1740: Sudoprime |
| Jim Randell on Enigma 406: The ritual |
Enigmatic Code
Programming Enigma Puzzles
Enigma 1209: The league game
Posted by on 19 August 2015
From New Scientist #2365, 19th October 2002 [link]
Lloyd and Owen have a new game. They imagine there is a football league with four teams, A, B, C and D. Each team plays every other team once, scoring 1 point for a draw and 2 for a win. The teams are ordered in their league by points and, where there are equal points, by goal difference.
At the start of their game, Lloyd has six cards in his hand, each with a different match on it, A v B, A v C, etc. The game consists of six rounds, numbered 1 to 6 in order. In each round Lloyd chooses one of the cards in his hand and lays it on the table. Owen writes a score on it, for example if the card was A v B, he might write A2 v B1. They then work out the league table for the matches played so far and see who is top. They also work out if it is certain that the team will be top after all the six matches have been played, whatever the scores of the remaining matches. If it is certain and it was not certain in the previous round then that round is called the “Decisive” round. That completes the round.
Lloyd plays so as to make the Decisive round as late as possible and Owen aims to make it as early as possible.
Question 1: If they both play as well as possible, what is the number of the Decisive round?
Question 2: If they change the rules so that a team gets 3 points for a win, what then is the number of the Decisive round?
[enigma1209]
Advertisements
I didn’t particularly like this puzzle. I’m not usually a fan of the “football league table”-type puzzle, and I found this one quite a tricky one to write a program for, and while it looks OK I’m not completely confident in it.
This Python program examines the possible game play. It runs in 5.6s. The number of points for a win can be specified on the command line (default = 2).
from enigma import Football, chunk, diff, printf # points for a win (2 or 3) import sys W = (2 if len(sys.argv) < 2 else int(sys.argv[1])) printf("[win = {W} points]") # scoring regime football = Football(points={ 'w': W, 'd': 1 }) # teams and matches teams = 'ABCD' matches = ('AB', 'AC', 'AD', 'BC', 'BD', 'CD') # number of matches each team plays P = len(teams) - 1 # marker for indecisive tournaments X = len(matches) + 1 # construct the table for a sequence def table(s): t = list() # dictionary of matches d = dict(chunk(s, 2)) # compute tables for x in teams: ms = tuple(k for k in d.keys() if x in k) t.append(football.table(tuple(d[k] for k in ms), tuple(k.index(x) for k in ms))) # sort it t.sort(key=lambda x: (x.points, x.w, x.d, x.l), reverse=True) return t # is the sequence decisive def is_decisive(s): t = table(s) # is there a leader? v = t[0].points vs = tuple(x for x in t if x.points == v) if len(vs) > 1: # if there are no wins we can't choose on goal difference if all(x.w == 0 for x in vs): return False # can anyone catch up with the leader? return all(x.points + W * (P - x.played) < v for x in t[1:]) # play the game # return the number of the decisive round def play(s, ms): (n, r) = divmod(len(s), 2) if r == 0: # is this round decisive? if is_decisive(s): return n # are there any matches left? if not ms: return X # player 1: choose a match # try to make the decisive round as late as possible return max(play(s + [x], diff(ms, [x])) for x in ms) else: # player 2: choose an outcome for the match # try to make the decisive round as early as possible return min(play(s + [x], ms) for x in 'wdl') # play the game, starting with the first match n = play(list(matches[:1]), list(matches[1:])) printf("decisive round = {n}")Solution: Q1. With 2 points for a win the decisive round is round 6; Q2. With 3 points for a win the decisive round is round 5.