Le problème du collier

Piste bleue 18 août 2016  - Ecrit par  Frédéric Meunier Voir les commentaires (2)

Deux voleurs, Alice et Bob, viennent de rafler un magnifique collier, formé de perles de types variés. Arrive le moment de le partager... Le théorème du collier assure qu’un partage équitable va être possible sans avoir à couper la chaînette trop souvent. Simple à énoncer, ce théorème ne connaît cependant pas de preuve élémentaire. Et puis, ce n’est pas parce que l’on sait qu’un tel partage équitable existe qu’il est facile de le déterminer...

Voici donc le collier qu’Alice et Bob ont volé et souhaitent se partager de manière équitable.

JPEG - 21.9 ko
Un magnifique collier avec trois types de perles.

Le collier est formé de perles de différents types (Akoya, Tahiti, Hanadama, etc.), dont les voleurs ignorent la valeur. Coup de chance : il y a un nombre pair de perles de chaque type. Sur l’exemple de la figure ci-dessus, il y a trois types de perles et exactement quatre perles par type. Il suffit donc que chacun des deux voleurs prenne la moitié des perles de chaque type, et le partage sera équitable. Les perles sont solidement fixées sur la chaînette. Alice et Bob aimeraient cependant ne pas avoir à la couper trop souvent, parce que c’est une opération délicate, ou simplement parce que la chaînette elle-même est précieuse, et ce serait dommage d’abîmer cette dernière plus que nécessaire. Et c’est là que le miracle mathématique se produit.

Il existe toujours un partage équitable d’un collier ouvert avec un nombre pair de perles par type ne nécessitant pas plus de coupes qu’il n’y a de types de perles dans le collier.

Le collier de la figure ci-dessus met en jeu trois types de perles, et il peut bien être partagé équitablement entre Alice et Bob en trois coupes :

JPEG - 38.5 ko
Un partage équitable en trois coupes.

Même si le collier a des trillions de perles, du moment qu’il n’y a que trois types de perles et un nombre pair de perles par type, il existera un partage équitable en au plus trois coupes. En revanche, on ne peut pas espérer avoir un théorème assurant moins de coupes : il existe toujours un collier nécessitant un nombre de coupes égal au nombre de types pour obtenir un partage équitable. Un exemple de tel collier est donné sur la figure suivante.

JPEG - 26.5 ko
Sur ce collier, tout partage équitable nécessite au moins autant de coupes qu’il y a de types de perles.

Ce théorème, trouvé au milieu des années 80 par Alon, Goldberg et West [AW86,GW85], a indubitablement quelque chose de fascinant. Mais ce qui l’est encore plus, c’est que la preuve de ce théorème est tout sauf élémentaire....

Prouver le théorème du collier

Il existe désormais plusieurs preuves du théorème du collier, mais toutes font appel, de manière explicite ou non, au théorème de Borsuk-Ulam, ou à un résultat équivalent. Le théorème de Borsuk-Ulam est un résultat avancé de topologie (discipline des mathématiques étudiant la façon dont les objets se déforment), et même son énoncé dépasse le niveau de cet article. En d’autres termes, même si tout le monde est capable de comprendre l’énoncé du théorème du collier, seules les personnes ayant suivi des cours avancés de mathématiques seront capables d’en comprendre la preuve. Il y a là un véritable défi pour le mathématicien : comment se fait-il qu’un énoncé aussi simple n’ait pas de preuve élémentaire ?

Le théorème de Borsuk-Ulam

On note $\mathcal{S}^d$ la sphère unité de dimension $d$ centrée en $\boldsymbol{0}$. En d’autres termes, \[\mathcal{S}^d=\left\{(x_1,\ldots,x_{d+1})\in\mathbb{R}^{d+1}\colon \sum_{i=1}^{d+1}x_i^2=1\right\}.\]
Le théorème de Borsuk-Ulam s’exprime alors comme suit. Soit $f$ une fonction continue $\mathcal{S}^d\rightarrow\mathbb{R}^d$ telle que $f(-\boldsymbol{x})=-f(\boldsymbol{x})$ pour tout $\boldsymbol{x}\in\mathcal{S}^d$ ; alors il existe $\boldsymbol{x}^*\in\mathcal{S}^d$ telle que $f(\boldsymbol{x}^*)=\boldsymbol{0}$.

Ce théorème se comprend aisément dans le cas où $d=1$ : lorsqu’on prend le cercle unité, et qu’on le plonge sur la droite réelle de manière à couvrir des réels de signes différents, on couvre forcément $0$.

Une application traditionnelle de ce théorème est la suivante : il existe toujours deux points symétriques sur Terre en lesquels la température et la pression sont identiques. Pour s’en convaincre, il suffit d’appliquer le théorème pour $d=2$ et pour
\[f:\boldsymbol{x}\mapsto\big(T(\boldsymbol{x})-T(-\boldsymbol{x}),P(\boldsymbol{x})-P(-\boldsymbol{x})\big),\]
où $T(\cdot)$ et $P(\cdot)$ renvoient respectivement la température et la pression en un point du globe.

Cela dit, il y a des cas particuliers du théorème du collier qu’on peut aisément démontrer. Par exemple, le cas à deux types de perles, disons rouge et bleu, admet une preuve abordable. Considérons un premier partage potentiel consistant à couper le collier exactement au milieu et à donner la première partie à Alice et la seconde à Bob. Si la première partie a exactement la moitié des perles de chaque type, la seconde aussi, et l’on a alors un partage équitable ne nécessitant qu’une seule coupe.

Quitte à retourner le collier, on peut donc supposer que la première partie du collier possède plus de la moitié des perles rouges et moins de la moitié des perles bleues. Pour la seconde partie, c’est le contraire : il y a moins de la moitié des perles rouges et plus de la moitié des perles bleues. Faisons maintenant avancer une « fenêtre » de longueur constante, de la première partie du collier à la seconde partie.

JPEG - 123.3 ko
Preuve du théorème du collier lorsqu’il y a deux types de perles.

À chaque fois que la fenêtre se déplace d’une perle, le nombre total de perles rouges dans la fenêtre change d’au plus une unité. Comme la fenêtre passe d’une position où il y a plus de la moitié des perles rouges à une position où il y a en moins de la moitié, la fenêtre visite forcément une position où il y a pile le bon nombre de perles rouges. Et comme la fenêtre en cette position contient la moitié du nombre total de perles, elle contient aussi le bon nombre de perles bleues. On a donc notre partage du collier en deux coupes : il suffit de couper le collier aux extrémités de la fenêtre.

Un autre cas qui se prouve aisément et qui est laissé en défi pour le lecteur est le cas où le nombre de types est quelconque, mais où il y a exactement deux perles de chaque type.

Deux perles de chaque type

On passe en revue les perles, de la gauche vers la droite. On affecte toujours la perle considérée au voleur courant. Au début, c’est Alice le voleur courant. Lorsqu’on arrive sur un type que le voleur courant possède déjà, on change de voleur courant. Les moments où l’on change de voleur courant correspondent aux coupes du collier.

Lorsqu’on change de voleur courant, la perle considérée est forcément la seconde occurrence de son type. On change donc de voleur courant au plus un nombre de fois égal au nombre de types. D’où le résultat.

Un algorithme ?

Étant donné un collier ouvert, avec un nombre pair de perles par type, le théorème assure qu’il existe un partage équitable ne nécessitant pas plus de coupes qu’il n’y a de types. Mais est-ce facile d’en trouver un ? Peut-on trouver rapidement un tel partage équitable ? Là encore, la situation est intrigante : on ne sait pas. Cette question peut être formalisée mathématiquement avec la notion d’algorithme. Un algorithme est une suite d’opérations que l’on peut programmer sur un ordinateur, qui prend des données et retourne un résultat. Ici, les données décrivent un collier avec un nombre pair de perles par type, et le résultat est l’endroit où il faut couper le collier pour obtenir un partage équitable comme assuré par le théorème. Pour un mathématicien, la question est donc de savoir s’il existe un algorithme qui parvient toujours à trouver un tel partage équitable sans faire trop d’opérations. À ce jour, le seul algorithme connu permettant de trouver à coup sûr un tel partage équitable consiste à énumérer tous les partages avec le bon nombre de coupes et donnant autant de perles de chaque type à Alice et à Bob. Ce n’est pas un algorithme satisfaisant car il effectue un nombre d’opérations qui croît exponentiellement avec le nombre de types de perles : passer à une instance avec un type de plus, même sans changer le nombre total de perles, fait plus que doubler le nombre d’opérations à effectuer pour trouver le partage équitable. Trouver un partage équitable avec un tel algorithme pour un collier avec 30 types et 4 perles par type mettrait plusieurs milliards d’années, même sur les ordinateurs les plus performants du monde.

La question de l’existence d’un algorithme non-exponentiel, bien que posée pour un problème dont la pertinence pratique semble limitée, est d’un enjeu théorique considérable. Il existe de nombreux théorèmes, comme celui du théorème du collier, où on est assuré de l’existence d’un objet mathématique sans avoir d’information sur la façon de l’exhiber. Certains d’entre eux ont d’ailleurs un intérêt pratique certain (en particulier pour les résultats assurant l’existence d’équilibres économiques). La théorie traitant des problèmes algorithmiques consistant à exhiber de tels objets est encore mal comprise. Trouver un algorithme rapide pour le problème du collier, ou démontrer qu’il ne peut y en avoir (oui, on peut démontrer sous certaines conditions l’inexistence d’algorithmes), permettrait sans aucun doute d’améliorer notre compréhension de cette théorie. Il est d’ailleurs possible que si on parvient un jour à trouver une preuve élémentaire du théorème, cette preuve donnera également un algorithme rapide.

Et s’il y a trois voleurs (ou même plus) ?

Un mathématicien à qui on présente le théorème du collier et sa preuve va naturellement se poser les questions mentionnées ci-dessus. Existe-t-il une preuve élémentaire ? Existe-t-il un algorithme rapide calculant un tel partage équitable ? Une autre question naturelle lui viendra aussi immédiatement à l’esprit : peut-on généraliser ce théorème ? Par exemple, existe-t-il un théorème couvrant le cas à deux voleurs, mais aussi le cas à trois voleurs, quatre voleurs, etc. ? On peut répondre par l’affirmative et le théorème, trouvé par Alon en 1987 [A87], est le suivant. Notons $q$ le nombre de voleurs et $t$ le nombre de types, et supposons que le nombre de perles par type est un multiple de $q$. Cette supposition permet d’assurer qu’il existe toujours un partage donnant, pour chaque type, le même nombre de perles à chaque voleur, i.e. un partage équitable.

Un collier ouvert avec $t$ types de perles et tel que le nombre de perles par type est divisible par $q$ peut être partagé équitablement entre $q$ voleurs sans avoir à le couper plus de $t(q-1)$ fois.

Lorsqu’il n’y a que deux voleurs, on a $q=2$ et le nombre de coupes nécessaire est bien au plus $t$.

Bien sûr, pour le cas où $q$ peut être quelconque, la preuve fait appel à des outils mathématiques encore plus avancés que le théorème de Borsuk-Ulam (à part dans des cas simples, comme le cas $t=2$ ou comme le cas où chaque type est présent exactement $q$ fois, laissés tous deux en défi pour le lecteur). Et bien entendu, on ne sait pas plus comment trouver un partage équitable de manière efficace pour cette généralisation.

Deux types pour un nombre quelconque de voleurs

On prouve ici le cas $t=2$ quand $q$ est quelconque. Comme précédemment, on appelle rouge et bleu les deux types considérés. La preuve fonctionne par récurrence sur $q$. Pour $q=2$, le résultat a été prouvé ci-dessus, avec l’argument de la fenêtre de longueur constante se déplaçant le long du collier. Supposons maintenant $q>2$. On considère un premier partage potentiel en $q$ parties, en coupant le collier toutes les $n/q$ perles, où $n$ est le nombre total de perles. Si chacune des parties a le bon nombre de perles de chacun des deux types, on a un partage équitable en $q-1<2(q-1)$ coupes.

On peut donc supposer qu’il y a une partie ayant plus d’une fraction $1/q$ des perles rouges et une autre moins. Le même argument de fenêtre que celui utilisé ci-dessus permet de conclure qu’il existe une position (entre ces deux parties) qui contient le bon nombre de perles rouges (et donc le bon nombre de perles bleues à cause de sa longueur). On retire les perles contenues dans cette fenêtre, et on applique l’hypothèse de récurrence au collier restant, pour un nombre de voleurs égal à $q-1$, puisque les perles retirées ont déjà satisfait un voleur. Les deux extrémités de la fenêtre sont deux coupes additionnelles et on a donc un total d’au plus $2+2(q-2)=2(q-1)$ coupes, ce qui achève la récurrence.

Chaque type présent exactement $q$ fois

La preuve est quasiment identique à celle du cas à deux voleurs et deux perles par type, donnée dans un encadré ci-dessus. On passe de même en revue les perles, de la gauche vers la droite, et on affecte toujours la perle considérée au voleur courant. Lorsqu’on arrive sur un type que le voleur courant possède déjà, on choisit un voleur courant qui ne possède pas encore ce type. Il en existe forcément un, car le nombre de perles par type est égal au nombre de voleurs. Le reste de la preuve est identique.

Il existe même une généralisation de cette généralisation, dans le cas où le nombre de perles n’est pas un multiple de $q$. Les voleurs estiment alors qu’un partage est équitable si, pour chaque type, ils voient le nombre de perles reçues différer d’au plus une unité. Mais le théorème reste le même : il existe toujours un partage équitable ne nécessitant pas plus de $t(q-1)$ coupes.

À l’origine : des motivations pratiques

Le théorème du collier et les questions qui y sont associées sont avant tout théoriques. Le partage équitable souhaité par les voleurs est un moyen de mettre en scène le théorème et ne constitue absolument pas une réelle motivation pratique. Cela dit, ce sont bien de telles motivations qui sont à son origine. C’est lors de travaux sur la conception de circuits intégrés que deux chercheurs américains, Bhatt et Leiserson [BL81], en sont venus au début des années 80 à le formuler comme une conjecture. Cette dernière ne leur était pas directement utile, mais le cas particulier à deux types de perles leur servait dans un algorithme d’agencement de composants électroniques, et ils se sont naturellement posé la question du cas à plus de deux types.

Ce qui est curieux, c’est que ce théorème a vécu la même histoire une seconde fois. Dans les années 2000, trois chercheurs allemands, Epping, Hochstättler et Oertel [EHO04], l’ont à nouveau formulé sous forme d’une conjecture alors qu’ils menaient des travaux appliqués dans un contexte de production automobile. Ils ne savaient pas que c’était déjà un théorème, mais cette ignorance n’est pas tellement surprenante : le nombre de résultats mathématiques publiés chaque année est tellement gigantesque qu’il est fréquent de passer à côté de certains résultats, même pertinents à sa recherche propre. Plus précisément, ils s’intéressaient au problème d’optimisation des opérations de peinture dans les chaînes de montage de l’industrie automobile. Un cas très particulier de leur problème — trop particulier pour être réaliste, mais cependant tout à fait naturel — coïncidait avec le problème du partage du collier à $q$ voleurs, et ils ont naturellement conjecturé la borne $t(q-1)$.

De nombreuses applications concrètes bénéficient de la puissance d’outils mathématiques théoriques. Ces deux histoires illustrent la réciproque : la recherche fondamentale en mathématiques se nourrit souvent de motivations pratiques.

Références

[AW86] N. Alon et D. West, The Borsuk-Ulam theorem and bisection of necklaces, Proceedings of the American Mathematical Society 98 (1986), 623-628.

[A87] N. Alon, Splitting necklaces, Advances in Mathematics 63 (1987), 247-253.

[BL81] S. N. Bhatt et C. E. Leiserson, How to assemble tree machines (extended abstract), Proceedings of the 14th Symposium on the Theory of Computing (1981), 99-104.

[EHO04] T. Epping, W. Hochstättler et P. Oertel, Complexity results on a paint shop problem, Discrete Applied Mathematics 136 (2004), 217-226.

[GW85] C. H. Goldberg et D. West, Bisection of circle colorings, SIAM Journal of Algebraic Discrete Methods 6 (1985), 93-106.

Post-scriptum :

L’auteur et la rédaction d’Images des Maths tiennent à remercier
les relecteurs agirand et François Guéritaud pour leur relecture attentive et leurs commentaires judicieux.

Article édité par Elise Janvresse

Partager cet article

Pour citer cet article :

Frédéric Meunier — «Le problème du collier» — Images des Mathématiques, CNRS, 2016

Commentaire sur l'article

  • Le problème du collier

    le 17 août à 19:54, par Guillaume

    Autres questions dans le cas deux voleurs :
    - Est-ce qu’il existe un algorithme/preuve « simple » qui garantit l’égalité en k*|nombre de type de perle| coupes pour un k ? Une sorte d’algorithme d’approximation ?
    - Est-ce qu’il existe un algorithme/preuve « simple » qui garantit en |nombre de type de perle| coupes qu’aucun voleur n’a plus de k* le nombre de perles de l’autre voleur pour chaque type de perle ?

    Répondre à ce message
    • Le problème du collier

      le 25 août à 21:58, par Frédéric Meunier

      Oui, ce sont d’excellentes questions, dont les réponses ne sont pas connues.

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM