Skip to content

Sunday Times Teaser 2965 – Knock, Knock

by Victor Bryant

Published July 21 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?

4 Comments Leave one →
  1. Brian Gladman permalink

    This solution runs in less than 1 millisecond using profile based timing. An analytic solution can be obtained as follows.

    Let last years competition consist of \(2^j\) groups each of \(m\) teams with \(2^j m\) teams in total playing \(2^j – 1 + 2^{j-1} m(m-1)\) matches.  Let the equivalent values for this year’s competition be \(2^k\) groups each of \(n\) teams playing \(2^k – 1 + 2^{k-1} n(n-1)\) matches. Equating the number of matches played this year and last year and rearranging the result gives:\[(2m-1)^2-2^{k-j}(2n-1)^2=7(2^{k-j}-1)\]Letting \[\begin{eqnarray}p&=&2m-1\\q&=&(2n-1)2^\left\lfloor\frac{k-j}{2}\right\rfloor\end{eqnarray}\] we obtain two different quadratic diophantine equations depending on whether \(k-j\) is even or odd:\[\begin{eqnarray}p^2&-&q^2&=&7(2^{k-j}-1)\;\;\;\;&k-j \text{ even}\\p^2&-2&q^2&=&7(2^{k-j}-1)\;\;\;\;&k-j\text{ odd}\end{eqnarray}\]The first of these can be solved by factoring both its sides and equating factors to give a finite number of solutions.  The second is a variant of Pell’s equation which has an infinite set of solutions as discussed here. For \(j=3\) and \(k=4\) we need solutions of the equation \[p^2-2 q^2=7\] which we can see has the two solutions \((p, q)\) equal to \((3, 1)\) and \((5, 3)\). From the analysis of Pell’s equation we can now use the following recurrence relations: \[\begin{eqnarray}p_{i+1}&=&3 p_i+ 4 q_i\\q_{i+1}&=&2 p_i + 3 q_i\end{eqnarray}\] to produce an infinite sequence of solutions as follows.

    \[\begin{eqnarray}(p, q):\;\;&(3,& 1)&\rightarrow &(13,&\;9)&\rightarrow&(\;75,&\;53)\;\dots\\&(5,&3)&\rightarrow&(27,&19)&\rightarrow&(157,&111)\;\dots\end{eqnarray}\]

    Converting these values to \(m\) and \(n\) we can now list the possible solutions for the team sizes, which gives:

    \[\begin{eqnarray}(&16,&32)&\rightarrow&(&\;56,&\;80)&\rightarrow&(&304,&432)\;\dots\\(&24,&32)&\rightarrow&(&112,&160)&\rightarrow&(&632,&896)\;\dots\end{eqnarray}\]

    Team sizes cannot be powers of two, which means that the smallest valid solution for the team sizes is \((56, 80)\) as found by the Python program given above.

    I have implemented methods for solving equations of this form in my number theory library which is described here The following program investigates possible solutions using it (the actual solution is that for \((j, k)\) = \((3, 4)\)):

  2. John Crabtree permalink

    Very neat analytical solution. Thank you.

  3. Erling Torkildsen permalink

  4. Erling Torkildsen permalink

    By using a dictionary based on the number of matches, M, and its corresponding number(s) of total teams, n, the task of finding doublets is much easier, simply: len(Ms[M]) == 2.
    (This simplification is by hint from Brian.)

Leave a comment to Erling Torkildsen Cancel reply

Note: HTML is allowed. Your email address will not be published.

Subscribe to this comment feed via RSS