Solution au problème de septembre 2006

1. Quinze chaises sont disposées régulièrement autour d'une table, chacune devant la carte d'identification d'un des quinze délégués. Cependant, les délégués ne remarquent pas les cartes d'identification avant de s'asseoir, et en fait aucun d'entre eux ne s'assoit devant la carte portant son nom. Démontrez qu'il est possible de tourner la table de sorte qu'au moins deux délégués soient assis à la bonne place.
   
   
2. Donnez un exemple d'un arrangement où seulement un des délégués est à la bonne place, et aucune des rotations ne permet de placer correctement plus d'un délégué.

Notre problème de septembre était le problème numéro 6 de l'Olympiade Mathématique Canadienne de 1975.

            Nous avons reçu des solutions correctes de 
 

Vinay Agarwala (États-Unis)		Xavier Hecquet (France)
Dave Arsenault (Internet)		Wolfgang Kais (Allemagne)
Pierre Bornsztein (France)		Normand LaLiberté (Ontario)
Phil Carmody (Finlande)		Matthew Lim (États-Unis)
K.A. Chandrashekara (Inde)		Juan Mir Pieras (Espagne)
Federico Felizzi (Italie)		Parham Noorzad Internet)
Philippe Fondanaiche (France)		Mark Pilloff (États-Unis)
Zac Friggstad (Edmonton)		Mohamed Benchaib (Internet)

Solution.
(a) Nous reproduisons ici la solution de Philippe Fondanaiche:
 Quand on fait tourner la table, elle prend15 positions différentes obtenues par des rotations successives de 24° chacune. Chaque délégué voit ainsi défiler les 15 cartes d'identification et il y a une position et une seule de la table pour laquelle il retrouve sa propre carte et se trouve ainsi assis à la bonne place. 
Comme il n'y a aucun délégué assis initialement à la bonne place avant rotation de la table, il en résulte qu'il y a au maximum 14 positions de la table pour lesquelles un délégué au moins est à la bonne place. Comme les 15 délégués retrouvent tous une fois et une seule leur propre carte en étant assis à la bonne place , d'après le principe des tiroirs ou principe de Dirichlet il y a donc une position de la table telle que deux délégués au moins sont assis à la bonne place.

Commentaires.  Plusieurs de nos correspondants nous ont fait remarquer que le même argument demeure valide pour n'importe quel nombre n > 1 de délégués. 
            Matthew Lim nous rappelle que la situation décrite dans le problème n'est pas si surprenante: Si les délégués s'assoient au hasard, la probabilité pour qu'aucun d'entre eux ne soit à la bonne place est légèrement supérieure à 1/3, tel qu'expliqué en particulier dans l'article de Mathworld sur les dérangements au http://mathworld.wolfram.com/Derangement.html. Par contre, personne n'a pu nous expliquer pourquoi les délégués ont décidé de faire tourner la table plutôt que de tout simplement changer de place

(b) La solution la plus populaire est de placer les délégués dans un ordre opposé à celui de leurs cartes. Nous démontrons la validité de cette solution de deux façons, après quoi nous verrons ce qui se passe si il y a n délégués plutôt que 15.

La façon géométrique.
            Imaginons que la table est un ``pendécagone'', c'est-à-dire un polygone régulier, avec quinze sommets. Les symétries des polygones sont bien connues; celles du pendécagone consistent en quinze rotations, et quinze réflections par rapport à un axe qui passe par le centre et un sommet du polygone. Chaque réflection fixe un seul sommet, et lorsqu'on compose une rotation avec une réflection, on obtient une autre réflection.  En y pensant bien, c'est exactement ce qui se passe lorsqu'on place les délégués dans l'ordre inverse de leurs cartes d'identification:
Pour chaque rotation de la table, le positionnement des délégués correspond à une réflection par rapport à leurs cartes. Cette réflection a un seul sommet fixe, c'est-à-dire un seul délégué placé devant sa propre carte.

La façon algébrique.
            Notons cycliquement 0, 1, ..., 14 les positions autour de la table. Les rotations de la tables correspondent à des ``addition modulo 15'' où a + b (mod 15) signifie le reste de la division de a + b par 15 et de même pour les soustractions. Ainsi, si c(i) dénote la position du délégué dont la carte d'identification est en position i, alors une rotation de k = c(i) - i (mod 15) lui rend sa carte. La permutation qui place les délégués dans un ordre opposé à celui de leurs cartes est c(i) = 15 - i (mod 15). La rotation de k positions ne rend sa carte qu'à un seul délégué si l'équation i + k = c(i) = 15 - i (mod 15) n'a qu'une solution. Cette équation se réduit à 

2i = 15 - k (mod 15).

Puisque 2i (mod 15) prend chacune des 15 valeurs possibles une seule fois, chaque équation a une seule solution. Ainsi, chaque rotation rend sa carte à un seul délégué.

Solutions algébriques alternatives.
            Xavier Hecquet place plutôt le délégué i en position 2i (mod 15). Comme on vient de le voir, cet arrangement évite les empilements de délégués, et l'équation i + k = c(i) = 2i (mod 15) devient i = 15 - k (mod 15), qui a clairement une seule solution pour chaque valeur de k. Mir note que la solution c(i) = 8i (mod 15) est une troisième possibilité: Pour qu'une solution de la forme c(i) = mi soit valide, il faut que m soit relativement premier à 15 (pour éviter les empilements de délégués), et que m-1 soit relativement premier à 15 (pour que l'équation i + k = mi (mod 15) ait une seule solution quel que soit le nombre k. Les valeurs

m = 2, 8, 14

sont les seules possibilités, 14 = -1 (mod 15) étant la plus populaire chez nos correspondants. Qu'en est-il en général lorsqu'il y a n délégués? Lorsque n est pair, Les solutions de la forme c(i) = mi (mod n) où m et m-1 sont relativement premiers à n demeurent valide, et parmi elles la plus simple c(i) = -i (mod n). Lorsque n est impair, ces solutions sont invalides (puisqu'on ne peut avoir m et m-1 tous deux relativement premiers à n), et il faut s'affairer à rechercher une permutation plus générale qui satisfait aux conditions demandées. En fait, une telle quête est vaine tel que l'ont démontré Bornsztein et Lim:

Lorsque n est pair, il n'existe aucune permutation c des délégués telle que pour tout k entre 0 et n-1, l'identité i = c(i) + k (mod n) est satisfaite pour exactement une valeur de i entre 0 et n-1.