.
. centre de ressources dilemmes et doutes le visage humain de mathématiques Qui sommes-nous Problème de mois activités de promotion babillard
Centrale des maths - centraledesmaths.uregina.ca
Problème du mois
Problème
du mois
  Problèmes récents
et solutions
Anciens problèmes
2005/2006 06/07 07/08 08/09 09/10 10/11 11/12

Solution au problème de septembre 2009

Le problème:
.

MP89
Problème d'octobre 2009

Un tournoi à élimination directe est une compétition en plusieurs tours. À
chaque tour les compétiteurs sont appariés, le vainqueur de chaque partie
passe au tour suivant et le perdant est éliminé. Une "exemption'' doit
parfois être accordée à un joueur qui n'a pas d'adversaire désigné à un
tour donné, et passe donc directement au tour suivant. Par exemple, avec 6
compétiteurs, on peut accorder deux exemptions au premier tour, ou bien
une seule exemption au deuxième tour. Notre problème du mois porte sur le
nombre minimal d'exemption qui doivent être accordées dans un tournoi à
élimination directe à n compétiteurs.

  1. 2010 compétiteurs étaient inscrits au tournoi international de "Je te
    tiens, tu me tiens par la barbichette'', à élimination directe. Quel est
    le nombre minimal d'exemptions qui auraient dû être accordées?

  2. À cause d'un scandale de dopage, seulement 1025 des compétiteurs ont pu
    participer. Combien d'exemptions ont dû être accordées?

La Barbichette

 

Nous avons reçu des solutions correctes de

Claudio Baiocchi (Italie)

Omran Kouba (Syrie)

Halima  Abdalla  Bashier (Regina)

Tannie Lau

Bojan Basic (Serbie)

Matthew Lim (États Unis)

José Borges (Portugal)

Jeff Lindstrom (Ontario)

Lou Cairoli (États Unis)

John T. Robinson (États Unis)

Dan Dima (Roumanie)

Uwe Schaefer (Allemagne)

Sébastien Dumortier (France)

Nutheti Shivdeep (Inde)

Magnus Jakobsson (Suède)

Albert Stadler (Suisse)


La solution:

  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 ck de compétiteurs restant au k-ième tour suit la règle

ck+1= [ck + 1],

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

2010, 1005, 503, 252, 126, 63, 32, 16, 8, 4, 2.

Nous avons souligné les termes impairs de la suite, correspondant aux tours où une exemption est nécessaire. On peut donc s'en tirer avec 3 exemptions. Avec 1025 compétiteurs, la suite correspondante est

1025, 513, 257, 129, 65, 33, 17, 9, 5, 3, 2,

donnant 10 exemptions nécessaires.

En fait, plusieurs de nos correspondants ont noté que

Le nombre d'exemptions nécessaires dans un tournoi à n compétiteurs est égal au nombre de fois où le chiffre 1 apparaît dans l'expression binaire de 2h - n, où 2h est la plus petite puissance de 2 supérieure ou égale à n.

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 2h - 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 2h-k+1, une puissance de 2, et le nombre ik de compétiteurs restant au k-ième tour suit la règle


ik+1
= [ik].

Ainsi, ik est pair lorsque le k-ième chiffre de l'expression binaire de 2h - n est 0, et impair lorsque le k-ième chiffre de l'expression binaire de 2h - n est 1. Or, puisque ck + ik = 2h-k+1ck et ik 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:
  1. 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.
  2. 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
  3. 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 2h - 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 2k compétiteurs imaginaires qui se sont mutuellement éliminés.  Puisqu'il y a au départ 2h - n compétiteurs imaginaires, un tournoi à m exemptions correspond donc a l'expression de 2h - n comme somme de m puissances de deux. Puisque 2k + 2k = 2k+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 2h - n exemptions plutôt que le minimum possible. Il ne semble pas y avoir d'avantage pratique à minimiser le nombre d'exemptions.


 

 


Centrale des maths reçoit une aide financière de l’Université de Regina et de The Pacific Institute for the Mathematical Sciences.

CMS
.

 

accueil centre de ressources accueil Société mathématique du Canada l'Université de Regina PIMS