Problème du partage d'un collier

Le problème du partage d'un collier est le nom imagé donné à plusieurs problèmes semblables en combinatoire et en théorie de la mesure. Son nom et ses solutions sont dus aux mathématiciens Noga Alon^[1] et Douglas West^[2].

La formulation de base comprend un collier avec des perles de différentes couleurs. Le collier doit être partagé entre plusieurs partenaires (des « voleurs »), de sorte que chaque partenaire reçoive la même quantité de perles de chaque couleur. De plus, le nombre de « coupes » doit être le plus petit possible (afin de gaspiller le moins possible de métal entre les perles).

Le problème admet de nombreuses variantes ; les suivantes ont été décrites et résolues dans l'article original :

1. Partage discret^{[1]:Th 1.1} : Le collier contient ${\displaystyle k\cdot n}$ perles. Les perles sont de ${\displaystyle t}$ couleurs différentes. Il y a ${\displaystyle k\cdot a_{i}}$ perles de chaque couleur ${\displaystyle i}$, où ${\displaystyle a_{i}}$ est un entier positif. On cherche à diviser le collier en ${\displaystyle k}$ parties (pas nécessairement contiguës), dont chacune contient exactement ${\displaystyle a_{i}}$ perles de couleur i, en effectuant au plus ${\displaystyle (k-1)t}$ coupes. Le nombre ${\displaystyle (k-1)t}$ est optimal car si les perles de chaque couleur sont contiguës sur le collier, il faut au moins ${\displaystyle k-1}$ coupes à l'intérieur de chaque couleur.
2. Partage continu^{[1]:Th 2.1} : Le collier est l'intervalle des nombres réels ${\displaystyle [0,k\cdot n]}$. Chaque réel de l'intervalle est coloré dans l'une des ${\displaystyle t}$ couleurs différentes. Pour chaque couleur ${\displaystyle i}$, l'ensemble des points colorés en ${\displaystyle i}$ est mesurable au sens de Lebesgue et de longueur ${\displaystyle k\cdot a_{i}}$, où ${\displaystyle a_{i}}$ est un nombre réel non négatif. On cherche à partitionner l'intervalle en ${\displaystyle k}$ parties (pas nécessairement contiguës), de sorte que dans chaque partie, la longueur totale de couleur ${\displaystyle i}$ est exactement ${\displaystyle a_{i}}$, le tout en effectuant au maximum ${\displaystyle (k-1)t}$ coupes.
3. Partage de mesures^{[1]:Th 1.2} : Le collier est un intervalle de nombres réels. Il y a ${\displaystyle t}$ différentes mesures sur l'intervalle, toutes absolument continues par rapport à la longueur. La mesure de l'ensemble du collier, pour la mesure ${\displaystyle i}$, est ${\displaystyle k\cdot a_{i}}$. On doit partitionner l'intervalle en ${\displaystyle k}$ parties (pas nécessairement contiguës), de sorte que la mesure de chaque partie, selon la mesure ${\displaystyle i}$, est exactement ${\displaystyle a_{i}}$. et en effectuant au maximum ${\displaystyle (k-1)t}$ coupes. Il s'agit d'une généralisation du théorème de Hobby-Rice, et il est utilisé pour obtenir un partage équitable d'un gâteau.

Chacun des problèmes peut être résolu comme suit :

• Le partage discret peut ramené à un partage continu, puisqu'un collier discret peut être converti en une coloration de l'intervalle réel ${\displaystyle [0,k\cdot n]}$ dans laquelle chaque intervalle de longueur 1 est coloré par la couleur de la perle correspondante. Dans le cas où le partage continue essaie de couper à l'intérieur d'une perle, les coupes peuvent être glissées continument de sorte qu'elles ne soient réalisées qu'entre les perles^{[1]:p. 249}.
• Le partage continu peut être ramené à un partage de mesures, puisqu'une coloration d'un intervalle en ${\displaystyle t}$ couleurs peut être convertie en un ensemble de ${\displaystyle t}$ mesures telles que la mesure ${\displaystyle i}$ a pour mesure la longueur totale de la couleur ${\displaystyle i}$. L'inverse est également vrai : le partage des mesures peut être résolu par un partage continu, mais en utilisant une réduction plus sophistiquée^{[1]:p. 252–253}.

Le cas ${\displaystyle k=2}$ peut être prouvé par le théorème de Borsuk-Ulam^[2].

Quand ${\displaystyle k}$ est un nombre premier impair, la preuve utilise une généralisation du théorème de Borsuk-Ulam^[3].

Quand ${\displaystyle k}$ est un nombre composé, la preuve est la suivante (illustrée ici pour la variante de partage de mesures). On suppose que ${\displaystyle k=p\cdot q}$. Il y a ${\displaystyle t}$ mesures, dont chacune a la valeur ${\displaystyle p\cdot q\cdot a_{i}}$ sur le collier entier. En utilisant ${\displaystyle (p-1)\cdot t}$ coupes, on divise le collier en ${\displaystyle p}$ parties telles que la mesure ${\displaystyle i}$ de chaque partie vaut exactement ${\displaystyle q\cdot a_{i}}$. En utilisant ${\displaystyle (q-1)\cdot t}$ coupes, on divise chacune de ces parties en ${\displaystyle q}$ pièces telles que la mesure ${\displaystyle i}$ de chaque pièce vaut exactement ${\displaystyle a_{i}}$. Il y a alors ${\displaystyle pq}$ pièces telles que la mesure ${\displaystyle i}$ de chaque pièce est exactement ${\displaystyle a_{i}}$. Le nombre total de coupes est ${\displaystyle (p-1)\cdot t}$ plus ${\displaystyle p(q-1)\cdot t}$, ce qui au total est exactement ${\displaystyle (pq-1)\cdot t}$ .

Dans certains cas, des colliers aléatoires peuvent être partagés également en utilisant moins de coupes. Noga Alon, Dor Elboim, Gábor Tardos et János Pach^[4] ont étudié le nombre de coupes nécessaires pour partager un collier au hasard entre deux voleurs. Dans le modèle qu'ils ont considéré, un collier est choisi uniformément au hasard parmi l'ensemble des colliers avec t couleurs et m perles de chaque couleur. Lorsque m tend vers l'infini, la probabilité que le collier puisse être divisé en utilisant au plus ${\displaystyle \lfloor (t+1)/2\rfloor }$ coupes tend vers zéro alors que la probabilité qu'il soit possible de réaliser le partage avec ${\displaystyle \lfloor (t+1)/2\rfloor +1}$ coupes est bornée et plus grande que zéro. Plus précisément, soit ${\displaystyle X=X(t,m)}$ le nombre minimal de coupes nécessaires pour diviser le collier. Alors, lorsque ${\displaystyle m}$ tend vers l'infini, on a :

pour tout ${\displaystyle s<(t+1)/2}$ :

${\displaystyle \mathbb {P} (X=s)=\Theta {\big (}m^{s-(t+1)/2}{\big )}\ }$ pour ${\displaystyle s<(t+1)/2}$ ;

${\displaystyle \mathbb {P} (X=s)=\Theta (1)\ }$ pour ${\displaystyle (t+1)/2<s\leq t}$ ;

${\displaystyle \mathbb {P} (X=s)=\Theta {\big (}(\log m)^{-1}{\big )}\ }$ quand ${\displaystyle t}$ est impair et ${\displaystyle s=(t+1)/2}$.

On peut aussi considérer le cas où le nombre de couleurs tend vers l'infini. Lorsque ${\displaystyle m=1}$ et que ${\displaystyle t}$ tend vers l'infini, le nombre de coupes nécessaires est au plus ${\displaystyle 0,4t}$ et au moins ${\displaystyle 0,22t}$ avec une forte probabilité. Il est conjecturé qu'il existe une constante ${\displaystyle c}$ avec ${\displaystyle 0,22<c<0,4}$ tel que '${\displaystyle X(t,1)/t}$ converge vers ${\displaystyle c}$ en distribution.

Dans le cas de deux voleurs (donc ${\displaystyle k=2}$) et de ${\displaystyle t}$ couleurs, un partage équitable nécessite au plus ${\displaystyle t}$ coupes. Avec seulement ${\displaystyle t-1}$ coupes, Gábor Simonyi^[5] a montré que les deux voleurs peuvent réaliser un partage « presque équitable » au sens suivant :

Si le collier est constitué de sorte qu'aucune t-coupe n'est possible, alors pour deux sous-ensembles quelconques ${\displaystyle D_{1}}$ et ${\displaystyle D_{2}}$ de ${\displaystyle \{1,\ldots \,t\}}$ disjoints et pas tous deux vides il existe une ${\displaystyle t-1}$-coupe telle que :

• Pour toute couleur ${\displaystyle i\in D_{1}}$, la partition 1 a plus de perles de couleur i que la partition 2 ;
• Pour toute couleur ${\displaystyle i\in D_{2}}$, la partition 2 a plus de perles de couleur i que la partition 1 ;
• Pour une couleur i qui n'appartient à aucune des partitions, les deux partitions ont autant de perles de couleur i .

Cela signifie que si les voleurs ont des préférences sous la forme de deux ensembles de « préférences » ${\displaystyle D_{1}}$ et ${\displaystyle D_{2}}$, non vides tous les deux, il existe une ${\displaystyle t-1}$-coupe de sorte que le voleur 1 obtient plus de perles de couleurs dans son ensemble de préférences '${\displaystyle D_{1}}$ que le voleur 2 ; le voleur 2 obtient plus de perles de couleurs dans son jeu de préférences ${\displaystyle D_{2}}$ que le voleur 1 ; et le partage pour les autres couleurs est égal équitable.

Simonyi attribue à Gábor Tardos le fait d'avoir remarqué que le résultat ci-dessus est une généralisation directe du théorème original du collier d'Alon dans le cas ${\displaystyle k=2}$. En effet, soit le collier a une (${\displaystyle t-1}$)-coupe et il n'y a rien à prouver, soit ce n'est pas le cas, et on peut ajouter des perles d'une couleur fictive au collier et faire en sorte que ${\displaystyle D_{1}}$ soit composé de la couleur fictive et ${\displaystyle D_{2}}$ vide. Le résultat de Simonyi montre qu'il alors existe une t -coupe avec le même nombre de perles de chaque couleur réelle.

Pour chaque ${\displaystyle k\geq 1}$ il existe une ${\displaystyle (k+3)}$-coloration mesurable de la droite réelle telle qu'aucun intervalle ne puisse être partagé équitablement en utilisant au plus ${\displaystyle k}$ coupes^[6].

Le résultat peut être généralisé à n mesures de probabilité définies sur un cube de dimension d avec n'importe quelle combinaison de n (k − 1) hyperplans parallèles aux côtés pour k voleurs^[7].

Un algorithme d'approximation pour partager un collier peut être dérivé d'un algorithme de réduction de moitié par consensus^[8].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Necklace splitting problem » (voir la liste des auteurs).

• Noga Alon et Andrei Graur, « Efficient splitting of necklaces », 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, vol. LIPIcs 198,‎ 2021, p. 14:1-14:17.
• Aris Filos-Ratsikas et Paul W. Goldberg, « The complexity of necklace splitting, consensus-halving, and discrete ham sandwich », Proceedings STOC,‎ 2019, p. 638-649 (DOI 10.1145/3313276.3316334, arXiv 1805.12559).
• Duško Jojić, Gaiane Panina et Rade Živaljević, « Splitting Necklaces, with Constraints », SIAM Journal on Discrete Mathematics, vol. 35, n^o 2,‎ janvier 2021, p. 1268–1286 (DOI 10.1137/20M1331949, arXiv 1907.09740).

• Colliers combinatoires
• Problème de collier (en)
• Division exacte (en)

• [vidéo] « "Sneaky Topology" », sur YouTube, une vidéo d'introduction présentant entre autres le problème et sa solution topologique.

• Portail des mathématiques
• Portail de l'informatique théorique