Problème du partage d'un collier

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