En la teoría de la medida matemática , para cada entero positivo n, el teorema del sándwich de jamón establece que dados n "objetos" mensurables en un espacio euclidiano de n dimensiones , es posible dividir cada uno de ellos por la mitad (con respecto a su medida , por ejemplo, volumen). con un hiperplano de una sola dimensión ( n − 1) . Esto es posible incluso si los objetos se superponen.
Fue propuesto por Hugo Steinhaus y demostrado por Stefan Banach (explícitamente en la dimensión 3, sin tomarse la molestia de enunciar el teorema en el caso n -dimensional), y también años más tarde se denominó teorema de Stone-Tukey en honor a Arthur H. Stone y John. Turquía .
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 son los ingredientes de un sándwich de jamón . Las fuentes difieren sobre 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 teorema del panqueque para referirse a la naturaleza plana de los dos objetos que serán atravesados 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 dividir tres sólidos con un plano, es una nota de 1938 en una revista de matemáticas 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 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 dividir 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 para que la carne, el hueso y la grasa se corten por la mitad?" Luego, la nota ofrece una prueba 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 entorno 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 y 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 conocida como teorema del panqueque ) puede demostrarse mediante un argumento que aparece en la literatura sobre el corte de pasteles (ver, por ejemplo, el procedimiento de cuchilla giratoria de Robertson-Webb ).
Para cada ángulo , una línea recta ("cuchillo") de ángulo puede dividir el panqueque n.° 1. Para ver esto, traslada [muévete paralelamente] una línea recta de ángulo desde hasta ; la fracción del panqueque #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 del camino. Es posible que toda una gama de traslaciones de nuestra línea produzcan una fracción de 1/2; en este caso, es una elección canónica elegir la del medio de todas esas traducciones.
Cuando el cuchillo está en el ángulo 0, también corta el panqueque n.° 2, pero los trozos probablemente no sean iguales (si tenemos suerte y los trozos son iguales, ya está). Defina 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 describe arriba. Cuando el ángulo es , defínalo como la fracción del panqueque #2 en el lado positivo del cuchillo. Inicialmente . La función es continua, ya que pequeños cambios en el ángulo provocan pequeños cambios en la posición de la cuchilla.
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 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 equivalente , esta prueba se incluiría en el paradigma de espacio de configuración/mapa de pruebas.
Sea A 1 , A 2 , ..., An los n objetos que deseamos bisecar simultáneamente. Sea S la esfera unitaria ( n − 1) incrustada en un espacio euclidiano de n dimensiones , 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 señalado por ese vector (es decir, es una elección de orientación ). Según el teorema del valor intermedio , cada familia de tales hiperplanos contiene al menos un hiperplano que biseca el objeto acotado An : en un extremo de traslación, ningún volumen de An está en el lado positivo, y en el otro extremo de traslación, todo A El volumen de 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 cual An es bisectado. Así obtenemos, para cada punto p de la esfera S , un hiperplano π ( p ) que es perpendicular al vector que va del origen a p y que biseca a An .
Ahora definimos una función f desde la ( n − 1) -esfera S al ( n − 1) -espacio euclidiano dimensional de la siguiente manera:
Esta función f es continua (lo cual, en una prueba formal, necesitaría alguna justificación). Según el teorema de Borsuk-Ulam , existen 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 Ai es el mismo en el lado positivo y negativo de π ( p ) (o π ( q ) ), para i = 1, 2, ... , norte −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 , ..., An .
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 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 , existe 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 bisecta 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 estándar del sándwich de jamón al dejar f ( s , x ) = s 1 x 1 + ... + s n x n .
Su segunda formulación es la siguiente: para cualesquiera n + 1 funciones medibles 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 al hacer que f 0 ( x ) = 1 y dejar 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 generalmente se refiere 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:
Hay un caso excepcional en el que los puntos se encuentran en la recta. 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, "biseccionar" de hecho significa que cada lado contiene menos de la mitad. del número total de puntos. En realidad, este caso excepcional es 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 el número de puntos de cada lado no puede 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 ellos de color "rojo" o "azul", encontrar un sándwich de jamón cortado 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 Megido podría encontrar en tiempo lineal. Posteriormente, Edelsbrunner y Waupotitsch (1986) dieron un algoritmo para el caso bidimensional general; 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 O grande . Finalmente, Lo y Steiger (1990) encontraron un algoritmo óptimo de tiempo O ( n ) . Este algoritmo fue ampliado 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 el mismo número de puntos de cada uno de los conjuntos en sus dos semiespacios, es decir, un jamón -Corte sándwich para los puntos indicados. Si d es parte de la entrada, entonces no se espera que exista ningún algoritmo de tiempo polinómico, ya que si los puntos están en una curva de momento , el problema se vuelve equivalente a la división de collares , que es PPA-completo .
Stojmenovíc (1991) describe un algoritmo de tiempo lineal que biseca dos polígonos convexos disjuntos.
El teorema original funciona para como máximo n colecciones, donde n es el número de dimensiones. Para bisectar un mayor número de colecciones sin pasar a dimensiones superiores, se puede utilizar, 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 :
Dadas medidas en un espacio n –dimensional, existe una superficie algebraica de grado k que las biseca a todas. (Smith y Wormald (1998)).
Esta generalización se prueba mapeando el plano n -dimensional en un plano dimensional y luego aplicando el teorema original. Por ejemplo, para n = 2 y k = 2 , el plano bidimensional se asigna a un plano de 5 dimensiones mediante:
![{\displaystyle \alpha \in [0,180^{\circ }]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59617ac970130c2c27f811f19cb3cf204e47a9d9)
