Arqade Asked by Der_Reparator on August 12, 2021
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.
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.
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.
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?
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.
Correct answer by mlk on August 12, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP