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, el 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 tomarse la molestia de enunciar el teorema en el caso n -dimensional), y también años más tarde llamado 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 el que n = 3 y los tres objetos que se van a dividir en dos son los ingredientes de un sándwich de jamón . Las fuentes difieren en cuanto a 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 que se van a dividir en dos por una línea (Cairns 1963).
Según Beyer y Zardecki (2004), el artículo más antiguo 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 de matemáticas polaca (Editors 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 acredita a Stefan Banach como el primero en resolver el problema, 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 un cortador de carne de modo que la carne, el hueso y la grasa se corten en mitades?" La nota luego ofrece una prueba del teorema.
Una referencia más moderna es Stone & 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 árbitro; pero Beyer & Zardecki (2004) afirman que esto es incorrecto, dada la nota mencionada anteriormente, aunque "Ulam hizo una contribución fundamental al proponer" el teorema de Borsuk-Ulam .
La variante bidimensional del teorema (también conocido como teorema del panqueque ) se puede demostrar mediante un argumento que aparece en la literatura sobre corte de tortas (véase, por ejemplo, el procedimiento de cuchillo giratorio de Robertson-Webb ).
Para cada ángulo , una línea recta ("cuchillo") de ángulo puede dividir en dos el panqueque n.° 1. Para ver esto, traslade a lo largo de su normal una línea recta de ángulo de a ; la fracción del panqueque n.° 1 cubierta por la línea cambia continuamente de 0 a 1, por lo que, por el teorema del valor intermedio, debe ser igual a 1/2 en algún punto del camino. Es posible que un rango completo de traslaciones de nuestra línea dé como resultado una fracción de 1/2; en este caso, es una elecció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). Definamos 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 , definamos como la fracción del panqueque n.° 2 en el lado positivo del cuchillo. Inicialmente . La función es continua, ya que pequeños cambios en el ángulo conducen a pequeños cambios en la posición del cuchillo.
Cuando el cuchillo está en un ángulo de 180°, está boca abajo, por lo que . Según el teorema del valor intermedio , debe haber un ángulo en el que . Cortar en ese ángulo divide en dos ambos panqueques simultáneamente.
El teorema del sándwich de jamón se puede demostrar de la siguiente manera utilizando el teorema de Borsuk-Ulam . Esta prueba 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 prueba caería bajo el paradigma del espacio de configuración/mapa de pruebas.
Sea A 1 , A 2 , ..., A n los n objetos que deseamos bisecar simultáneamente. Sea S la esfera unitaria ( n − 1) incrustada en el espacio euclidiano n -dimensional , centrada en el origen . Para cada punto p en la superficie de la esfera S , podemos definir un continuo de hiperplanos afines orientados (no necesariamente centrados en 0) perpendiculares al vector ( normal ) desde el origen hasta p , con el "lado positivo" de cada hiperplano definido como el lado al que apunta ese vector (es decir, es una elección de orientación ). Por el teorema del valor intermedio , cada familia de tales hiperplanos contiene al menos un hiperplano que biseca el objeto 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 en el medio debe haber una traslación que tenga la mitad del volumen de A n en el lado positivo. Si hay más de un hiperplano de este tipo en la familia, podemos elegir uno canónicamente eligiendo el punto medio del intervalo de traslaciones para el que A n está bisecado. Así obtenemos, para cada punto p en la esfera S , un hiperplano π ( p ) que es perpendicular al vector desde el origen a p y que biseca A n .
Ahora definimos una función f desde la ( n − 1) -esfera S al espacio euclidiano de ( n − 1) -dimensional de la siguiente manera:
Esta función f es continua (lo que, en una prueba formal, necesitaría alguna justificación). Por el teorema de Borsuk-Ulam , hay puntos antípodas p y q en la esfera S tales que f ( p ) = f ( q ) . Los puntos antípodas p y q corresponden a hiperplanos π ( p ) y π ( q ) que son iguales excepto que tienen lados positivos opuestos. Por lo tanto, f ( p ) = f ( q ) significa que el volumen de A i es el mismo en el lado positivo y negativo de π ( p ) (o π ( q ) ), para i = 1, 2, ..., n −1 . Por lo tanto, π ( p ) (o π ( q ) ) es el corte de sándwich de jamón deseado que biseca simultáneamente los volúmenes de A 1 , A 2 , ..., 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 1 , X 2 , ..., X n de un conjunto común X , donde X tiene una medida externa de Carathéodory y cada X i tiene una medida externa finita.
Su primera formulación general es la siguiente: para cualquier función real continua , hay un punto p de la n - esfera S n y un número real s 0 tal que la superficie f ( p , x ) = s 0 divide a X en f ( p , x ) < s 0 y f ( p , x ) > s 0 de igual medida y simultáneamente biseca la medida exterior de X 1 , X 2 , ..., X n . La prueba es nuevamente una reducción al teorema de Borsuk-Ulam. Este teorema generaliza el teorema del sándwich de jamón estándar al hacer f ( s , x ) = s 1 x 1 + ... + s n x n .
Su segunda formulación es la siguiente: para cualesquiera n + 1 funciones mensurables f 0 , f 1 , ..., f n sobre X que sean linealmente independientes sobre cualquier subconjunto de X de medida positiva, existe una combinación lineal f = a 0 f 0 + a 1 f 1 + ... + a n f n tal que la superficie f ( x ) = 0 , dividiendo X en f ( x ) < 0 y f ( x ) > 0 , biseca simultáneamente la medida exterior de X 1 , X 2 , ..., X n . Este teorema generaliza el teorema estándar del sándwich de jamón haciendo que f 0 ( x ) = 1 y haciendo que f i ( x ) , para i > 0 , sea la i -ésima coordenada de x .
En geometría discreta y geometría computacional , el teorema del sándwich de jamón suele referirse 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 puede enunciarse de la siguiente manera:
Existe un caso excepcional en el que los puntos se encuentran en la línea. En esta situación, contamos cada uno de estos puntos como si estuvieran en un lado, en el otro o en ninguno de los lados de la línea (posiblemente dependiendo del punto), es decir, "bisecar" de hecho significa que cada lado contiene menos de la mitad del número total de puntos. Este caso excepcional es realmente necesario para que el teorema se cumpla, por supuesto cuando el número de puntos rojos o el número de puntos azules es impar, pero también en configuraciones específicas con números pares de puntos, por ejemplo, cuando todos los puntos se encuentran en 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 los números de puntos en cada lado no pueden coincidir entre sí se proporciona agregando un punto adicional 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 el siguiente: dado un conjunto finito de n puntos en el plano, cada uno de color "rojo" o "azul", encuentre 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 en un lado de alguna línea y todos los puntos azules están en el otro lado, una situación en la que hay un corte de sándwich de jamón único, que Megiddo podría 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 . 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 de sus semiespacios, es decir, un corte de sándwich de jamón para los puntos dados. Si d es una 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 del collar , que es PPA-completo .
Stojmenovíc (1991) describe un algoritmo de tiempo lineal que divide en dos el área de dos polígonos convexos disjuntos.
El teorema original funciona para un máximo de n conjuntos, donde n es el número de dimensiones. Para bisecar un mayor número de conjuntos sin pasar a dimensiones superiores, se puede utilizar, en lugar de un hiperplano, una superficie algebraica de grado k , es decir, una superficie de ( n −1 ) dimensiones definida por una función polinómica de grado k :
Dadas medidas en un espacio n -dimensional, existe una superficie algebraica de grado k que las divide en dos. (Smith y Wormald (1998)).
Esta generalización se demuestra al convertir el plano n -dimensional en un plano dimensional y luego aplicar el teorema original. Por ejemplo, para n = 2 y k = 2 , el plano bidimensional se convierte en un plano de cinco dimensiones mediante:
![{\displaystyle \alpha \en [0,180^{\circ }]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59617ac970130c2c27f811f19cb3cf204e47a9d9)
