Teorema del sándwich de jamón

En la teoría matemática de la medida , para cada entero positivo n, el teorema del sándwich de jamón establece que, dados n "objetos" medibles en un espacio euclidiano n - dimensional , es posible dividir cada uno de ellos por la mitad (con respecto a su medida , por ejemplo, volumen) con un único hiperplano ( n -1) -dimensional . Esto es posible incluso si los objetos se superponen.

Fue propuesto por Hugo Steinhaus y demostrado por Stefan Banach (explícitamente en dimensión 3, sin enunciar el teorema en el caso n -dimensional), y años más tarde también se le llamó teorema de Stone-Tukey en honor a Arthur H. Stone y John Tukey .

El teorema del sándwich de jamón toma su nombre del caso en que n = 3 y los tres objetos a bisecar son los ingredientes de un sándwich de jamón . Las fuentes difieren en si estos tres ingredientes son dos rebanadas de pan y un trozo de jamón ( Peters 1981 ) , pan, queso y jamón ( Cairns 1963 ) , o pan, mantequilla y jamón ( Dubins y Spanier 1961 ) . En dos dimensiones, el teorema se conoce como el teorema del panqueque para referirse a la naturaleza plana de los dos objetos a bisecar por una línea ( Cairns 1963 ) .

Según Beyer y Zardecki (2004) , el primer artículo conocido sobre el teorema del sándwich de jamón, específicamente el caso n = 3 de bisecar tres sólidos con un plano, es una nota de 1938 en una revista matemática polaca ( Editores 1938 ) . El artículo de Beyer y Zardecki incluye una traducción de esta nota, que atribuye el planteamiento del problema a Hugo Steinhaus y reconoce a Stefan Banach como el primero en resolverlo, mediante una reducción al teorema de Borsuk-Ulam . La nota plantea el problema de dos maneras: primero, formalmente, como "¿Es siempre posible bisecar tres sólidos, ubicados arbitrariamente, con la ayuda de un plano apropiado?" y segundo, informalmente, como "¿Podemos colocar un trozo de jamón debajo de una cortadora de carne de manera que la carne, el hueso y la grasa se corten por la mitad?". La nota luego ofrece una demostración del teorema.

Una referencia más moderna es Stone y Tukey (1942) , que es la base del nombre "teorema de Stone-Tukey". Este artículo demuestra la versión n -dimensional del teorema en un contexto más general que involucra medidas. El artículo atribuye el caso n = 3 a Stanislaw Ulam , basándose en información de un revisor; pero Beyer y Zardecki (2004) afirman que esto es incorrecto, dada la nota mencionada anteriormente, aunque "Ulam sí hizo una contribución fundamental al proponer" el teorema de Borsuk-Ulam .

La variante bidimensional del teorema (también conocida como el teorema del panqueque ) se puede demostrar mediante un argumento que aparece en la literatura sobre el corte de pasteles justos (véase, por ejemplo, el procedimiento del cuchillo giratorio de Robertson-Webb ).

Para cada ángulo${\displaystyle \alpha \in [0,180^{\circ }]}$, una línea recta ("cuchillo") de ángulo${\displaystyle \alpha }$puede bisecar el panqueque n.° 1. Para ver esto, traslade a lo largo de su normal una línea recta de ángulo${\displaystyle \alpha }$de${\displaystyle -\infty }$a${\displaystyle \infty }$La fracción del panqueque n.° 1 cubierta por la línea cambia continuamente de 0 a 1, por lo que, según el teorema del valor intermedio, debe ser igual a 1/2 en algún punto. Es posible que todo un rango de traslaciones de nuestra línea produzca una fracción de 1/2; en este caso, es una opción canónica elegir la del medio de todas esas traslaciones.

Cuando el cuchillo está en un ángulo de 0, también corta el panqueque n.° 2, pero los trozos probablemente sean desiguales (si tenemos suerte y los trozos son iguales, hemos terminado). Definimos el lado "positivo" del cuchillo como el lado en el que la fracción del panqueque n.° 2 es mayor. Ahora giramos el cuchillo y lo trasladamos como se describió anteriormente. Cuando el ángulo es${\displaystyle \alpha }$, definir${\displaystyle p(\alpha )}$como la fracción del panqueque n.° 2 en el lado positivo del cuchillo. Inicialmente${\displaystyle p(0)>1/2}$. La función${\displaystyle p}$es continuo, ya que pequeños cambios en el ángulo conllevan pequeños cambios en la posición del cuchillo.

Cuando el cuchillo está en un ángulo de 180 grados, el cuchillo está al revés, por lo tanto ${\displaystyle p(180)<1/2}$. Por el teorema del valor intermedio , debe existir un ángulo en el que${\displaystyle p(\alpha )=1/2}$Cortar en ese ángulo divide ambas tortitas por la mitad simultáneamente.

El teorema del sándwich de jamón se puede demostrar de la siguiente manera utilizando el teorema de Borsuk-Ulam . Esta demostración sigue la descrita por Steinhaus y otros (1938), atribuida allí a Stefan Banach , para el caso n = 3. En el campo de la topología equivariante , esta demostración se enmarcaría dentro del paradigma del espacio de configuración/mapa de pruebas.

Sean A ₁ , A ₂ , ..., A _n los n subconjuntos compactos (o más generalmente acotados y medibles según Lebesgue ) de${\displaystyle \mathbb {R} ^{n}}$que deseamos bisecar simultáneamente.${\displaystyle S=\{v=(v_{1},\ldots ,v_{n})\in \mathbb {R} ^{n}\colon v_{1}^{2}+\ldots +v_{n}^{2}=1\}}$sea ​​la esfera unitaria ( n − 1) en${\displaystyle \mathbb {R} ^{n}}$. Para cada punto v en S , podemos definir un continuo${\displaystyle (E_{v,c})_{c\in \mathbb {R} }}$de hiperplanos afines con vector normal v :${\displaystyle E_{v,c}=\{x\in \mathbb {R} ^{n}\colon x_{1}v_{1}+\ldots +x_{n}v_{n}=c\}}$para${\displaystyle c\in \mathbb {R} }$. Para cada${\displaystyle c\in \mathbb {R} }$, llamamos al espacio${\displaystyle E_{v,c}^{+}=\{x\in \mathbb {R} ^{n}\colon x_{1}v_{1}+\ldots +x_{n}v_{n}>c\}}$el "lado positivo" de${\displaystyle E_{v,c}}$, que es el lado al que apunta el vector v . Por el teorema del valor intermedio , toda familia de tales hiperplanos contiene al menos un hiperplano que biseca el conjunto acotado A _n : en una traslación extrema, ningún volumen de A _n está en el lado positivo, y en la otra traslación extrema, todo el volumen de A _n está en el lado positivo, por lo que entre ambos debe haber un intervalo cerrado I _v de posibles valores de${\displaystyle c\in \mathbb {R} }$, para el cual${\displaystyle E_{v,c}}$biseca el volumen de A _n . Si A _n tiene volumen cero, elegimos${\displaystyle c=0}$a pesar de${\displaystyle v\in S}$. De lo contrario, el intervalo I _v es compacto y podemos elegir canónicamente${\displaystyle c={\frac {1}{2}}(\inf I_{v}+\sup I_{v})}$como su punto medio para cada uno${\displaystyle v\in S}$De esta forma obtenemos una función continua.${\displaystyle \alpha \colon S\to \mathbb {R} }$de tal manera que para cada punto v en la esfera S el hiperplano${\displaystyle E_{v,\alpha (v)}}$biseca A _n . Nótese además que tenemos${\displaystyle I_{-v}=-I_{v}}$y por lo tanto${\displaystyle \alpha (-v)=-\alpha (v)}$a pesar de${\displaystyle v\in S}$.

Ahora definimos una función${\displaystyle f\colon S\to \mathbb {R} ^{n-1}}$como sigue:

${\displaystyle f(v)=(vol(A_{1}\cap E_{v,\alpha (v)}^{+}),\ldots,vol(A_{n-1}\cap E_{v,\alpha (v)}^{+}))}$.

Esta función f es continua (lo cual se puede demostrar con el teorema de convergencia dominada ). Por el teorema de Borsuk-Ulam , existen puntos antipodales.${\displaystyle v}$y${\displaystyle -v}$en la esfera S tal que${\displaystyle f(v)=f(-v)}$Los puntos antipodales corresponden a hiperplanos.${\displaystyle E_{v,\alpha (v)}}$y${\displaystyle E_{-v,\alpha (-v)}=E_{-v,-\alpha (v)}}$que son iguales excepto que tienen lados positivos opuestos. Por lo tanto,${\displaystyle f(v)=f(-v)}$significa que el volumen de A _i es el mismo en el lado positivo y negativo de${\displaystyle E_{v,\alpha (v)}}$, para${\displaystyle i=1,\ldots ,n}$. De este modo,${\displaystyle E_{v,\alpha (v)}}$es el corte deseado para el sándwich de jamón que divide simultáneamente en dos los volúmenes de A ₁ , ..., A _n .

En teoría de la medida , Stone y Tukey (1942) demostraron dos formas más generales del teorema del sándwich de jamón. Ambas versiones se refieren a la bisección de n subconjuntos X ₁ , X ₂ , ..., X _n de un conjunto común X , donde X tiene una medida exterior de Carathéodory y cada X _i tiene una medida exterior finita.

Su primera formulación general es la siguiente: para cualquier función real continua${\displaystyle f\colon S^{n}\times X\to \mathbb {R} }$, existe un punto p de la n - esfera S ⁿ y un número real s ₀ tal que la superficie f ( p , x ) = s ₀ divide a X en f ( p , x ) < s ₀ y f ( p , x ) > s ₀ de igual medida y simultáneamente biseca la medida exterior de X ₁ , X ₂ , ..., X _n . La demostración es nuevamente una reducción al teorema de Borsuk-Ulam. Este teorema generaliza el teorema estándar del sándwich de jamón al hacer f ( s , x ) = s ₁ x ₁ + ... + s _n x _n .

Su segunda formulación es la siguiente: para cualesquiera n + 1 funciones medibles f ₀ , f ₁ , ..., f _n sobre X que son linealmente independientes sobre cualquier subconjunto de X de medida positiva, existe una combinación lineal f = a ₀ f ₀ + a ₁ f ₁ + ... + a _n f _n tal que la superficie f ( x ) = 0 , que divide a X en f ( x ) < 0 y f ( x ) > 0 , biseca simultáneamente la medida exterior de X ₁ , X ₂ , ..., X _n . Este teorema generaliza el teorema estándar del sándwich de jamón al hacer f ₀ ( x ) = 1 y hacer f _i ( x ) , para i > 0 , que sea la i -ésima coordenada de x .

En geometría discreta , el teorema del sándwich de jamón se refiere generalmente al caso especial en el que cada uno de los conjuntos que se dividen es un conjunto finito de puntos . Aquí, la medida relevante es la medida de conteo , que simplemente cuenta el número de puntos a cada lado del hiperplano. En dos dimensiones, el teorema se puede enunciar de la siguiente manera:

Para un conjunto finito de puntos en el plano, cada uno coloreado de "rojo" o "azul", existe una línea que biseca simultáneamente los puntos rojos y los puntos azules; es decir, el número de puntos rojos a cada lado de la línea es igual y el número de puntos azules a cada lado de la línea también es igual.

Existe un caso excepcional cuando los puntos se encuentran sobre la línea. En esta situación, consideramos que cada punto se encuentra a un lado, al otro o en ninguno de los dos lados de la línea (dependiendo del punto), es decir, "biseca" significa que cada lado contiene menos de la mitad del número total de puntos. Este caso excepcional es necesario para que el teorema se cumpla, por supuesto, cuando el número de puntos rojos o azules es impar, pero también en configuraciones específicas con un número par de puntos, por ejemplo, cuando todos los puntos se encuentran sobre la misma línea y los dos colores están separados entre sí (es decir, los colores no se alternan a lo largo de la línea). Una situación en la que el número de puntos en cada lado no puede coincidir se proporciona añadiendo un punto extra fuera de la línea en la configuración anterior.

En geometría computacional , este teorema del sándwich de jamón conduce a un problema computacional , el problema del sándwich de jamón . En dos dimensiones, el problema es este: dado un conjunto finito de n puntos en el plano, cada uno coloreado de "rojo" o "azul", encontrar un corte de sándwich de jamón para ellos. Primero, Megiddo (1985) describió un algoritmo para el caso especial, separado. Aquí todos los puntos rojos están a un lado de una línea y todos los puntos azules están al otro lado, una situación en la que hay un corte de sándwich de jamón único, que Megiddo pudo encontrar en tiempo lineal. Más tarde, Edelsbrunner y Waupotitsch (1986) dieron un algoritmo para el caso general bidimensional; el tiempo de ejecución de su algoritmo es O ( n log n ) , donde el símbolo O indica el uso de la notación Big O . Finalmente, Lo y Steiger (1990) encontraron un algoritmo óptimo de tiempo O ( n ) . Este algoritmo fue extendido a dimensiones superiores por Lo, Matoušek y Steiger (1994), donde el tiempo de ejecución es${\displaystyle o(n^{d-1})}$Dados d conjuntos de puntos en posición general en un espacio d -dimensional, el algoritmo calcula un hiperplano ( d -1) -dimensional que tiene un número igual de puntos de cada uno de los conjuntos en ambos semiplanos, es decir, un corte de sándwich de jamón para los puntos dados. Si d es parte de la entrada, entonces no se espera que exista un algoritmo de tiempo polinomial , ya que si los puntos están en una curva de momento , el problema se vuelve equivalente a la división de collar , que es PPA-completo .

Stojmenovíc (1991) describe un algoritmo de tiempo lineal que divide por la mitad el área de dos polígonos convexos disjuntos .

El teorema original funciona para como máximo n colecciones, donde n es el número de dimensiones. Para bisecar un mayor número de colecciones sin pasar a dimensiones superiores, se puede usar, en lugar de un hiperplano, una superficie algebraica de grado k , es decir, una superficie ( n -1 )-dimensional definida por una función polinómica de grado k :

Dado${\displaystyle {\binom {k+n}{n}}-1}$medidas en un espacio n -dimensional, existe una superficie algebraica de grado k que las biseca todas. ( Smith & Wormald (1998) ).

Esta generalización se demuestra mapeando el plano n -dimensional en un${\displaystyle {\binom {k+n}{n}}-1}$plano dimensional, y luego aplicando el teorema original. Por ejemplo, para n = 2 y k = 2 , el plano 2-dimensional se transforma en un plano 5-dimensional mediante:

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

• División exacta

• Beyer, WA; Zardecki, Andrew (2004), "La historia temprana del teorema del sándwich de jamón" , American Mathematical Monthly , 111 (1): 58– 61, doi : 10.2307/4145019 , JSTOR 4145019 , ProQuest 203746537  .
• Cairns, Stewart S. (Primavera de 1963), "Redes, sándwiches de jamón y masilla", Pi Mu Epsilon Journal , 3 (8): 389–403 , JSTOR 24338222 .
• Dubins, LE ; Spanier, EH (enero de 1961), "Cómo cortar un pastel de manera justa", American Mathematical Monthly , 68 (1P1): 1–17 , doi : 10.1080/00029890.1961.11989615
• Edelsbrunner, Herbert ; Waupotitsch, R. (1986), "Cálculo de un sándwich de jamón cortado en dos dimensiones", Journal of Symbolic Computation , 2 (2): 171– 178, doi : 10.1016/S0747-7171(86)80020-7.
• Lo, Chi-Yuan; Steiger, WL (1990), "Un algoritmo de tiempo óptimo para cortes de sándwich de jamón en el plano", Actas de la Segunda Conferencia Canadiense sobre Geometría Computacional , págs . 5-9 .
• Lo, Chi-Yuan; Matoušek, Jiří ; Steiger, William L. (1994), "Algoritmos para cortes de sándwich de jamón", Discrete & Computational Geometry , 11 (4): 433– 452, doi : 10.1007/BF02574017.
• Megiddo, Nimrod (1985), "Particionamiento con dos líneas en el plano", Journal of Algorithms , 6 (3): 430– 433, doi : 10.1016/0196-6774(85)90011-2.
• Peters, James V. (Verano de 1981), "El teorema del sándwich de jamón y algunos resultados relacionados", 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), "Teoremas y aplicaciones del separador geométrico", Actas del 39.º Simposio Anual sobre Fundamentos de la Informática (Cat. n.º 98CB36280) , pág.  232, doi : 10.1109/sfcs.1998.743449 , ISBN 0-8186-9172-7, S2CID 17962961 
• Editores (1938), "Notatki: Z topologii", Mathesis Polska (en polaco), 11 ( 1– 2): 26– 28.
• Stone, Arthur H.; Tukey , John W. (1942), "Teoremas generalizados de tipo "sándwich"", Duke Mathematical Journal , 9 (2): 356–359 , doi : 10.1215/S0012-7094-42-00925-6.
• Stojmenovíc, Ivan (1991), "Bisecciones y cortes sándwich de jamón de polígonos y poliedros convexos", Information Processing Letters , 38 (1): 15–21 , doi : 10.1016/0020-0190(91)90209-Z.

• Weisstein, Eric W. , "Teorema del sándwich de jamón" , MathWorld
• Teorema del sándwich de jamón sobre los primeros usos conocidos de algunas palabras de matemáticas
• Cortes de jamón para sándwich por Danielle MacNevin
• Una demostración interactiva en 2D