Quelle est la différence minimale de points entre la première et la dernière place dans Mario Kart Wii après N courses ?

Question

Tout d'abord : Je sais que ma question est bien plus un problème mathématique/une énigme/... qu'une question vraiment liée au jeu, mais j'ai pensé que, par exemple, le Math StackExchange ne correspondait pas à la question.

La mise en place

Ces derniers jours, j'ai joué à Super Mario Kart Wii en écran partagé à 3 joueurs avec mes colocataires. Après avoir terminé l'une des séries de courses (nous jouons toujours 8 courses à la fois), la question s'est posée de savoir à quel point les scores finaux des 12 pilotes pouvaient être proches.

Le problème

Dans Super Mario Kart Wii, les 12 places d'une course se voient attribuer le nombre de points suivant :

Lieu

Points

1er

15

2ème

12

3ème

10

4ème

8

5ème

7

6ème

6

7ème

5

8ème

4

9ème

3

10ème

2

11ème

1

12ème

0

Donc après 1 course La différence minimale de points entre la dernière et la première place est de 15 .

Et la différence maximale de points est très facile à calculer, même pour N courses, car le même joueur peut toujours arriver 1er tandis qu'un autre joueur peut toujours arriver dernier :

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

Mais comment calculer la minimum différence de points après exactement N courses ?

Ainsi, dans les courses intermédiaires, une répartition non optimale des points est autorisée si elle conduit à une différence minimale de points plus faible après N courses.

Note : Le nombre de points distribués dans une course est de 73.

Ce que nous avons fait jusqu'à présent

Nous avons essayé d'imposer par la force notre cas de N=8 : Mais il y a (naïvement) 12!^8 = 2*10^69 différentes distributions. Cela peut certainement être simplifié parce que l'ordre des 8 courses n'a pas d'importance, mais nous n'avons pas encore trouvé cette solution.

Nous avons imaginé une tactique pour N = even où nous inversons toujours les places (ainsi, les numéros 1, 2, 3, ... dans les courses impaires deviennent les numéros 12, 11, 10, ... dans les courses paires). Pour N=8 (qui a un nombre moyen de points pour chaque conducteur de 73*8/12 = 48.7 ), nous avons obtenu que le conducteur qui passe du n° 1 au n° 12 obtienne 60 points et les pilotes en milieu de peloton (par exemple en passant de la 6e à la 7e place) obtiennent des points. 44 points. Nous obtenons donc :

minDiff(8 selon la tactique ci-dessus) = 60 - 44 = 16

ce qui ne représente qu'une différence d'un point de plus que pour N = 1 .

Mais nous ne savons pas si c'est l'approche la plus efficace et nous ne savons pas comment traiter le cas de manière optimale N = odd .

---

Quelqu'un a-t-il trouvé une solution intéressante à ce problème ?

Answer 1

Une belle énigme. En bricolant un peu, on peut trouver des solutions optimales pour certains des plus petits nombres, puis combiner le reste à partir de là.

La différence minimale est de 15 et 4 points pour 1 ou 2 courses respectivement, puis toujours 1 point si le nombre n'est pas divisible par 12 et 0 point dans le cas contraire.

n=1 : Il n'y a pas beaucoup de choix, car la différence entre la première et la dernière place est toujours de 15.

n=2 : Le mieux que vous puissiez faire est d'inverser l'ordre avec un minimum de 15-11=4. Preuve d'optimalité : L'un d'entre eux aura au moins 15 points, ce qui signifie que la moyenne des autres est de (2*73-15) /11 = 11,909..., de sorte qu'au moins l'un des autres doit avoir 11 points ou moins.

n=3 : L'optimum est 1 (il ne peut pas être 0, car le nombre total de points n'est pas divisible par 12, il en va de même pour toutes les courses qui ne sont pas des multiples de 12) : 1ère+9ème+12ème place donne 18 points 2ème+7ème+11ème donne 18 points, 3ème+5ème+10ème donne 19 points et 4ème+6ème+8ème donne 18 points. Ainsi, si trois pilotes obtiennent une fois chacun une place dans ces quatre groupes, ils termineront tous avec 18 ou 19 points.

n=4 : L'optimum est 1. Même procédure avec la 1ère+6ème+9ème+12ème, la 2ème+5ème+7ème+11ème et la 3ème+4ème+8ème+10ème place pour 24, 25 et 24 points respectivement.

n=5 : Le dernier non réductible et le plus délicat. Là encore, vous pouvez atteindre 1, mais comme le nombre de conducteurs n'est pas divisible par 5, c'est beaucoup moins net. Tout d'abord, donnez les 2ème+4ème+7ème+8ème+10ème une fois chacun à un groupe de cinq pour 31 points chacun. Ensuite, distribuez les places/points restants entre les pilotes restants de la manière suivante (j'ai forcé cette partie avec un programme court, mais compte tenu de la rapidité et du nombre de solutions, cela aurait pu être fait à la main également) : Donner 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 et 0+6+3+15+6 points aux pilotes pour un total de 30 chacun.

n=6,9 : Répétez la procédure pour n=3 deux ou trois fois, mais changez les pilotes qui obtiennent 19 points.

n=7 : appliquer la procédure pour n=3 et n=4, de manière à ce que personne n'obtienne 19+25 points.

n=8 : Identique à la procédure n=4 deux fois.

n=10 : deux fois n=3, puis une fois n=4, toujours possible sans donner deux fois le point supplémentaire à qui que ce soit.

n=11 : idem 2x n=4 + n=3

n=12 : La valeur optimale est 0 : Il suffit d'attribuer chaque place à tout le monde précisément une fois.

n=13 : 3x n=3+ n=4, si la répartition est correcte, un conducteur obtient 2 des points supplémentaires et tous les autres en obtiennent 1.

n=14 : 2x n=3+ 2x n=4, similaire, avec 2 pilotes obtenant 2 points supplémentaires et tous les autres 1.

n>14 : Répétez n=12 jusqu'à ce qu'il ne reste plus que 14 courses ou moins, tout le monde ayant le même nombre de points, puis utilisez la solution correspondante.