Solution d'octobre 2009 - Centrale des maths

Il paraît évident qu'on minimise le nombre d'exemptions en appariant le plus possible les compétiteurs à chaque tour, accordant donc une seule exemption lorsque le nombre de compétiteurs restant est impair, et aucune lorsque ce nombre est pair. Ce fait reste à démontrer, ce que nous ferons plus bas. Pour l'instant, notons que si le tournoi se déroule selon cette règle, alors le nombre c_k de compétiteurs restant au k-ième tour suit la règle

où [x] dénote le plus petit entier inférieur ou égal à x. Avec au départ 2010 compétiteurs, la suite des c_k serait donc

Pour le voir, on peut supposer que les compétiteurs sont alignés, et appariés de gauche à droite: Le premier contre le deuxième, le troisième contre le quatrième, ... Le dernier bénéficie d'une exemption si le nombre de compétiteurs est impair. Après chaque tour, les perdants quittent la file et le processus se répète. L'idée de Dumortier et de Kouba est d'ajouter au départ 2^h - n compétiteurs imaginaires à la droite des compétiteurs réels. Une exemption correspond alors à un match entre un compétiteur réel et un compétiteur imaginaire, dont le vainqueur est bien sûr le compétiteur réel. Un match entre compétiteurs imaginaires donne un vainqueur imaginaire (dont on se moque éperdument) et match entre compétiteurs réels donne un vainqueur réels (qu'on félicite chaleureusement). De cette façon, le nombre total de compétiteurs au k-ième tour est 2^h-k+1, une puissance de 2, et le nombre i_k de compétiteurs restant au k-ième tour suit la règle

i_k+1= [i_k].

Ainsi, i_k est pair lorsque le k-ième chiffre de l'expression binaire de 2^h - n est 0, et impair lorsque le k-ième chiffre de l'expression binaire de 2^h - n est 1. Or, puisque c_k + i_k = 2^h-k+1, c_k et i_k ont la même parité.

Il nous reste à démontrer l'assertion de départ, selon laquelle le nombre d'exemptions est minimisé lorsqu'on accorde au plus une exemption à chaque tour. Pour se faire, nous allons appliquer l'idée des compétiteurs imaginaires à tout déroulement possible du tournoi: Le dernier tour est la confrontation des deux derniers compétiteurs réels en lice, pour déterminer le vainqueur du tournoi. On ajoute des compétiteurs imaginaires aux tours précédents selon les règles suivantes:

Une exemption au k-ième tour correspond à un match entre un compétiteur réel et un compétiteur imaginaire, dont le vainqueur est le compétiteur réel.
Un compétiteur imaginaire en lice à la fin du k-ième tour est le vainqueur d'un match de k-ième tour entre deux compétiteurs imaginaires
Un compétiteur réel toujours en lice à la fin du k-ième tour, et qui n'a pas bénéficié d'exemption au k-ième tour est le vainqueur d'un match de k-ième tour entre deux compétiteurs réels.

Ainsi, le nombre de compétiteurs réels et imaginaires au début du tournoi est une puissance de 2, soit n compétiteurs réels et 2^h - n compétiteurs imaginaires. Une exemption au k-ième tour correspond à l'élimination d'un compétiteur imaginaire qui était l'unique survivant d'un groupe de 2^k compétiteurs imaginaires qui se sont mutuellement éliminés. Puisqu'il y a au départ 2^h - n compétiteurs imaginaires, un tournoi à m exemptions correspond donc a l'expression de 2^h - n comme somme de m puissances de deux. Puisque 2^k + 2^k = 2^k+1, ce nombre est minimal lorsque chaque puissance de deux apparaît au plus une fois. Ainsi, le nombre d'exemptions est minimisé lorsqu'on accorde au plus une exemption à chaque tour.

Commentaires. Il semble que dans la vie réelle, les tournois sont organisés de façon à avoir toutes les exemptions au premier tour, ce qui donne 2^h - n exemptions plutôt que le minimum possible. Il ne semble pas y avoir d'avantage pratique à minimiser le nombre d'exemptions.