33
$\begingroup$

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)

$\endgroup$
7
  • 2
    $\begingroup$ 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) $\endgroup$
    – Retudin
    Dec 18, 2023 at 9:51
  • 2
    $\begingroup$ Indeed, like @Retudin asked: can we tie for last (or any other) place? or only for first place? $\endgroup$ Dec 18, 2023 at 12:05
  • 1
    $\begingroup$ @Retudin there are never more than 12 competitors in a race $\endgroup$
    – juicifer
    Dec 18, 2023 at 14:54
  • $\begingroup$ 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. $\endgroup$
    – Hearth
    Dec 18, 2023 at 15:38
  • $\begingroup$ I have an intuition that the generalized case is NP-hard. By some reduction from subset-sum or something like that, maybe. $\endgroup$
    – rus9384
    Dec 18, 2023 at 20:30

3 Answers 3

40
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ The possible common scores in an $11$-way tie turn out to be $25, 26, 27, 28, 29$. $\endgroup$
    – RobPratt
    Dec 19, 2023 at 23:04
  • $\begingroup$ @RobPratt Sounds interesting, can you elaborate? I'd like to know how you found those $\endgroup$ Dec 20, 2023 at 2:50
  • 3
    $\begingroup$ 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. $\endgroup$ Dec 20, 2023 at 15:01
  • $\begingroup$ @HansOlsson They are all achievable. $\endgroup$
    – RobPratt
    Dec 21, 2023 at 0:46
10
$\begingroup$

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$

$\endgroup$
0
6
$\begingroup$

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}

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – justhalf
    Dec 21, 2023 at 6:00
  • $\begingroup$ There are numerous solutions (and not that to make by hand) so 'the' scoring does not really exist. $\endgroup$
    – Retudin
    Dec 21, 2023 at 13:04
  • 1
    $\begingroup$ @justhalf I added solutions for 25 and 29 just now. $\endgroup$
    – RobPratt
    Dec 21, 2023 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.