Problème du partage d'un collier

Exemple de partage : k = 2 partenaires, t = 2 couleurs de perles, et 8 perles rouges et 6 vertes. Chaque partenaire reçoit 4 perles rouges et 3 vertes. Une coupe est affichée : l'un des partenaires reçoit la section centrale et l'autre les deux parties restantes.

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 et Douglas West.

Description

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).

Variantes

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

1. Partage discretModèle:Rp : Le collier contient $k\cdot n$ perles. Les perles sont de $t$ couleurs différentes. Il y a $k\cdot a_i$ perles de chaque couleur $i$, où $a_i$ est un entier positif. On cherche à diviser le collier en $k$ parties (pas nécessairement contiguës), dont chacune contient exactement $a_i$ perles de couleur i, en effectuant au plus $(k-1)t$ coupes. Le nombre $(k-1)t$ est optimal car si les perles de chaque couleur sont contiguës sur le collier, il faut au moins $k-1$ coupes à l'intérieur de chaque couleur.
2. Partage continuModèle:Rp : Le collier est l'intervalle des nombres réels $[0,k\cdot n]$. Chaque réel de l'intervalle est coloré dans l'une des $t$ couleurs différentes. Pour chaque couleur $i$, l'ensemble des points colorés en $i$ est mesurable au sens de Lebesgue et de longueur $k\cdot a_i$, où $a_i$ est un nombre réel non négatif. On cherche à partitionner l'intervalle en $k$ parties (pas nécessairement contiguës), de sorte que dans chaque partie, la longueur totale de couleur $i$ est exactement $a_i$, le tout en effectuant au maximum $(k-1)t$ coupes.
3. Partage de mesuresModèle:Rp : Le collier est un intervalle de nombres réels. Il y a $t$ différentes mesures sur l'intervalle, toutes absolument continues par rapport à la longueur. La mesure de l'ensemble du collier, pour la mesure $i$, est $k\cdot a_i$. On doit partitionner l'intervalle en $k$ parties (pas nécessairement contiguës), de sorte que la mesure de chaque partie, selon la mesure $i$, est exactement $a_i$. et en effectuant au maximum $(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.

Réduction des variantes

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 $[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 perlesModèle:Rp.
• Le partage continu peut être ramené à un partage de mesures, puisqu'une coloration d'un intervalle en $t$ couleurs peut être convertie en un ensemble de $t$ mesures telles que la mesure $i$ a pour mesure la longueur totale de la couleur $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éeModèle:Rp.

Preuves

Le cas $k=2$ peut être prouvé par le théorème de Borsuk-Ulam.

Quand $k$ est un nombre premier impair, la preuve utilise une généralisation du théorème de Borsuk-Ulam.

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

Extensions

Colliers aléatoires

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 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 $\lfloor (t+1)/2\rfloor$ coupes tend vers zéro alors que la probabilité qu'il soit possible de réaliser le partage avec $\lfloor (t+1)/2\rfloor +1$ coupes est bornée et plus grande que zéro. Plus précisément, soit $X=X(t,m)$ le nombre minimal de coupes nécessaires pour diviser le collier. Alors, lorsque $m$ tend vers l'infini, on a :

pour tout $s<(t+1)/2$ :

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

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

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

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

Une coupe de moins

Dans le cas de deux voleurs (donc $k=2$) et de $t$ couleurs, un partage équitable nécessite au plus $t$ coupes. Avec seulement $t-1$ coupes, Gábor Simonyi 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 $D_1$ et $D_2$ de $\{1,\dots t\}$ disjoints et pas tous deux vides il existe une $t-1$-coupe telle que :

• Pour toute couleur $i\in D_1$, la partition 1 a plus de perles de couleur i que la partition 2 ;
• Pour toute couleur $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 » $D_1$ et $D_2$, non vides tous les deux, il existe une $t-1$-coupe de sorte que le voleur 1 obtient plus de perles de couleurs dans son ensemble de préférences '$D_1$ que le voleur 2 ; le voleur 2 obtient plus de perles de couleurs dans son jeu de préférences $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 $k=2$. En effet, soit le collier a une ($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 $D_1$ soit composé de la couleur fictive et $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.

Un résultat négatif

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

Partage multidimensionnels

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.

Algorithme d'approximation

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

Annexes

Bibliographie

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.

Articles liés

• Colliers combinatoires
• Modèle:Lien
• Modèle:Lien

Liens externes

• Modèle:YouTube, une vidéo d'introduction présentant entre autres le problème et sa solution topologique.