## Teaser 3146: Curling league [revised]

**From The Sunday Times, 8th January 2023** [link] [link]

The number of teams in our curling league is more than 4, but less than 26. In a tournament each team plays each of the other teams once, and the teams are ranked according to the number of wins they achieve (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 (when 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 not have been possible, irrespective of results. With one more team in the league, the minimum number of games needed to allow a ranking would be G+2.

How many teams are in the league and what was the value of G?

This is a revised version of the puzzle posted as **Teaser 3146**. The underlined text has been changed from the published version, to be in line with the intention of the setter.

[teaser3146]

## Jim Randell 9:41 am

on9 January 2023 Permalink |I solved the previous version of this puzzle with a fairly straightforward search [link]. And it came up with a solution quickly, without having to explore the entire solution space. Which was handy because that would have taken a long time.

So I looked at making my program more efficient. By looking at the number of wins achieved by each team we find there are only certain patterns of wins that are viable. Limiting the search to these patterns of wins, and doing more checks to reject candidate solutions early I was able to come up with a (more complicated) program that explores the entire solution space in a reasonable time, and constructively finds a single solution to the puzzle.

(This program can also be used to find both solutions to the puzzle as originally worded).

The following Python program runs in 7.6s.

Solution:There are 16 teams in the league. G = 6.For example, with teams A – P, each can play 6 games, and be orderable as follows:

And it is not possible for 16 teams to have each played 5 games and be orderable.

But it is possible for 17 teams, A – Q, to have each played 8 games and be orderable:

but not for any number of games less than 8.

Here are some notes on the refinements I used to eliminate cases from testing compared with my original program, that allows it to run in a reasonable time over the entire solution space…

Firstly we don’t care what order the teams are in, so we can assume team 1 is 1st in the order, team 2 is 2nd, and so on.

For a league with

nteams, each having playedkmatches there arep = (n × k /2)matches played in total (each match involves 2 teams), so we can allocate thesepwins among thenteams in a non-decreasing sequence of[0..k]wins. With team 1 having the largest number of wins, down to teamnhaving the least wins.Then looking at groups of teams with the same number of wins, these groups must be ordered according to the matches played amongst the teams involved. If team

Xhas 0 wins there cannot be another teamYwith 0 wins, as we can only order them with anXvs.Ymatch, which neither team can be allowed to win. So there can be at most 1 team with 0 wins, at most 2 teams with 1 wins, etc.And by considering losses we get the same pattern coming down. There can be at most 1 team with

kwins, at most 2 teams with(k – 1)wins, and so on.So, I generated viable patterns of wins and then allocated matches according to these patterns by working through the list of wins and allocating appropriate matches for each team.

When allocating the remaining matches for each team I check after each allocation that we haven’t allocated too many wins (or losses) to one of the later occurring teams, and also after we have allocated the matches for a team the matches for that team and all earlier teams are fixed, so the set of matches restricted to just these teams must already be orderable (as they are not going to change later).

Also, it soon became obvious that using [[

`enigma.decompose()`

]] to generate all possible decompositions and discarding those that were unsuitable was not very efficient asnincreased, so I wrote a specific [[`decompose()`

]] routine to do this for me.Then I realised that if we have groups of teams with the same number of wins, and we know the order that we want them to appear in, then we can allocate the wins involved between those teams immediately, before we start the general allocation of the remaining matches.

Together all these improvements let the program run in 10s or less (running under

PyPy 7.3.11). This was hugely faster than my initial program for the original puzzle, and let the program examine the entire solution space, and construct orderings where they were possible.LikeLike

## Frits 4:41 pm

on9 January 2023 Permalink |Using a different solve() is a bit faster. Basically we start with making a list of orderable set of wins (first item only) by calling decompose().

Only changes made to the code is to return a tuple in decompose() and to suppress printing in the check routine.

The “not found” branche is not further developed as it seems that all decompose() output is orderable.

LikeLike

## Jim Randell 9:46 pm

on9 January 2023 Permalink |@Frits: I think most of the speed increase you are seeing comes from not checking the full range for

n. If the number of teams can be up to 25 then we need to check up ton= 26. Otherwise it seems to be doing pretty much the same thing as my program, but finding solutions at the end rather than as it goes along.The values generated by [[

`decompose()`

]] all give an orderable set of matches when the program is run normally, but this is not the case in general. While playing around I found [[`check(10, 8)`

]] (for example) needed to look at multiple decompositions before an orderable set was found.LikeLike

## Frits 11:21 pm

on9 January 2023 Permalink |@Jim, you are right, with range(start, stop + 2) the performance gain is minimal.

A bit surprising, your program calls check() 135 times and mine only 23 times (but these are all time consuming).

LikeLike

## Jim Randell 11:28 pm

on9 January 2023 Permalink |The [[

`check()`

]] function is cached (via the [[`@cache`

]] decorator), so we get access to previously computed values without recalculating them.LikeLike

## Frits 11:34 pm

on9 January 2023 Permalink |Removing @cache most of the time slightly improves the run time!

LikeLike

## Jim Randell 9:36 am

on27 January 2023 Permalink |Here is a non-constructive solution, that uses the pattern of wins given in my notes above.

Thinking about leagues of

nteams where each team has playedkmatches, then if we start with a value forkwe see the smallest possible value thatncan be is(k + 1).And when we think about allocating the

p = (n.k / 2)matches among thenteams, then there can only be 1 team with 0 wins orkwins, 2 teams with 1 win or(k − 1)wins, etc.So, if

kis even (say2x) we get a pattern of the form:And if

kis odd (say2x + 1) we get a pattern of the form:So by considering increasing values of

kwe can find a range of potentially viablenvalues and build up a set of viable(n, k)values. Note that no(n, k)value where bothnandkare odd is viable, as a correspondingpvalue cannot be calculated, but we assume that all remaining(n, k)valuewillallow a viable ordering to be constructed. (In my program above this assumption is not made, and we don’t accept an(n, k)until an orderable scenario has been constructed. Removing this requirement significantly reduces the amount of work required to find a solution, and is the approach used in the setters’ own solution).Once an appropriate set of

(n, k)values has been constructed we can look for scenarios that provide a solution to the puzzle.We are looking for a number of teams

Tand number of gamesGsuch that:The Python program performs this search. It runs in 57ms. (Internal runtime is 534µs).

Run:[ @replit ]LikeLike