## Teaser 2965: Knock, knock!

**From The Sunday Times, 21st July 2019** [link]

Last year a two-figure number of teams entered our football competition. With that number, it was impossible to have a straightforward knockout competition (where half the teams are knocked out in each round), so we divided the teams into equal-sized groups, each pair of teams within a group played each other once, and the overall winner from each group went forward to the second stage consisting of a knockout competition. Unfortunately our local team was knocked out in the quarter-finals of that stage.

This year a higher number of teams entered (but not twice as many). Again a straightforward knockout competition was impossible so we copied last year’s model but with smaller groups and more of them. By coincidence the total number of games played this year equalled the number played last year.

How many teams entered last year and how many this year?

[teaser2965]

## Jim Randell 7:01 pm

on19 July 2019 Permalink |In order to have a knockout tournament (without using

byes) the number of teams needs to be a power of 2 (half the teams are knocked out at each stage).So the numbers of teams we are dealing with cannot be powers of two. But we can divide the numbers into groups where the winners of the groups can have a knockout tournament, so the number of groups must be a power of 2. Hence the total number of teams has to have a divisor that is a power of 2.

Within a group of size

m, the number of matches where each team plays each other team isT(m − 1).This Python program looks for 2-digit values for the number of teams last year, works out the total number of matches played in the tournament, and then finds a scenario for this year which has the same total number of matches. It runs in 91ms.

Run:[ @repl.it ]Solution:56 teams entered last year. 80 teams entered this year.Last year the 56 teams were formed into 8 groups of 7. Each group would play 21 matches, and then the 8 winners of the groups would play 4 quarter-finals, 2 semi-finals and 1 final to give 175 matches in total.

This year the 80 teams were formed into 16 groups of 5. Each group would play 10 matches, and then the 16 winners of the groups would play 8 eighth-finals, 4 quarter-finals, 2 semi-finals and 1 final to also give 175 matches in total.

As a team was knocked out in the quarter-finals last year, the number of groups must have been at least 8, and we can consider multiples of 8 (that are not exact powers of 2). So there are only 8 candidate numbers for the number of teams last year: 24, 40, 48, 56, 72, 80, 88, 96.

There are two “near miss” scenarios:

But both are eliminated by the requirement that the number of teams this year is not twice the number of teams last year.

When I initially read the puzzle I took “not twice as many” to mean “fewer than twice as many”, but in my program I relaxed this condition to “not exactly twice as many”, and the single solution remains.

There is also the question of whether, in the knockout tournament, there is a match to decide 3rd and 4th places. It doesn’t matter if there is or not, as long as both tournaments use the same format. If there is a match for the semi-final losers then the total numbers of matches will be increased by 1.

LikeLike

## Robert Brown 8:30 pm

on19 July 2019 Permalink |Doesn’t need a program . . .

LikeLike

## Jim Randell 12:52 pm

on22 July 2019 Permalink |Here is a

MiniZincmodel for the puzzle. It executes in 66ms.I wasn’t sure how use the neat trick to test for powers of 2 in

MiniZinc, so I assumed an upper bound of 1,000 teams, and just made a set of powers of 2 less than this.LikeLike