Teaser 3199: County cup
From The Sunday Times, 14th January 2024 [link] [link]
In our county football competition, fewer than 100 teams compete in two stages. First, the teams are allocated to more than two equally-sized groups, and in each group there is one match between each pair of teams. The top two teams in each group proceed to the first round of the knockout stage, where a single match between two teams eliminates one of them. If the number of teams entering the knockout stage is not a power of 2, sufficiently many teams are given byes (they don’t have to play in the first round), so that the number of teams in the second round is a power of 2. The knockout stage continues until only one team remains. In one year the competition was played with a single match on every day of the year.
How many teams were in the competition that year?
[teaser3199]
Guy, 
Brian Gladman, and 2 others are discussing. 
S2T2 
Jim Randell 5:40 pm on 12 January 2024 Permalink |
(See also: Teaser 2965, Enigma 1067, Enigma 1169, Enigma 1276, Enigma 176, Enigma 1398).
This Python program runs in 57ms. (Internal runtime is 229µs).
from enigma import (irange, C, printf) # consider number of groups in stage 1 for k in irange(3, 33): # consider number of teams per group for g in irange(3, 99 // k): # number of matches in stage 1 (in each group each pair plays) m1 = k * C(g, 2) # stage 2: the top 2 teams from each group progress to knockout q = 2 * k # number of matches in stage 2 (1 team is eliminated in each match) m2 = q - 1 # total number of matches in the tournament t = m1 + m2 if t in {365, 366}: printf("[{n} teams]", n=k * g) printf("stage 1: {k} groups of {g} teams = {m1} matches") printf("stage 2: {q} teams = {m2} matches") printf("total = {t} matches") printf()Solution: There were 48 teams in the tournament.
Stage 1 consisted of 3 groups, each with 16 teams. In each group there were 120 matches. So stage 1 consisted of 360 matches.
Stage 2 consisted of 6 teams (the top 2 teams from each of the 3 groups), so 5 matches were played to find the winner of the tournament. (2 matches in the first round, leaving 4 teams in the second round. 2 matches in the second round (semi-finals), leaving 2 teams to play in the final match).
In total there were 365 matches.
If there was an additional match for 3rd/4th place in the tournament there would be 1 extra match, which would bring the total to 366, but this could be played one match per day in a leap year, so the answer remains the same.
With a bit of analysis:
If M is the total number of matches, we get:
And in this case we are looking for solutions where M = 365 or 366.
So k is a divisor of 732 or 734 (k ≥ 3), and the remainder is g(g − 1) + 4 (which has a minimum value of 10).
The only options are:
And only one of these gives a viable g value.
from enigma import (divisors_pairs, quadratic, printf) # look for total number of matches = M def solve(M): # consider possible k values for (k, x) in divisors_pairs(2 * (M + 1), every=1): if k < 3 or x < 10: continue # look for possible g values for g in quadratic(1, -1, 4 - x, domain='Z', include='+'): if g < 3: continue printf("M={M}: k={k} g={g} -> n={n}", n=k * g) # consider possible total numbers of matches solve(365) solve(366)LikeLike
Frits 7:29 pm on 12 January 2024 Permalink |
# next higher power (<= 128) nhp = lambda n: [x for x in [2 ** i for i in range(1, 8)] if x >= n][0] # we have a least 3 groups of at least 2 players for n in range(6, 100): # the teams are allocated to more than two equally-sized groups divpairs = {(i, n // i) for i in range(2, int(n**.5) + 1) if n % i == 0} # for divisor pair (a, b) add pair (b, a) divpairs |= {(d2, d1) for d1, d2 in divpairs} divpairs = [(d1, d2) for d1, d2 in divpairs if d1 > 2] for ngrps, grpsz in divpairs: # number of games in stage 1 = ngrps * (grpsz * (grpsz - 1) // 2) # number of byes = next higher power - 2 * ngrps # tot = number of games in stage 1 plus (next power - 1 - number of byes) if ngrps * (grpsz * (grpsz - 1) // 2 + 2) - 1 in {365, 366}: print(f"answer: {n} teams")LikeLike
Brian Gladman 10:32 pm on 12 January 2024 Permalink |
I am not getting a solution (here) because I constrain the number of teams in round two to be a power of two by adding byes. Am I misreading the need for this constraint?
LikeLike
Brian Gladman 1:21 am on 13 January 2024 Permalink |
I did misinterpret this.
LikeLike
Jim Randell 9:50 am on 13 January 2024 Permalink |
Although byes are used in the first round of stage 2 (the knockout stage), you don’t need to worry about them. In a knockout tournament each match eliminates 1 team, so starting with n teams you get down to 1 team after (n − 1) matches. (And if there is a match to determine 3rd/4th place there will be n matches in total).
LikeLike
Brian Gladman 10:18 am on 13 January 2024 Permalink |
Thanks Jim, I did eventually figure out how it works. Thanks for correcting my link (but it is not very useful now since I have changed my code).
LikeLike
Guy 11:04 am on 15 January 2024 Permalink |
Unfortunately, unlike Brian, I’m still confused.
I think you have an unusual knockout tournament when there is not a power of 2 (eg 6) number of teams. With 6 teams in the Knockout Stage, the two teams in the final game will have played a different number of games in the Knockout Stage.
The question appears to require that the Knockout Stage must have a power of 2 number of teams. So the number of groups determines the number of Stage One byes required. With 48 teams and 3 groups, you would get 6 teams (2 per Stage One group) through the Stage One route and need additional 2 byes to make up to 8 (next Power of 2) teams for the Knockout Stage. The teams with byes don’t play a game in Stage One. Hence the adjusted, now unequal, Stage One groups would be either 15,15,16 or 14,16,16. Total games would then be 337 (330+7) or 338 (331+7).
LikeLike
Jim Randell 1:41 pm on 15 January 2024 Permalink |
Here’s an example of how the tournament would work with 10 groups in stage 1 (so there would be 30, 40, 50, …, 90 teams in total).
2 teams from each group proceed to stage 2 (the knockout stage), so there are 20 teams entering stage 2.
But 20 is not a power of 2, so in the first round (of stage 2) we play pairs of teams against each other until the number of teams remaining is a power of 2.
So in the example, 2 teams play, 1 is eliminated and 1 goes through to the second round (of stage 2), and there are 19 teams left in the tournament. This still isn’t a power of two, so another 2 teams play, 1 is eliminated and 1 goes through to the second round. And there are 18 teams left. Another 2 play, and there are 17 teams left. Another 2 play and there are 16 teams left, which is a power of 2.
So, after 4 matches in round 1 of the knockout stage there are 16 teams remaining. The 12 teams that are still in round 1 are all given byes to round 2, and so there are 16 teams in round 2, so we have 8 matches in round 2, the winners go through to round 3, so there are 4 matches in round 3, 2 matches in round 4, and 1 (the final) match in round 5.
The total number of matches in the knockout stage was: 4 + 8 + 4 + 2 + 1 = 19.
But the simpler way to look at it is that one team is eliminated from the tournament with each knockout match, and we start with 20 teams, so after 19 matches there is only 1 team remaining (the winner).
LikeLike
Guy 2:14 pm on 15 January 2024 Permalink |
OK, finally got it, thank you! Re-reading the question, the first round in “(they don’t have to play in the first round)” refers to first round of Knockout Stage, not the Group Stage. Following you help, it’s annoyingly obvious now.
[The alternative problem with byes in Group Stage was still fun. Would have 99 teams split into 11 groups, you need to give 10 byes, so a possible arrangement for the 11 groups could be (3, 6, 8, 9, 9, 9, 9, 9, 9, 9, 9). The knockout stage then begins with 32 teams (11×2 from Group Stage plus the 10 byes).]
LikeLike