Théorème du sandwich au jambon - Ham sandwich theorem

En mathématique théorie de la mesure , pour tout entier positif n le théorème sandwich au jambon états que compte tenu de n mesurables « objets » en n - dimensions espace euclidien , il est possible de diviser tous dans la moitié (par rapport à leur mesure , le volume par exemple) avec un seul hyperplan de dimension ( n − 1) .

Il a été proposé par Hugo Steinhaus et prouvé par Stefan Banach (explicitement en dimension 3, sans se soucier d'énoncer automatiquement le théorème dans le cas n-dimensionnel), et aussi des années plus tard appelé le théorème de Stone-Tukey d' après Arthur H. Stone et John Tukey .

Appellation

Un sandwich au jambon

Le théorème du sandwich au jambon tire son nom du cas où n = 3 et les trois objets à couper en deux sont les ingrédients d'un sandwich au jambon . Les sources diffèrent selon que ces trois ingrédients sont deux tranches de pain et un morceau de jambon ( Peters 1981 ), du pain et du fromage et du jambon ( Cairns 1963 ) ou du pain et du beurre et du jambon ( Dubins & Spanier 1961 ). En deux dimensions, le théorème est connu sous le nom de théorème de la crêpe pour désigner la nature plate des deux objets à couper en deux par une ligne ( Cairns 1963 ).

Histoire

Selon Beyer & Zardecki (2004) , le plus ancien article connu sur le théorème du sandwich au jambon, en particulier le cas n = 3 de la bissectrice de trois solides avec un plan, est de Steinhaus (1938) . L'article de Beyer et Zardecki comprend une traduction de l'article de 1938. Il attribue la pose du problème à Hugo Steinhaus , et crédite Stefan Banach comme le premier à résoudre le problème, par une réduction au théorème de Borsuk-Ulam . L'article pose le problème de deux manières : d'abord, formellement, comme « Est-il toujours possible de couper en deux trois solides, arbitrairement situés, à l'aide d'un plan approprié ? et deuxièmement, de manière informelle, comme « Pouvons-nous placer un morceau de jambon sous un coupe-viande afin que la viande, les os et la graisse soient coupés en deux ? » Plus tard, l'article offre une preuve du théorème.

Une référence plus moderne est Stone & Tukey (1942) , qui est à la base du nom " théorème de Stone-Tukey ". Cet article prouve la version n- dimensionnelle du théorème dans un cadre plus général impliquant des mesures. L'article attribue le cas n = 3 à Stanislaw Ulam , sur la base des informations d'un arbitre ; mais Beyer & Zardecki (2004) prétendent que c'est incorrect, étant donné l'article de Steinhaus, bien que « Ulam ait apporté une contribution fondamentale en proposant » le théorème de Borsuk-Ulam .

Variante bidimensionnelle : preuve à l'aide d'un couteau rotatif

La variante bidimensionnelle du théorème (également connue sous le nom de théorème de la crêpe ) peut être prouvée par un argument qui apparaît dans la littérature de coupe de gâteau équitable (voir par exemple la procédure de couteau rotatif de Robertson-Webb ).

Pour chaque angle , nous pouvons diviser la crêpe #1 en deux en utilisant une ligne droite en angle (pour voir cela, translatez [déplacez] une ligne droite en angle de à ; la fraction de la crêpe #1 couverte par la ligne passe continuellement de 0 à 1, donc d'après le théorème des valeurs intermédiaires, il doit être égal à 1/2 quelque part en cours de route). ${\displaystyle \alpha \in [0,180^{\circ }]}$${\style d'affichage \alpha }$${\style d'affichage \alpha }$${\displaystyle -\infty }$${\style d'affichage \infty }$

Cela signifie que nous pouvons prendre un couteau droit, le faire pivoter à chaque angle et le traduire de manière appropriée pour cet angle particulier, de sorte que la crêpe n ° 1 soit coupée en deux à chaque angle et à la translation correspondante. ${\displaystyle \alpha \in [0,180^{\circ }]}$

Lorsque le couteau est à l'angle 0, il coupe également la crêpe #2, mais les morceaux sont probablement inégaux (si nous avons de la chance et que les morceaux sont égaux, nous avons terminé). Définissez le côté « positif » du couteau comme le côté dans lequel la fraction de crêpe #2 est plus grande. Définir comme la fraction de crêpe #2 sur le côté positif du couteau. Au départ . ${\style d'affichage p(\alpha )}$${\style d'affichage p(0)\geq 1/2}$

Lorsque le couteau est à un angle de 180, le couteau est à l'envers, donc . Par le théorème des valeurs intermédiaires , il doit y avoir un angle dans lequel . Couper à cet angle coupe en deux les deux crêpes simultanément. ${\style d'affichage p(180)\leq 1/2}$${\style d'affichage p(\alpha )=1/2}$

variante n -dimensionnelle : preuve utilisant le théorème de Borsuk-Ulam

Le théorème du sandwich au jambon peut être prouvé comme suit en utilisant le théorème de Borsuk-Ulam . Cette preuve suit celle décrite par Steinhaus et al. (1938), attribuée ici à Stefan Banach , pour le cas n = 3 . Dans le domaine de la topologie équivariante , cette preuve relèverait du paradigme configuration-espace/tests-map.

Soit A ₁ , A ₂ , …, A _n les n objets que l'on souhaite diviser simultanément en deux. Soit S l' unité ( n − 1) -sphère noyée dans l' espace euclidien à n dimensions , centrée à l' origine . Pour chaque point p de la surface de la sphère S , on peut définir un continuum d' hyperplans affines orientés (pas nécessairement centrés en 0) perpendiculaires au vecteur ( normal ) de l'origine à p , avec le « côté positif » de chaque hyperplan défini comme le côté pointé par ce vecteur (c'est-à-dire qu'il s'agit d'un choix d' orientation ). D'après le théorème des valeurs intermédiaires , chaque famille de tels hyperplans contient au moins un hyperplan qui coupe l'objet borné A _n : à une translation extrême, aucun volume de A _n n'est du côté positif, et à l'autre translation extrême, tout A Le volume de _n est du côté positif, donc entre les deux, il doit y avoir une traduction qui a la moitié du volume de A _n du côté positif. S'il y a plus d'un tel hyperplan dans la famille, nous pouvons en choisir un canoniquement en choisissant le milieu de l'intervalle de translations pour lequel A _n est bissecté. On obtient ainsi, pour chaque point p de la sphère S , un hyperplan π ( p ) perpendiculaire au vecteur de l'origine à p et coupant A _n . ${\displaystyle \mathbb {R} ^{n}}$

Nous définissons maintenant une fonction f de la ( n − 1) -sphère S à ( n − 1) - espace euclidien comme suit : ${\displaystyle \mathbb {R} ^{n-1}}$

f ( p ) = ( volume de A ₁ sur le côté positif de π ( p ) , vol de A ₂ sur le côté positif de π ( p ) , ..., vol de A _{n -1} sur le côté positif de π ( p )) .

Cette fonction f est continue . D'après le théorème de Borsuk-Ulam , il existe des points antipodaux p et q sur la sphère S tels que f ( p ) = f ( q ) . Le secteur antipodaux p et q correspondent à des hyperplans de ( p ) et π ( q ) qui sont égaux sauf qu'ils ont des côtés opposés positifs. Ainsi, f ( p ) = f ( q ) signifie que le volume de A _i est le même du côté positif et négatif de π ( p ) (ou π ( q ) ), pour i = 1, 2, …, n -1 . Ainsi, π ( p ) (ou π ( q ) ) est la coupe de sandwich au jambon désirée qui coupe simultanément les volumes de A ₁ , A ₂ , …, A _n .

Mesurer les versions théoriques

En théorie de la mesure , Stone & Tukey (1942) ont prouvé deux formes plus générales du théorème du sandwich au jambon. Les deux versions concernent la bissection de n sous-ensembles X ₁ , X ₂ , …, X _n d'un ensemble commun X , où X a une mesure extérieure de Carathéodory et chaque X _i a une mesure extérieure finie.

Leur première formulation générale est la suivante: pour tout réel continu fonction , il existe un point p du n - sphère S ⁿ et un nombre réel de ₀ de sorte que la surface f ( p , x ) = de ₀ divise X dans f ( p , x ) < s ₀ et f ( p , x ) > s ₀ de mesure égale et divise simultanément la mesure extérieure de X ₁ , X ₂ , …, X _n . La preuve est encore une réduction au théorème de Borsuk-Ulam. Ce théorème généralise le théorème standard du sandwich au jambon en laissant f ( s , x ) = s ₁ x ₁ + … + s _n x _n . ${\displaystyle f\colon S^{n}\times X\to \mathbb {R} }$

Leur deuxième formulation est la suivante : pour toute fonction mesurable n + 1 f ₀ , f ₁ , …, f _n sur X qui sont linéairement indépendantes sur tout sous-ensemble de X de mesure positive, il existe une combinaison linéaire f = a ₀ f ₀ + a ₁ f ₁ + … + a _n f _n tel que la surface f ( x ) = 0 , divisant X en f ( x ) < 0 et f ( x ) > 0 , coupe simultanément la mesure extérieure de X ₁ , X ₂ , …, X _n . Ce théorème généralise le théorème standard du sandwich au jambon en laissant f ₀ ( x ) = 1 et en laissant f _i ( x ) , pour i > 0 , être la i -ième coordonnée de x .

Versions géométriques discrètes et computationnelles

Une coupe de jambon-sandwich de huit points rouges et sept points bleus dans l'avion.

En géométrie discrète et en géométrie computationnelle , le théorème du sandwich au jambon fait généralement référence au cas particulier dans lequel chacun des ensembles divisés est un ensemble fini de points . Ici, la mesure pertinente est la mesure de comptage , qui compte simplement le nombre de points de chaque côté de l'hyperplan. En deux dimensions, le théorème peut s'énoncer comme suit :

Pour un ensemble fini de points dans le plan, chaque couleur "rouge" ou "bleu", il y a une ligne qui coupe simultanément les points rouges et les points bleus, c'est-à-dire le nombre de points rouges de chaque côté de la ligne est égal et le nombre de points bleus de chaque côté de la ligne est égal.

Il existe un cas exceptionnel où des points se trouvent sur la ligne. Dans cette situation, on compte chacun de ces points comme étant soit d'un côté, de l'autre, soit d'un côté ou de l'autre de la ligne (éventuellement selon le point), c'est-à-dire que « bissecter » signifie en fait que chaque côté contient moins de la moitié du nombre total de points. Ce cas exceptionnel est en effet nécessaire pour que le théorème soit vérifié, bien sûr lorsque le nombre de points rouges ou le nombre de bleus est impair, mais aussi dans des configurations particulières avec des nombres de points pairs, par exemple lorsque tous les points se trouvent sur la même droite et les deux couleurs sont séparées l'une de l'autre (c'est-à-dire que les couleurs n'alternent pas le long de la ligne). Une situation où les nombres de points de chaque côté ne peuvent pas correspondre est fournie en ajoutant un point supplémentaire hors de la ligne dans la configuration précédente.

En géométrie computationnelle, ce théorème du sandwich au jambon conduit à un problème de calcul, le problème du sandwich au jambon . En deux dimensions, le problème est le suivant : étant donné un ensemble fini de n points dans le plan, chacun de couleur « rouge » ou « bleu », trouvez un sandwich au jambon coupé pour eux. Premièrement, Megiddo (1985) a décrit un algorithme pour le cas spécial séparé. Ici, tous les points rouges sont d'un côté d'une ligne et tous les points bleus sont de l'autre côté, une situation où il existe une coupe de sandwich au jambon unique, que Megiddo pourrait trouver en temps linéaire. Plus tard, Edelsbrunner & Waupotitsch (1986) ont donné un algorithme pour le cas général à deux dimensions ; la durée de leur algorithme est O ( n log n ) , où le symbole O indique l'utilisation de la notation Big O . Enfin, Lo & Steiger (1990) ont trouvé un optimal O ( n ) -temps algorithme . Cet algorithme a été étendu à des dimensions supérieures par Lo, Matoušek & Steiger (1994) où le temps d'exécution est . Étant donné d ensembles de points en position générale dans l'espace de dimension d , l'algorithme calcule un hyperplan de dimension ( d −1) qui a un nombre égal de points de chacun des ensembles dans ses deux demi-espaces, c'est-à-dire un ham -coupe sandwich pour les points donnés. Si d fait partie de l'entrée, aucun algorithme de temps polynomial ne devrait exister, car si les points se trouvent sur une courbe des moments , le problème devient équivalent à la division du collier , qui est PPA-complet . ${\style d'affichage o(n^{d-1})}$

Un algorithme en temps linéaire qui coupe en deux deux polygones convexes disjoints est décrit par Stojmenovíc (1991) .

Généralisations

Le théorème original fonctionne pour au plus n collections, où n est le nombre de dimensions. Si l'on veut bissecter un plus grand nombre de collections sans passer à des dimensions supérieures, on peut utiliser, à la place d'un hyperplan, une surface algébrique de degré k , c'est-à-dire une surface ( n −1 )–dimensionnelle définie par une fonction polynomiale de degré k :

Étant donné des mesures dans un espace à n dimensions, il existe une surface algébrique de degré k qui les coupe toutes en son milieu. ( Smith et Wormald (1998) ). ${\displaystyle {\binom {k+n}{n}}-1}$

Cette généralisation est prouvée en mappant le plan à n dimensions dans un plan dimensionnel, puis en appliquant le théorème original. Par exemple, pour n = 2 et k = 2 , le plan à 2 dimensions est mappé à un plan à 5 dimensions via : ${\displaystyle {\binom {k+n}{n}}-1}$

( x , y ) → ( x , y , x ² , y ² , xy ) .

Voir également

• Division exacte

Les références

• Beyer, WA ; Zardecki, Andrew (2004), "The early history of the ham sandwich theorem" , American Mathematical Monthly , 111 (1) : 58–61, doi : 10.2307/4145019 , JSTOR  4145019 , ProQuest  203746537.
• Cairns, Stewart S. (Printemps 1963), "Networks, ham sandwichs, and putty", Pi Mu Epsilon Journal , 3 (8) : 389-403, JSTOR  24338222.
• Dubins, LE ; Spanier, EH (janvier 1961), "Comment couper un gâteau équitablement", American Mathematical Monthly , 68 (1P1) : 1–17, doi : 10.1080/00029890.1961.11989615
• Edelsbrunner, Herbert ; Waupotitsch, R. (1986), "Computing a ham sandwich cut in two dimensions", Journal of Symbolic Computation , 2 (2) : 171-178, doi : 10.1016/S0747-7171(86)80020-7.
• Lo, Chi-Yuan ; Steiger, WL (1990), "An optimal time algorithm for ham-sandwich cuts in the plane", Actes de la deuxième conférence canadienne sur la géométrie computationnelle , pp. 5-9.
• Lo, Chi-Yuan ; Matoušek, Jiří ; Steiger, William L. (1994), "Algorithms for Ham-Sandwich Cuts", Discrete and Computational Geometry , 11 (4) : 433–452, doi : 10.1007/BF02574017.
• Megiddo, Nimrod (1985), "Partitioning with two lines in the plane", Journal of Algorithms , 6 (3) : 430-433, doi : 10.1016/0196-6774(85)90011-2.
• Peters, James V. (Été 1981), "The ham sandwich theorem and some related results", The Rocky Mountain Journal of Mathematics , 11 (3): 473-482, doi : 10.1216/RMJ-1981-11-3-473 , JSTOR  44236614.
• Smith, WD ; Wormald, NC (1998), "Théorèmes et applications du séparateur géométrique", Actes du 39e Symposium annuel sur les fondements de l'informatique (Cat. No.98CB36280) , p. 232, doi : 10.1109/sfcs.1998.743449 , ISBN 0-8186-9172-7, S2CID  17962961
• Steinhaus, Hugo (1938), "Notatki: Z topologii", Mathesis Polska (en polonais), 11 (1-2): 26-28.
• Pierre, Arthur H. ; Tukey, John W. (1942), "Théorèmes "sandwich" généralisés", Duke Mathematical Journal , 9 (2) : 356-359, doi : 10.1215/S0012-7094-42-00925-6.
• Stojmenovíc, Ivan (1991), "Bisections et coupes en sandwich au jambon de polygones convexes et de polyèdres.", Info. Traitement des lettons. , 38 (1) : 15-21, doi : 10.1016/0020-0190(91)90209-Z.

Liens externes

• Weisstein, Eric W. "Théorème du sandwich au jambon" . MathWorld .
• théorème du sandwich au jambon sur les premières utilisations connues de certains mots mathématiques
• Coupes de sandwich au jambon par Danielle MacNevin
• Une démonstration 2D interactive