# What is the largest n-way tie possible for Mario Kart?

In a $$12$$ player race, the scoring system of Mario Kart awards $$15$$ points for 1st place, $$12$$ for 2nd, then $$13-x$$ for $$3\leq x\leq 12$$. A standard cup is $$4$$ races. What is the largest $$n$$ such that an $$n$$-way tie is possible?

For example, a $$4$$-way tie is trivially achievable by having the four best racers achieve 1st, 2nd, 3rd and 4th once each. A $$12$$-way tie is trivially impossible, as the total points available is not divisible by $$12$$.

Optional extra: Can this be generalized to any point distribution/number of racers/number of races? Not required for accepted answer, but I'm curious to know.

(Full disclaimer, I don't know the answer)

• What for x>12 - 0 points? or is that not allowed. "12 is trivially impossible" suggest all players should tie, is this the intent. If not: Are we talking a tie for first place, or is any tie allowed (I get to a 22-way tie for last place, even infinite for scoring 0, but assume that is not what you want) Commented Dec 18, 2023 at 9:51
• Indeed, like @Retudin asked: can we tie for last (or any other) place? or only for first place? Commented Dec 18, 2023 at 12:05
• @Retudin there are never more than 12 competitors in a race Commented Dec 18, 2023 at 14:54
• Note that the scoring is different in different entries in the series; prior to mario kart 8, you couldn't even have 12-person races, with 8 being the maximum. Commented Dec 18, 2023 at 15:38
• I have an intuition that the generalized case is NP-hard. By some reduction from subset-sum or something like that, maybe. Commented Dec 18, 2023 at 20:30

An 11 way tie is possible:

11 players score 28:
4 players finish 1st, 3rd, 11th and 12th: 15 + 10 + 2 + 1 = 28
4 players finish 2nd, 4th, 9th and 10th: 12 + 9 + 4 + 3 = 28
2 players finish 5th twice and 7th twice, : 8 + 8 + 6 + 6 = 28
1 player finishes 6th in each race: 7 + 7 + 7 + 7 = 28
with last place finishing 8th in each race: 5 + 5 + 5 + 5 = 20

• The possible common scores in an $11$-way tie turn out to be $25, 26, 27, 28, 29$. Commented Dec 19, 2023 at 23:04
• @RobPratt Sounds interesting, can you elaborate? I'd like to know how you found those Commented Dec 20, 2023 at 2:50
• An 11-way tie where the common score isn't 25..29 is at least impossible, since the non-common score is either negative or above 60 (which requires more than 15 per round). And for 25..27 it will not be a tie for the win. But I don't know if they are achievable. Commented Dec 20, 2023 at 15:01
• @HansOlsson They are all achievable. Commented Dec 21, 2023 at 0:46

Here’s how to do a $$10$$-way tie:

- Four racers achieving 1st, 5th, 9th and 10th for a total of $$15+8+4+3=30$$
- Four racers achieving 2nd, 4th, 6th, and 11th for a total of $$12+9+7+2=30$$
- Two racers achieving 3rd and 8th twice, for a total of $$10+5+10+5 = 30$$
- Two racers achieving 7th and 12th twice, who tie last with a score of $$6+1+6+1=14$$

You can solve the problem via integer linear programming as follows. For $$j\in \{1,\dots,12\}$$, let $$p_j$$ be the points awarded for place $$j$$; that is, $$p_1=15$$, $$p_2=12$$, and $$p_j=13-j$$ otherwise. For $$i\in\{1,\dots,12\}$$, $$j\in \{1,\dots,12\}$$, and $$k\in\{1,\dots,4\}$$, let binary decision variable $$x_{ijk}$$ indicate whether player $$i$$ places $$j$$ in race $$k$$. Let decision variable $$s_i$$ be the total score for player $$i$$, let decision variable $$c$$ be the common score, and let binary decision variable $$y_i$$ indicate whether $$s_i=c$$. The problem is to maximize $$\sum_i y_i$$ subject to linear constraints \begin{align} \sum_j x_{ijk} &= 1 &&\text{for all i and k} \tag1\label1 \\ \sum_i x_{ijk} &= 1 &&\text{for all j and k} \tag2\label2 \\ \sum_{j,k} p_j x_{ijk} &= s_i &&\text{for all i} \tag3\label3 \\ -15(1-y_i) \le s_i - c &\le 15(1-y_i) &&\text{for all i} \tag4\label4 \end{align} Constraint \eqref{1} assigns one place to each player and race. Constraint \eqref{2} assigns one player to each place and race. Constraint \eqref{3} enforces the definition of $$s_i$$. Constraint \eqref{4} enforces the logical implication $$y_i=1 \implies s_i=c$$.

The optimal objective value turns out to be $$11$$, achieved for example by the following outcomes (each race $$k$$ yields a permutation of $$\{1,\dots,12\}$$): $$\begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&7&7&12&28\\ 2&2&12&2&10&28\\ 3&3&1&12&11&28\\ 4&4&11&11&1&28\\ 5&5&5&10&4&28\\ 6&6&10&9&7&20\\ 7&7&3&8&6&28\\ 8&8&2&6&9&28\\ 9&9&9&1&8&28\\ 10&10&6&5&3&28\\ 11&11&4&4&5&28\\ 12&12&8&3&2&28 \end{matrix}$$

To find the range of possible common scores $$c$$, impose an additional constraint $$\sum_i y_i = 11$$ and minimize or maximize $$c$$. The range turns out to be $$25 \le c \le 29$$, and all five values are achievable.

Here's a solution with $$c=25$$: $$\begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&10&9&10&25\\ 2&2&11&11&4&25\\ 3&3&9&12&3&25\\ 4&4&5&7&11&25\\ 5&5&1&1&1&53\\ 6&6&4&5&12&25\\ 7&7&12&2&7&25\\ 8&8&8&6&5&25\\ 9&9&7&10&2&25\\ 10&10&2&8&8&25\\ 11&11&3&4&9&25\\ 12&12&6&3&6&25 \end{matrix}$$

Here's a solution with $$c=29$$: $$\begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&6&8&11&29\\ 2&2&9&9&4&29\\ 3&3&7&6&7&29\\ 4&4&5&4&10&29\\ 5&5&1&11&9&29\\ 6&6&2&10&6&29\\ 7&7&12&12&12&9\\ 8&8&4&3&8&29\\ 9&9&11&1&5&29\\ 10&10&10&5&1&29\\ 11&11&8&2&3&29\\ 12&12&3&7&2&29 \end{matrix}$$

• Can you list down the scoring for the 25 and the 29 score? That's something interesting since it's the lowest and highest possible score in the 11-way tie. Commented Dec 21, 2023 at 6:00
• There are numerous solutions (and not that to make by hand) so 'the' scoring does not really exist. Commented Dec 21, 2023 at 13:04
• @justhalf I added solutions for 25 and 29 just now. Commented Dec 21, 2023 at 14:18