Teaser 3104: Prime football
From The Sunday Times, 20th March 2022 [link] [link]
There are more than 13 clubs in the Prime Football League, and each club plays each other twice during the football season, gaining three points for winning a match, and one point for a draw.
At the end of last season, it was observed that the final numbers of points gained by the clubs were all different double-digit prime numbers. During the season our local club, Wessex Wanderers, won just three times as many matches as they lost. If you knew how many clubs were in the league, you could work out the final points total of Wessex Wanderers.
How many clubs are in the league, and what was the final points total of Wessex Wanderers?
[teaser3104]
Alex T Sutherland and 
GeoffR, 
Hugh+Casement, and 
Tony Brooke-Taylor and 
Brian Gladman, 
Frits, and 
S2T2 
Jim Randell 5:55 pm on 18 March 2022 Permalink |
We know there are more than 13 teams in the league, and there are only 21 primes between 10 and 99, so this puts an upper limit on the number of teams in the league.
If there are n teams in the league, and each team plays every other team twice during a season, then there are a total of 2 × C(n, 2) matches during the season. And each team plays 2(n − 1) matches.
So we can consider the number of draws d played by WW. The remaining matches must be 3/4 wins and 1/4 losses. So we can calculate p = WW’s points at the end of the season, and this must be a 2-digit prime number.
We can then look to see if there is a scenario where the teams can all score a different 2-digit prime number of points, and if there is a way for this to occur then we have a viable (n, p) pair. (The program only checks that there is an n-subset of the primes, that includes p, and sums to a potentially viable total number of points awarded during the season. But it turns out this step doesn’t weed out any candidate solutions anyway, so a simpler program would find the same answer).
This Python program looks for viable (n, p) pairs, and looks for solutions where if we knew n there is a unique value for p. It runs in 94ms.
Run: [ @replit ]
from enigma import (primes, irange, C, subsets, div, Record, filter_unique, printf) # 2-digit primes prms = set(primes.between(10, 99)) # find a viable scenario def scenario(r): (n, w, d, l, p) = (r.n, r.w, r.d, r.l, r.p) # m = total number of number of matches m = 2 * C(n, 2) # consider possible total number of draws in all matches for td in irange(d, m - w - l): # calculate the total number of points awarded tp = 2 * td + 3 * (m - td) # can tp be made from an n-subset of primes (that includes p)? for ps in subsets(prms, size=n): if p in ps and sum(ps) == tp: # then this is a viable scenario printf("[n={n}; l={l} w={w} d={d}; p={p} -> ps={ps}]") yield ps # generate viable scenarios def generate(): # consider n = number of teams in the league for n in irange(14, len(prms)): # WW plays 2(n - 1) matches # if there are d draws, then the remaining matches are (3/4) win and (1/4) lost t = 2 * (n - 1) for l in irange(0, t // 4): w = 3 * l d = t - l - w # and calculate the points (a 2-digit prime) p = 3 * w + d if p not in prms: continue # is there a viable scenario? r = Record(n=n, w=w, d=d, l=l, p=p) for ps in scenario(r): yield Record.update(r, ps=ps) break # find solutions if we know n we can work out p for r in filter_unique(generate(), (lambda r: r.n), (lambda r: r.p)).unique: printf("n={r.n} p={r.p}")Solution: There are 18 clubs in the league. The final points total for Wessex Wanderers was 59.
We find there are the following potential (n, p) pairs (grouped by n):
If each of these situations is viable then the answer is n=18, p=59, as this is the only one where knowing n gives a unique p value.
And we can show that the n =18, p=59 situation is viable as follows:
With 18 teams there are 2×C(18, 2) = 306 matches.
One situation that gives each team a different 2-digit prime number of points is:
This verifies that n =18, p=59 is indeed a solution to the puzzle.
Although to show that it is the only solution would require showing that there are at least 2 viable (n, p) values for n = 14, 15, 17, 19, 20.
I think this would be quite tedious to do by hand. But the program below verifies each of the potential situations given is viable, which means that n = 18 is the only solution.
LikeLike
Jim Randell 11:38 am on 20 March 2022 Permalink |
Here is a variation on the program above. It looks for a viable collection of matches that produces the required points for WW, and different prime numbers of points for each of the other teams.
It uses a MiniZinc model (highlighted below) to look for viable scenarios, and it does take a while to check all possible (n, w, l, p) values, but it turns out each of them is viable, so a shorter program which doesn’t check for viability will produce the correct result.
from enigma import (primes, irange, C, subsets, div, Record, filter_unique, update, sprintf, join, peek, printf) from minizinc import MiniZinc # 2-digit primes prms = set(primes.between(10, 99)) # check for a viable scenario (using MiniZinc) # the model model = """ include "globals.mzn"; % 2-digit primes set of int: primes = {prms}; % number of teams int: n = {n}; % decision table: x[i, j] = number of matches won by team i against team j array [1..n, 1..n] of var 0..2: x; constraint forall (i in 1..n) (x[i, i] = 0); constraint forall (i, j in 1..n where i < j) (x[i, j] + x[j, i] < 3); % calculate points for a team function var int: wins(var int: i) = sum (j in 1..n) (x[i, j]); function var int: loss(var int: i) = sum (j in 1..n) (x[j, i]); function var int: points(var int: i) = 2 * (n - 1 + wins(i)) - loss(i); % points for each team array [1..n] of var 10..99: pts; constraint forall (i in 1..n) (pts[i] = points(i) /\ pts[i] in primes); constraint all_different(pts); % specific constraints for team 1 constraint pts[1] = {p} /\ wins(1) = {w} /\ loss(1) = {l}; solve satisfy; """ # default environment env = dict(primes=join(prms, sep=", ", enc="{}")) # check for a viable scenario def scenario(r): vs = update(env, Record.map(r).items()) # create the model m = MiniZinc(sprintf(model, **vs), solver="minizinc --solver cbc") # is there a solution to the model? return peek(m.solve(), default=None) # generate viable scenarios def generate(): # consider n = number of teams in the league for n in irange(14, len(prms)): # WW plays 2(n - 1) matches # if there are d draws, then the remaining matches are (3/4) win and (1/4) lost t = 2 * (n - 1) for l in irange(0, t // 4): w = 3 * l d = t - l - w # and calculate the points (a 2-digit prime) p = 3 * w + d if p not in prms: continue # check for a viable scenario r = Record(n=n, w=w, d=d, l=l, p=p) if scenario(r): printf("[n={n}; d={d} w={w} l={l} p={p}]") yield r # find solutions if we know n we can work out p for r in filter_unique(generate(), (lambda r: r.n), (lambda r: r.p)).unique: printf("n={r.n} p={r.p} [{r}]")I found the
mzn-g12mipsolver andcbcsolver gave run times of around 25s.LikeLike
Alex T Sutherland 3:39 pm on 21 March 2022 Permalink |
Number_of_ Teams = [14:21] ; Teams_Count = [0]; Do for each Number_ of_ Teams Calculate Number_of_ games_ played = g Do for each Number_of_Losses [0 : g ] This range can be shortened Wins= 3*Losses Draws = g - Wins -Losses if Draws < 0 continue to next Loss Points = a*Losses + b*g a & b can easily be derived if Points are in prime range (11 :97] ; if not continue to next Loss Record the data Increment the count for this team number end endFrom the record obtain the data for team number who has a count = 1
My answer has (number of teams + their number of losses ) = prime number.
Run time :- varies between 2 and 6 ms.
LikeLike