La división de collares es un nombre pintoresco que se le da a varios problemas relacionados en la combinatoria y la teoría de la medida . Su nombre y sus soluciones se deben a los matemáticos Noga Alon [1] y Douglas B. West . [2]
El escenario básico consiste en un collar con cuentas de diferentes colores. El collar debe dividirse entre varios socios, de modo que cada socio reciba la misma cantidad de todos los colores. Además, el número de cortes debe ser lo más pequeño posible (para desperdiciar la menor cantidad posible de metal en los eslabones entre las cuentas).
Variantes
Las siguientes variantes del problema se han resuelto en el documento original:
- División discreta : [1] : Th 1.1 El collar tienerosario. Las cuentas entranColores diferentes. Existen cuentas de cada color , dónde es un número entero positivo. Divide el collar en partes (no necesariamente contiguas), cada una de las cuales tiene exactamente perlas de color i . Usar como máximocortes. Tenga en cuenta que si las cuentas de cada color son contiguas en el collar, al menos los cortes deben hacerse dentro de cada color, por lo que es óptimo.
- División continua : [1] : Th 2.1 El collar es el intervalo real. Cada punto del intervalo está coloreado en uno deColores diferentes. Para cada color, el conjunto de puntos coloreados por es medible en Lebesgue y tiene una longitud, dónde es un número real no negativo. Particione el intervalo para partes (no necesariamente contiguas), de modo que en cada parte, la longitud total del color es exactamente . Usar como máximo cortes.
- Medida de división : [1] : Th 1.2 El collar es un intervalo real. Existendiferentes medidas en el intervalo, todas absolutamente continuas con respecto a la longitud. La medida de todo el collar, según medida., es . Particione el intervalo para partes (no necesariamente contiguas), de modo que la medida de cada parte, según medida , es exactamente . Usar como máximocortes. Esta es una generalización del teorema de Hobby-Rice y se usa para obtener una división exacta de un pastel .
Cada problema puede resolverse con el siguiente problema:
- La división discreta se puede resolver mediante la división continua, ya que un collar discreto se puede convertir en una coloración del intervalo real. en el que cada intervalo de longitud 1 está coloreado por el color de la cuenta correspondiente. En caso de que la división continua intente cortar el interior de las cuentas, los cortes se pueden deslizar gradualmente de modo que se hagan solo entre las cuentas. [1] : 249
- La división continua se puede resolver dividiendo la medida, ya que una coloración de un intervalo en los colores se pueden convertir en un conjunto medidas, tales que miden mide la longitud total del color . Lo contrario también es cierto: la división de medidas se puede resolver mediante una división continua, utilizando una reducción más sofisticada. [1] : 252–253
Prueba
El caso puede demostrarse mediante el teorema de Borsuk-Ulam . [2]
Cuándo es un número primo impar , la demostración implica una generalización del teorema de Borsuk-Ulam. [3]
Cuándo es un número compuesto , la prueba es la siguiente (demostrada para la variante de división de medidas). Suponer. Existen medidas, cada una de las cuales valora todo el collar como . Utilizando cortes, divide el collar para partes tales que miden de cada parte es exactamente . Utilizando cortes, divida cada parte para partes tales que miden de cada parte es exactamente . En general, ahora hay partes tales que miden de cada parte es exactamente . El número total de cortes es más que es exactamente .
Resultados adicionales
Un corte menos de lo necesario
En el caso de dos ladrones [es decir, k = 2] y t colores, una división justa requeriría como máximo t cortes. Sin embargo, si solo se dispone de cortes t - 1, el matemático húngaro Gábor Simonyi [4] muestra que los dos ladrones pueden lograr una división casi justa en el siguiente sentido.
Si el collar está dispuesto de manera que no sea posible una división en t , entonces para dos subconjuntos cualesquiera D 1 y D 2 de {1, 2, ..., t }, no ambos vacíos , de modo que, existe una división ( t - 1) tal que:
- Si el color , entonces la partición 1 tiene más perlas de color i que la partición 2;
- Si el color , entonces la partición 2 tiene más perlas de color i que la partición 1;
- Si el color i no está en ninguna de las particiones, ambas particiones tienen el mismo número de cuentas de color i .
Esto significa que si los ladrones tienen preferencias en forma de dos conjuntos de "preferencias" D 1 y D 2 , no ambos vacíos, existe una división ( t - 1) para que el ladrón 1 obtenga más cuentas de tipos en su conjunto de preferencias. D 1 que ladrón 2; el ladrón 2 obtiene más cuentas de tipos en su conjunto de preferencias D 2 que el ladrón 1; y el resto son iguales.
Simonyi le da crédito a Gábor Tardos por notar que el resultado anterior es una generalización directa del teorema del collar original de Alon en el caso k = 2. O el collar tiene una división ( t - 1), o no la tiene. Si es así, no hay nada que probar. Si no es así, podemos agregar cuentas de un color ficticio al collar y hacer que D 1 consista en el color ficticio y D 2 vacío. Entonces el resultado de Simonyi muestra que hay una división en t con números iguales de cada color real.
Resultado negativo
Para cada hay un medible -coloración de la línea real de modo que ningún intervalo pueda dividirse equitativamente utilizando como máximo cortes. [5]
División de collares multidimensionales
El resultado se puede generalizar en n medidas de probabilidad definidas en un cubo dimensional d con cualquier combinación de n ( k - 1) hiperplanos paralelos a los lados para k ladrones. [6]
Algoritmo de aproximación
Se puede derivar un algoritmo de aproximación para dividir un collar a partir de un algoritmo para reducir a la mitad por consenso . [7]
Ver también
Referencias
- ↑ a b c d e f Alon, Noga (1987). "Collares partidos" . Avances en Matemáticas . 63 (3): 247-253. doi : 10.1016 / 0001-8708 (87) 90055-7 .
- ^ a b Alon, Noga; West, DB (diciembre de 1986). "El teorema de Borsuk-Ulam y bisección de collares" . Actas de la American Mathematical Society . 98 (4): 623–628. doi : 10.1090 / s0002-9939-1986-0861764-9 .
- ^ I.Barany y SBShlosman y A.Szucs (1981). "Sobre una generalización topológica de un teorema de Tverberg". Revista de la Sociedad Matemática de Londres . 2 (23): 158-164. CiteSeerX 10.1.1.640.1540 . doi : 10.1112 / jlms / s2-23.1.158 .
- ^ Simonyi, Gábor (2008). "Bisección del collar con un corte menos del necesario" . Revista electrónica de combinatoria . 15 (N16). doi : 10.37236 / 891 .
- ^ Alon, Noga (25 de noviembre de 2008). "Collares partidos y coloraciones medibles de la línea real". Actas de la American Mathematical Society . 137 (5): 1593-1599. arXiv : 1412.7996 . doi : 10.1090 / s0002-9939-08-09699-8 . ISSN 1088-6826 .
- ^ de Longueville, Mark; Rade T. Živaljević (2008). "Partiendo collares multidimensionales". Avances en Matemáticas . 218 (3): 926–939. arXiv : matemáticas / 0610800 . doi : 10.1016 / j.aim.2008.02.003 .
- ^ Simmons, Forest W .; Su, Francis Edward (febrero de 2003). "Consenso-reducción a la mitad a través de teoremas de Borsuk-Ulam y Tucker". Ciencias Sociales Matemáticas . 45 (1): 15-25. CiteSeerX 10.1.1.203.1189 . doi : 10.1016 / s0165-4896 (02) 00087-2 .
enlaces externos
- "Topología Sneaky" en YouTube, un video introductorio que presenta el problema con su solución topológica.