Teaser 3146: Curling league
From The Sunday Times, 8th January 2023 [link] [link]
In our curling league (between 4 and 26 teams), each team plays each other once. Teams are ranked according to the number of wins (draws are impossible). If any teams are tied on wins, ranking is only possible if those teams have different numbers of wins in their mutual games. For example, in a three-way tie if A beats B, B beats C and A beats C, the ranking is ABC, but if C beats A (or A has not yet played C), then ranking is impossible, as A and B have one win each.
At one point (each team had played G games), ranking the teams as above was possible. However, if each team had played G-1 games, a ranking would have been impossible, irrespective of results. With one more team in the league, the minimum number of games needed to allow a ranking is G+2.
How many teams are in the league and what was the value of G?
Note: The setter of the puzzle is expecting a solution where the league has at least 5 and no more than 25 teams. (Which I would have phrased as “between 5 and 25 teams”).
See Teaser 3146: Curling league [revised] for a revised version of this puzzle.
[teaser3146]
Frits, and 
Brian Gladman are discussing. 
GeoffR, 
bencooperjamin, and 4 others are discussing. 
Hugh+Casement, and 
Robert Brown are discussing. 
Jim Olson are discussing. 
John Crabtree, 
Ellen Napier, 
Dilwyn Jones, and 1 other are discussing. 
Jim Randell 5:42 pm on 6 January 2023 Permalink |
I wrote a quick program to start attacking this puzzle starting with the smallest number of teams and working upwards, although I didn’t expect my program to run in a reasonable time as the number of teams grew.
However I found that a situation that satisfies the conditions described in the puzzle presented itself very quickly, which makes me wonder if I have missed something.
The following Python program runs in 57ms (it stops when the first solution is found). (Internal run time is 4.3ms).
from enigma import ( irange, group, item, div, subsets, multiset, cproduct, seq_all_different, cache, printf ) # labels for <n> teams; 1..n teams = lambda n: irange(1, n) # a match is represented by (<winning-team>, <losing-team>) # check a set of matches for <n> teams is orderable def orderable(n, ms): # extract the winners (ws, _) = zip(*ms) # and count the number of wins for each team w = dict((t, ws.count(t)) for t in teams(n)) # group teams with the same number of wins together g = group(w.items(), by=item(1), f=item(0), fn=sorted) # look for tied groups for (_, ts) in g.items(): if len(ts) < 2: continue # collect the mutual games amongst the group ws_ = list(x for (x, y) in ms if x in ts and y in ts) # and check they are all different if not seq_all_different(ws_.count(t) for t in ts): return False # looks good return True # choose <p>-subsets of potential matches <ps>, with <k> matches played per team def choose(n, ps, p, k): for ss in subsets(ps, size=p): m = multiset.from_seq(*ss) if all(m.count(t) == k for t in teams(n)): yield ss # find orderable sets of wins for <n> teams, each having played <k> matches def wins(n, k): # calculate the number of played matches p = div(n * k, 2) if p is None: return # construct the possible matches ps = list(subsets(teams(n), size=2)) # choose a p-subset with k matches played per team for ss in choose(n, ps, p, k): # now choose the winning team in each match for ms in cproduct([(x, y), (y, x)] for (x, y) in ss): # is this set of matches orderable? if orderable(n, ms): yield ms # check if <n> teams, each played <k> games is orderable @cache def check(n, k): if not (n > k > 0): return None for r in wins(n, k): printf("[n={n} k={k} -> {r}]") return True printf("[n={n} k={k} -> None]") return False # solve the puzzle def solve(): # n = number of teams in the league for n in irange(5, 27): # k = number of matches played by each team # look for minimum k that is orderable for k in irange(1, n - 1): # can we find an orderable set of wins? r = check(n, k) # find the smallest k that gives an orderable set if r: printf("-> n={n}: min_k = {k}") (T, G) = (n - 1, k - 2) # look to see if (T, G) is possible and (T, G - 1) is not possible if check(T, G) is True and check(T, G - 1) is False: # output solution printf("=> T = {T}; G = {G}") printf("##### SOLUTION FOUND -> league has {T} teams; games played = {G} #####") # we are done return break printf() solve()There are two solution to this puzzle:
Solution: There are either 4 teams in the league, and G = 2. Or there are 16 teams in the league and G = 6.
My program quickly finds the first of these solutions, but would take a long time to find the second one (and to exhaustively check the entire solution space).
But the program I wrote for the revised puzzle [link] does find both solutions in a reasonable time.
Here is a description of the solution with 4 teams:
It is possible for each of the 4 teams (A, B, C, D) to have played 2 games. For example:
And we see the teams are ranked:
It is not possible to rank the teams if they have only played one game. As there will only have been 2 games played, involving all 4 teams. 2 of the teams will have 1 win (and cannot be ranked, as they have not played each other), and the other will have 0 wins (likewise).
If there were 5 teams in the league (A, B, C, D, E) then it is not possible for each of the teams to have played an odd number of games (as each game requires 2 teams), but it is possible for each team to play 4 games, for example:
The teams are ranked:
All that remains is to show that it is not possible to find a set of matches with 2 wins per team, and the program can do this for us:
LikeLike
Frits 12:35 pm on 7 January 2023 Permalink |
@Jim, nice solution. It is not easy to solve this week.
How can you be sure this is the only solution? So you might give an incorrect answer (for “our curling league”).
One thing I can deduce is that if k = n-1 then we can always find an orderable set of wins.
LikeLike
Jim Randell 12:44 pm on 7 January 2023 Permalink |
My program gets bogged down as n increases, so it just stops at the first viable solution, and I haven’t been able to check all values up to n = 26.
There may be an analytical way to show that there is only a single solution. Although if there are multiple solutions we won’t be able to tell which of them the setter had in mind.
LikeLike
Jim Randell 11:32 am on 9 January 2023 Permalink |
I’ve put a more efficient (but more complex) version of my program up on the page for the revised version of this puzzle [link].
And we see that the original formulation of the puzzle has 2 solutions.
LikeLike
Jim Randell 10:26 am on 8 January 2023 Permalink |
Apparently the setter of this puzzle is expecting a solution for this puzzle with the number of teams in the league in the interval [5..25]. If this is the case, I think the wording should have been chosen more carefully.
LikeLike
Brian Gladman 2:48 pm on 7 January 2023 Permalink |
Congratulations on getting a solution for this one Jim. At the moment I don’t have one 😦
LikeLike
Brian Gladman 10:50 am on 8 January 2023 Permalink |
John Owen has just clarified on the Sunday Times discussion group site that “between 4 and 26” means “5 or more and at most 25”.
LikeLike
Jim Randell 2:49 pm on 8 January 2023 Permalink |
@Brian: This change certainly makes things trickier, as my program gets bogged down before it can check leagues with 10 or more teams.
Although I would have expected this condition to be expressed as “between 5 and 25 teams”.
LikeLike
Frits 4:14 pm on 8 January 2023 Permalink |
Nice to encounter a teaser which doesn’t seem to get solved (within a reasonable time) by brute force. My adapted version (with recursion) of Jim’s program is getting too slow at n=10.
It isn’t easy to find a way to simplify the problem so it can be solved.
LikeLike