Determine the number of rankings given some constraints.

Question

Here below is a combinatoric challenge. I am not sure if it can be craked only using pencil and paper or if a numerical simulation is required.

Four boats are doing a regatta. This one consists of seven races. At the end of each race, each crew is credited with one point if it finishes the race, plus one point for each boat finishing after it. There is never a tie in a race, but in order to break a tie in total points, the rule states that one crew will be "ahead" of the other if, over the seven races, they finished ahead of the other more often.

At the end of such a regatta, it was found that :

• all the boats finished all the races
• crews A, B and C are tied on points
• Crew A "beats" B, B "beats" C and C "beats" A!
• winning crew D finished in every possible place.

We called a regata, an ordered list of the seven rankings. Hence, if we discard the constraints: there are $(4!)^{7}$ possible regattas making brute force impossible

Let $S_{1}, ..., S_{k}$ be the total possible scores of crew D.

Let $N_{i}$ be the number of regattas respecting all the constraints and for which the total score of crew D is $S_{i}$. What is the sum of $\sum_{i=1}^kN_{i} Si$ ?

Here below my (limited) findings:

1) all the boats finished all the races => there are 10*7 = 70 points per regatta

2) crews A, B and C are tied on points and winning crew D finished in every possible place => crew D has either 19 or 22 points (solving D+3X=70 with D and X integer and D>X)

3) Crew A "beats" B, B "beats" C and C "beats" A! => I am not sure about this one but I think that in case D has 19 points, the only solution is that D got 4 times 3rd place and once on 1st 2nd and 4th place in order to respect some kind of symmetry for other 3 teams

Anyway, with all the above I tried pencil, paper but I am stuck. I also tried numerical computation but I am doing some logical error somewhere.

Any help would be very much appreciated !!

Answer 1

Your findings are a very good start. I would start the same, letting $a$, $b$, $c$ and $d$ denote the total numbers of points of crews $A$, $B$, $C$ and $D$, respectively. Then:

1. The first point tells you that $a+b+c+d=70$.
2. The second point tells you that $a=b=c$.
3. The fourth point tells you that $d>a,b,c$ and that $13\leq d\leq22$.

Putting these together shows that $d\geq18$ and $d\equiv1\pmod{3}$ because $$d=70-(a+b+c)=70-3a>70-3d,$$ so either $d=19$ or $d=22$. That is, $k=2$ and $\{S_1,S_2\}=\{19,22\}$, and $a=b=c\in\{16,17\}$.

Now we still have the third point to consider; there are many different restrictions to deduce from this, but whichever way you go about it, this seems to take some work. I should be doable with pencil and paper within 30 minutes though.

Answer 2

This is not a complete answer, and I don’t feel like working out a complete answer because this is really something that should be done by computers. But you wanted something mathematical instead of brute force, so here’s something that should make it possible for you to work out the cases by hand if you insist:

Consider the $6$ permutations of $ABC$ with respect to how they contribute to the intransitive result $A\gt B\gt C\gt A$:

\begin{array}{c|cc} &A\gt B&B\gt C&C\gt A\\\hline ABC&+&+&-\\ BCA&-&+&+\\ CAB&+&-&+\\ ACB&+&-&-\\ CBA&-&-&+\\ BAC&-&+&- \end{array}

The first three have two $+$ and one $-$, the other three two $-$ and one $+$. Summed over the seven permutations in the seven races (ignoring $D$) the sum in each column must be positive. Consider any pair of columns. Four of the permutations have one $+$ and one $-$, only one has two $+$ and only one has two $-$. Thus, to get to a total sum of at least $+2$ in a pair of columns, there must be at least one more of the one with two $+$ than of the one with two $-$, since the net contribution of the others is zero. So $ABC$, $BCA$ and $CAB$ must all occur at least once, and once more for each time their opposite occurs. Any excess of them over that must fulfill the weak triangle inequality, i.e. each two of the excesses must at least sum to the third.

That leaves us with the following possibilities (where in each case I write out one representative and put the number of symmetry equivalents in parentheses; the triples at the ends of the lines are explained below):

• $3\times ABC$, $2\times CBA$, $1\times BCA$, $1\times CAB\quad(3)\quad(7,7,7)$
• $2\times ABC$, $2\times BCA$, $1\times CBA$, $1\times ACB$, $1\times CAB\quad(3)\quad(7,7,7)$
• $3\times ABC$, $1\times CBA$, $2\times BCA$, $1\times CAB\quad(9)\quad(7,8,6)$
• $2\times ABC$, $1\times CBA$, $2\times BCA$, $2\times CAB\quad(3)\quad(6,7,8)$
• $3\times ABC$, $3\times BCA$, $1\times CAB\quad(3),\quad(7,9,5)$
• $3\times ABC$, $2\times BCA$, $2\times CAB\quad(3),\quad(8,7,6)$

We can also narrow down the possible placements of $D$. We must have $1$, $2$, $3$ and $4$ points at least once each, and that leaves either $9$ or $12$ points for the remaining $3$ races. If it’s $12$ points, the only possibility is $4$ per race. If it’s $9$ points, the possibilities are $(3,3,3)$, $(4,3,2)$ and $(4,4,1)$.

From the permutations of $ABC$ above we can derive the point totals that $A$, $B$ and $C$ would get if $D$ were always ahead of them. These are the triples at the ends of the lines above. Any imbalance here must be made up for by races where $D$ is somewhere in the middle, thus adding to the differences among $A$, $B$ and $C$. For instance, the permutations that lead to $(7,9,5)$ can’t be used in the cases where the excess placements of $D$ are $(4,4,4)$ or $(4,4,1)$, since in those cases there are only two races where $D$ is in the middle and that’s not enough to make up for the imbalance in $(7,9,5)$.

So there’s still some casework left for you to do, but it’s now a manageable task of filling the possible cases for $A$, $B$ and $C$ into the possible cases for $D$ such that the tied points for $A$, $B$ and $C$ come out right.