4

First off: I know my question is much more of an math problem/riddle/... than a really gaming related question, but I figured that e.g. the Math StackExchange didn't fit the question.

The Setup

In the last days I played Super Mario Kart Wii in 3-player Splitscreen with my roommates. After finishing one of the race series (we always play 8 races at a time), the question arose how close the final scores of all 12 drivers can become.

The Problem

In Super Mario Kart Wii, the 12 places in a race get awarded the following number of points:

Place Points
1st 15
2nd 12
3rd 10
4th 8
5th 7
6th 6
7th 5
8th 4
9th 3
10th 2
11th 1
12th 0

So after 1 race, the minimum point difference between last and first place is 15.

And the maximum point difference is very easy to calculate even for N races as the same player can always come in 1st while another player can always come in last:

maxDiff(N) = N * 15 - N * 0 = N * 15

But how can we calculate the minimum point difference after exactly N races?

So in the intermediate races a non-optimal distribution of points is allowed if that leads to a lower minimum point difference after N races.

Note: The number of points handed out in one race is 73.

What we've done so far

Tried to bruteforce our case of N=8: But there are (naively) 12!^8 = 2*10^69 different distributions. This can surely be simplified because the order of the 8 races doesn't matter but we did not come up with that yet.

We imagined a tactic for N = even where we always mirror the places (so #1, #2, #3, ... in odd races become #12, #11, #10, ... in even races). For N=8 (which has an average number of points for each driver of 73*8/12 = 48.7) we got that the driver who switches between #1 and #12 gets 60 points and the drivers in the middle of the pack (e.g. switching between #6 and #7) get 44 points. So we get:

minDiff(8 according to tactic above) = 60 - 44 = 16

which is only 1 point difference more than for N = 1.

But we don't know whether this is the most efficient approach and we don't know how to optimally handle the case N = odd.

Is anybody able to come up with a nice solution for this problem?

Improve this question
0

1 Answer 1

Reset to default
8

A nice riddle. With a bit of fiddling you can find optimal solutions for some of the smaller numbers and then combine the rest from there.

The minimal difference is 15 and 4 points difference for 1 or 2 races respectively and then always 1 point if the number is not divisible by 12 and 0 points otherwise.

n=1: Not much choice, as the difference between first and last place is always 15.

n=2: The best you can do is indeed reverse the order with a minimum of 15-11=4. Proof of optimality: One will have at least 15 points, which means the average for the others is (2*73-15) /11 = 11.909..., so at least one of the others needs to have 11 or less.

n=3: The optimum is 1 (it can't be 0, as the total number of points is not divisible by 12, the same is true for every non-multiple of 12 races): 1st+9th+12th place give you 18 points 2nd+7th+11th give you 18 points, 3rd+5th+10th give you 19 points and 4th+6th+8th give you 18 points. So if three drivers each get each place in these four groups once, they will all end up with either 18 or 19 points.

n=4: Optimum is 1. Same procedure with 1st+6th+9th+12th, 2nd+5th+7th+11th and 3rd+4th+8th+10th place for 24, 25 and 24 points respectively.

n=5: The last non-reducible one and the most tricky. Again you can reach 1, but because the number of drivers is not divisible by 5, it is far less neat. First, give 2nd+4th+7th+8th+10th once each to a group of five for 31 points each. Then distribute the remaining places/points among the remaining drivers in the following way (that part I brute-forced with a short program, but considering how fast it was and how many solutions there are, this could have been done by hand as well): Give 15+15+0+0+0, 10+10+6+3+1, 7+7+7+6+3, 6+3+10+1+10, 3+1+1+10+15, 1+0+15+7+7 and 0+6+3+15+6 points to the drivers for a total of 30 each.

n=6,9: Repeat the procedure for n=3 twice or thrice, but change which drivers get 19 points.

n=7: Apply the procedure for n=3 and n=4, again so that no one gets 19+25 points.

n=8: Same with the n=4 procedure twice.

n=10: two times n=3, then once n=4, again possible without giving anyone the extra point twice.

n=11: same with 2x n=4 + n=3

n=12: Optimum is 0: Just give every place to everyone precisely once.

n=13: 3x n=3+ n=4, if you split it correctly, one driver gets 2 of the extra points and all other get 1.

n=14: 2x n=3+ 2x n=4, similar, with 2 drivers getting 2 extra points and everyone else getting 1.

n>14: Repeat n=12 until you reach 14 or less races left with everyone at the same number of points, then use the corresponding solution.

Improve this answer
2
  • Nice bruteforce of the problem. But yeah after 12 the problem loops on itself. So yeah the n can be n%12
    – Fredy31 ♦
    May 3, 2021 at 14:14
  • Thank you for your efforts! As far as I can see, your proposed distributions of positions are all correct. From your hints on what is reducible and what is not, one can also directly conclude that the solutions of 1 cannot be reduced further to 0 and so these distributions indeed are correct.
    – Der_Reparator
    May 3, 2021 at 14:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .