El teorema del sándwich

El teorema del sándwich establece que, dados n "objetos" medibles en un espacio euclidiano de n dimensiones , pueden dividirse en dos (según su medida , es decir, el volumen) por un solo hiperplano ( n − 1) dimensional .

La afirmación fue hecha por Hugo Steinhaus y probada por Stefan Banach (en dimensión tres, sin asumir una extensión automática del teorema al caso n-dimensional), y un año más tarde la afirmación se denominó teorema de Stone-Tukey en honor a Arthur G. Stone y John Tukey .

Título

El teorema del sándwich recibe su nombre del caso cuando n = 3 y los tres objetos de cualquier forma son una loncha de jamón y dos rebanadas de pan . Relativamente hablando, un sándwich , que se puede dividir simultáneamente por un corte (es decir, por un plano ). En dimensión dos, el teorema se conoce como teorema del panqueque , ya que consiste en cortar un panqueque infinitamente delgado en dos mitades con un solo corte (es decir, una línea recta ).

Historia

Según Bayer y Szardecki [1] , el artículo más antiguo sobre el teorema del sándwich, es decir, para el caso de n = 3 cortes de tres cuerpos por un plano, es el artículo de Steinhaus [2] . El artículo de Bayer y Szardecki incluye una traducción del artículo de 1938. El artículo atribuye el planteamiento del problema a Hugo Steinhaus y afirma que Stefan Banach fue el primero en resolver el problema por reducción al teorema de Borsuk-Ulam . El artículo presenta el problema de dos maneras. El primero es formal: "¿Es siempre posible dividir tres cuerpos ubicados arbitrariamente por un plano?". La segunda, informal: "¿Podemos poner un trozo de jamón debajo del cuchillo para que la carne, el hueso y la grasa se partan por la mitad con el cuchillo?" El artículo ofrecía una demostración del teorema.

Un artículo más reciente es el artículo de Stone y Tukey [3] , que dio su nombre al "teorema de Stone-Tukey". Este artículo prueba la versión n -dimensional del teorema bajo condiciones de medida más generales. El artículo atribuye el caso n = 3 a Stanisław Ulam , basado en su propia información, pero Bayer y Zzardecki [1] argumentan que esto es falso, apuntando al artículo de Steinhaus, aunque estipulan: "Ulam hizo una contribución fundamental a la prueba de el ' teorema de Borsuk-Ulam '".

Versión bidimensional: prueba usando el "cuchillo móvil"

Se puede demostrar una versión bidimensional del teorema (también conocido como el teorema del panqueque ) usando argumentos que aparecen en la literatura sobre el problema de cortar un pastel justo (ver, por ejemplo, Procedimiento de cuchillo en movimiento de Robertson-Webb ).

Para cualquier ángulo , podemos cortar el panqueque No. 1 con una línea recta en ángulo (para ver esto, moveremos la línea recta en ángulo de a . La fracción del panqueque No. 1 cortado por una línea recta cambia continuamente de 0 a 1, por lo que por el valor del teorema intermedio , debe tomar el valor 1/2 en alguna parte). ${\ estilo de visualización \ alfa \ en [0,180 ^ {\ circ}]}$ $\alfa$ $\alfa$ $-\infty$ $\infty$

Esto significa que podemos tomar un cuchillo recto y girarlo en un ángulo , moviéndolo paralelo a la distancia requerida, de modo que el panqueque #1 siempre se corte por la mitad para cualquier ángulo. ${\ estilo de visualización \ alfa \ en [0,180 ^ {\ circ}]}$

Cuando el cuchillo está en un ángulo de 0, también corta el panqueque #2, pero sus partes pueden no ser iguales (si tuvimos suerte y las partes fueron iguales, hicimos nuestro trabajo). Definámoslo como el lado "positivo" del cuchillo, con el que la proporción de la tortita N° 2 es mayor. Lo definimos como la parte del panqueque No. 2 en el lado positivo del cuchillo. inicialmente _ ${\ estilo de visualización p (\ alfa)}$ ${\ estilo de visualización p (0) \ geqslant 1/2}$

Cuando el cuchillo gire 180, estará en el mismo lugar, pero al revés, así que . De acuerdo con el teorema del valor intermedio , debe haber un ángulo en el que . Cortar con este ángulo de hoja cortará ambos panqueques por la mitad al mismo tiempo. $p(180)\leqslant 1/2$ ${\ estilo de visualización p (\ alfa) = 1/2}$

Versión n -dimensional: prueba usando el teorema de Borsuk-Ulam

El teorema del sándwich se puede probar de la siguiente manera usando el teorema de Borsuk-Ulam . La demostración dada sigue a la dada por Steinhaus y otros en el artículo de 1938, atribuido allí a Stefan Banach , para el caso n =3 . En el campo de la topología equivariante , esta prueba corresponde al paradigma espacio de configuración/espacio de prueba-mapa.

Denotemos n objetos que queremos dividir en dos al mismo tiempo. Sea S una esfera unitaria ( n − 1 ) incrustada en un espacio euclidiano de n - dimensiones y centrada en el origen . Para cada punto p en la superficie de la esfera S , podemos definir un continuo hiperplanos afines orientados (no necesariamente a través del centro 0) perpendiculares ( la normal ) a un vector desde el origen en p , con el "positivo side" de cada hiperplano definido como el lado al que apunta el vector (es decir, es la elección de la orientación ). Por el teorema del teorema del valor intermedio, cualquier familia de tales hiperplanos contiene al menos un hiperplano que biseca un objeto acotado - con una traslación extrema, no habrá volumen y en el lado positivo, pero con una traslación extrema en la otra dirección , todo el volumen estará en el lado positivo, por lo que entre estos extremos debe haber una transferencia, que tenga la mitad del volumen en el lado positivo . Si hay más de uno de estos hiperplanos, podemos elegir uno como el punto medio del intervalo bisect-carry . Así, obtenemos para cada punto p de la esfera S un hiperplano , que es perpendicular al vector desde el origen hasta el punto p y que biseca a . ${\displaystyle A_{1},A_{2},\puntos,A_{n))$ $\mathbb{R} ^{n}$ $Un}$ $Un}$ $Un}$ $Un}$ ${\ estilo de visualización \ pi (p)}$ $Un}$

Ahora definimos una función f de la ( n − 1) -esfera S en el ( n − 1) -espacio euclidiano dimensional de la siguiente manera: ${\ estilo de visualización \ mathbb {R} ^ {n-1}}$

{\ estilo de visualización f (p) = (V_ {1}, V_ {2}, \ puntos, V_ {n})}

donde es igual al volumen en el lado positivo . Esta función f es continua . Por el teorema de Borsuk-Ulam , existen puntos antípodas p y q en la esfera S tales que . Los puntos antípodas p y q corresponden a los hiperplanos y , que son iguales excepto por la orientación del lado positivo. Entonces significa que el volumen es el mismo en los lados positivo y negativo (o ), para i =1, 2, …, n −1 . Así, (o ) es el corte requerido del sándwich, dividiendo los volúmenes por la mitad . $V_{k}$ $Alaska$ ${\ estilo de visualización \ pi (p)}$ ${\ estilo de visualización f (p) = f (q)}$ ${\ estilo de visualización \ pi (p)}$ ${\ estilo de visualización \ pi (q)}$ ${\ estilo de visualización f (p) = f (q)}$ $Ai}$ ${\ estilo de visualización \ pi (p)}$ ${\ estilo de visualización \ pi (q)}$ ${\ estilo de visualización \ pi (p)}$ ${\ estilo de visualización \ pi (q)}$ ${\displaystyle A_{1},A_{2},\puntos,A_{n))$

Versiones en teoría de la medida

En la teoría de la medida, Stone y Tukey [3] demostraron dos formas más generales del teorema del sándwich. Ambas versiones tratan sobre la bisección de un n subconjunto de un conjunto común X , donde X tiene una medida exterior de Carathéodory , y cada subconjunto tiene una medida exterior finita. ${\displaystyle X_{,}X_{2},\puntos,X_{n))$ $X_{yo}$

Su primera formulación generalizada es la siguiente: para cualquier función real propiamente acotada, existe un punto p n -esfera tal que la superficie divide el conjunto X por y simultáneamente biseca la medida exterior . La demostración se realiza de nuevo por reducción al teorema de Borsuk-Ulam. Este teorema generaliza el teorema del sándwich estándar al asumir . $f\colon S^{n}\times X\to \mathbb {R}$ $S^{n}$ ${\ estilo de visualización f (s, x) = 0}$ ${\ estilo de visualización f (s, x) <0}$ ${\ estilo de visualización f (s, x)> 0}$ ${\displaystyle X_{1},X_{2},\puntos,X_{n))$ ${\displaystyle f(s,x)=s_{0}+s_{1}x_{1}+\dots +s_{n}x_{n))$

Su segunda formulación generalizada es la siguiente: para cualesquiera n + 1 funciones medibles en X que sean linealmente independientes en cualquier subconjunto de X de medida positiva, existe una combinación lineal tal que una secuencia que divide X por f ( x ) < 0 y f ( x ) > 0 , biseca simultáneamente las medidas exteriores . Este teorema generaliza el teorema del sándwich estándar, donde , y para i > 0 es la i -ésima coordenada del vector x . ${\displaystyle f_{0},f_{1},\puntos,f_{n))$ ${\displaystyle f=a_{0}f_{0}+a_{1}f_{1}+\puntos +a_{n}f_{n))$ $f(x)=0$ ${\displaystyle X_{1},X_{2},\puntos,X_{n))$ ${\ estilo de visualización f_ {0} (x) = 1}$ $arreglar)$

Versiones en geometría discreta y computacional

En geometría combinatoria y computacional , el teorema del emparedado generalmente se refiere al caso especial donde cada uno de los conjuntos a dividir es un conjunto finito de puntos . Aquí la medida más apropiada es la medida de conteo , que cuenta el número de puntos en un lado del hiperplano. En la dimensión dos, el teorema se puede formular de la siguiente manera:

Para un conjunto finito de puntos en el plano, pintados en colores "rojo" y "azul", hay una línea que biseca simultáneamente los puntos rojos y los puntos azules, es decir, el número de puntos rojos en cada lado de la línea es lo mismo y lo mismo es cierto para los puntos azules.

Hay una excepción cuando los puntos se encuentran en una línea. En este caso, consideramos que cada uno de estos puntos se encuentra en un lado o en el otro, o en ninguno de los lados de la línea (esto puede depender del punto), es decir, "reducir a la mitad" en realidad significa que cada lado contiene menos de la mitad del número total de puntos. Se requiere este caso excepcional 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 ciertas configuraciones con un número par de puntos, por ejemplo, cuando todos los puntos están en la misma línea y los dos colores están separados entre sí (no intercalados a lo largo de la línea). La situación en la que el número de puntos de cada lado no coincide se soluciona añadiendo puntos adicionales fuera de la línea.

En geometría computacional, este teorema del sándwich conduce al problema computacional del sándwich de jamón . En la versión bidimensional, el problema es el siguiente: dado un conjunto finito de n puntos en el plano, pintados en colores "rojo" y "azul", encontrar para ellos un corte de sándwich de jamón. Megiddo [4] describió por primera vez el algoritmo para un caso especial separado. Aquí todos los puntos rojos se encuentran en un lado de alguna línea, y todos los puntos azules se encuentran en el otro lado de la misma línea. En esta situación, existe el único corte de sándwich de jamón que Meguido pudo encontrar en tiempo lineal. Posteriormente, Edelsbrunner y Wapotich [5] dieron un algoritmo para el caso bidimensional general. El tiempo de ejecución de su algoritmo es , donde el símbolo O significa O-grande . Finalmente, Lo y Steiger [6] encontraron un algoritmo óptimo con tiempo de ejecución O ( n ) . Este algoritmo fue extendido a grandes dimensiones por Lo, Matushek y Steiger [7] y el tiempo de ejecución del algoritmo es . Dados d puntos en una posición común en un espacio d -dimensional, el algoritmo calcula un hiperplano ( d − 1) -dimensional que tiene el mismo número de puntos en cada uno de los semiespacios, es decir, da un corte de sándwich de jamón para el puntos dados. Si se incluye d en la entrada, entonces no se espera un algoritmo de tiempo polinomial, ya que en el caso de que los puntos se encuentren en la curva de momento , el problema se vuelve equivalente a cortar el collar , que es PPA-hard . $O(n\log n)$ $o(n^{d-1})$

Stoimenovic [8] describió un algoritmo de tiempo lineal que divide dos polígonos convexos que no se intersecan .

Generalizaciones

El teorema original funciona como máximo para n colecciones, donde n es el número de dimensiones. Si queremos particionar más colecciones sin entrar en dimensiones más altas, podemos usar una superficie algebraica de grado k en lugar de un hiperplano , es decir, una superficie ( n − 1 )-dimensional definida por una función polinomial de grado k :

Dadas las medidas en un espacio de n dimensiones, existe una superficie algebraica de grado k que las biseca a todas [9] . ${\binom {k+n}{n}}-1$

Esta generalización se prueba transformando un plano n - dimensional en un plano - dimensional y luego aplicando el teorema original. Por ejemplo, para n =2 y k =2 , un plano de 2 dimensiones se asigna a un plano de 5 dimensiones: ${\binom {k+n}{n}}-1$

{\ estilo de visualización (x, y) \ a (x, y, x ^ {2}, y ^ {2}, xy)}

Véase también

división exacta

Literatura

Beyer WA, Andrew Zardecki. La historia temprana del teorema del sándwich de jamón // American Mathematical Monthly . - 2004. - T. 111 , núm. 1 . — págs. 58–61 . -doi : 10.2307/ 4145019 . . _
Herbert Edelsbrunner, Waupotitsch R. Cálculo de un sándwich de jamón cortado en dos dimensiones // Journal of Symbolic Computation. - 1986. - Vol. 2 , número. 2 . — S. 171–178 . - doi : 10.1016/S0747-7171(86)80020-7 .
Chi-Yuan Lo, Steiger WL 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. - 1990. - S. 5–9.
Chi-Yuan Lo, Jiri Matousek, William L. Steiger. Algoritmos para Cortes de Sándwich de Jamón // Geometría Discreta y Computacional . - 1994. - T. 11 , núm. 4 . — S. 433–452 . -doi : 10.1007/ BF02574017 .
Nimrod Megido. Particionamiento con dos líneas en el plano // Journal of Algorithms. - 1985. - T. 6 , núm. 3 . — S. 430–433 . - doi : 10.1016/0196-6774(85)90011-2 .
Smith WD, Wormald NC Teoremas y aplicaciones del separador geométrico // Actas del 39º Simposio Anual sobre Fundamentos de Ciencias de la Computación (Cat. No.98CB36280). - 1998. - S. 232. - ISBN 0-8186-9172-7 . -doi : 10.1109/ sfcs.1998.743449 .
Hugo Steinhaus . Una nota sobre el teorema del sándwich de jamón // Mathesis Polska. - 1938. - T. 9 . — P. 26–28 .
Arthur Harold Piedra, John W. Tukey. Teoremas generalizados del "sándwich" // Duke Mathematical Journal . - 1942. - T. 9 , núm. 2 . — S. 356–359 . -doi : 10.1215/ S0012-7094-42-00925-6 .
Iván Stojmenovic. Bisecciones y cortes en sándwich de jamón de polígonos convexos y poliedros. // información Tramitación Letts.. - 1991. - T. 38 . — P. 15–21 . -doi : 10.1016 / 0020-0190(91)90209-Z .

• Biblioteca "Caleidoscopio matemático" de Hugo Steinhaus • Kvant • número 8 traducido del polaco por F.L. Varpakhovsky Moscú "Ciencia" Edición principal de literatura física y matemática 1981

Enlaces

Weisstein, Eric W. Ham Sandwich Theorem (inglés) en el sitio web de Wolfram MathWorld .
Teorema del sándwich de jamón sobre los primeros usos conocidos de algunas de las palabras de las matemáticas
Cortes de sándwich de jamón por Danielle MacNevin
Una demostración 2D interactiva