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?
Best Answer
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.