Problema de rotura del collar

Ejemplo de división de collar con k = 2 (es decir, dos parejas) y t = 2 (es decir, dos tipos de cuentas, en este caso 8 rojas y 6 verdes). Se muestra una división en 2: una pareja recibe la sección más grande y la otra recibe las dos piezas restantes.

La división de collares es un nombre pintoresco que se le da a varios problemas relacionados en combinatoria y teoría de la medida . Su nombre y soluciones se deben a los matemáticos Noga Alon ^[1] y Douglas B. West ^[2] .

El diseño básico consiste en un collar con cuentas de diferentes colores. El collar debe dividirse entre varios socios (por ejemplo, ladrones), de modo que cada socio reciba la misma cantidad de cada color. 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

En el artículo original se han resuelto las siguientes variantes del problema:

1. División discreta : ^{[1] : Th 1.1} El collar tiene cuentas. Las cuentas vienen en diferentes colores. Hay cuentas de cada color , donde es un entero positivo. Divida el collar en partes (no necesariamente contiguas), cada una de las cuales tiene exactamente cuentas de color i . Use como máximo cortes. Tenga en cuenta que si las cuentas de cada color son contiguas en el collar, entonces se deben hacer al menos cortes dentro de cada color, por lo que es óptimo. ${\displaystyle k\cdot n}$ ${\displaystyle t}$ ${\displaystyle k\cdot a_{i}}$ ${\displaystyle i}$ ${\displaystyle a_{i}}$ ${\displaystyle k}$ ${\displaystyle a_{i}}$ ${\displaystyle (k-1)t}$ ${\displaystyle k-1}$ ${\displaystyle (k-1)t}$
2. División continua : ^{[1] : Th 2.1} El collar es el intervalo real . Cada punto del intervalo está coloreado con uno de diferentes colores. Para cada color , el conjunto de puntos coloreados por es medible según el método de Lebesgue y tiene una longitud , donde es un número real no negativo. Particiona el intervalo en partes (no necesariamente contiguas), de modo que en cada parte, la longitud total del color sea exactamente . Utiliza como máximo cortes. ${\displaystyle [0,k\cdot n]}$ ${\displaystyle t}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle k\cdot a_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle a_{i}}$ ${\displaystyle (k-1)t}$
3. División de medidas : ^{[1] : Th 1.2} El collar es un intervalo real. Hay diferentes medidas en el intervalo, todas absolutamente continuas con respecto a la longitud. La medida de todo el collar, según la medida , es . Partición del intervalo en partes (no necesariamente contiguas), de modo que la medida de cada parte, según la medida , sea exactamente . Utilice como máximo cortes. Esta es una generalización del teorema de Hobby-Rice , y se utiliza para obtener una división exacta de un pastel . ${\displaystyle t}$ ${\displaystyle i}$ ${\displaystyle k\cdot a_{i}}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle a_{i}}$ ${\displaystyle (k-1)t}$

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 la que cada intervalo de longitud 1 se colorea con el color de la cuenta correspondiente. En caso de que la división continua intente cortar las cuentas internas, los cortes se pueden deslizar gradualmente de modo que se realicen solo entre las cuentas. ^{[1] : 249} ${\displaystyle [0,k\cdot n]}$
• La división continua se puede resolver mediante la división de medidas, ya que la coloración de un intervalo en colores se puede convertir en un conjunto de medidas, de modo que la medida mide la longitud total del color . Lo opuesto también es cierto: la división de medidas se puede resolver mediante la división continua, utilizando una reducción más sofisticada. ^{[1] : 252–253} ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle i}$ ${\displaystyle i}$

Prueba

El caso puede demostrarse mediante el teorema de Borsuk-Ulam . ^[2] ${\displaystyle k=2}$

Cuando es un número primo impar , la prueba implica una generalización del teorema de Borsuk-Ulam. ^[3] ${\displaystyle k}$

Cuando es un número compuesto , la prueba es la siguiente (demostrada para la variante de división de medidas). Supongamos que . Hay medidas, cada una de las cuales valora el collar entero como . Usando cortes, divide el collar en partes tales que la medida de cada parte sea exactamente . Usando cortes, divide cada parte en partes tales que la medida de cada parte sea exactamente . En total, ahora hay partes tales que la medida de cada parte es exactamente . El número total de cortes es más que es exactamente . ${\displaystyle k}$ ${\displaystyle k=p\cdot q}$ ${\displaystyle t}$ ${\displaystyle p\cdot q\cdot a_{i}}$ ${\displaystyle (p-1)\cdot t}$ ${\displaystyle p}$ ${\displaystyle i}$ ${\displaystyle q\cdot a_{i}}$ ${\displaystyle (q-1)\cdot t}$ ${\displaystyle q}$ ${\displaystyle i}$ ${\displaystyle a_{i}}$ ${\displaystyle pq}$ ${\displaystyle i}$ ${\displaystyle a_{i}}$ ${\displaystyle (p-1)\cdot t}$ ${\displaystyle p(q-1)\cdot t}$ ${\displaystyle (pq-1)\cdot t}$

Resultados adicionales

Dividiendo collares al azar

En algunos casos, los collares al azar se pueden dividir de manera uniforme utilizando menos cortes. Los matemáticos Noga Alon, Dor Elboim, Gábor Tardos y János Pach estudiaron el número típico de cortes necesarios para dividir un collar al azar entre dos ladrones. ^[4] En el modelo que consideraron, se elige un collar de manera uniforme al azar del conjunto de collares con t colores y m cuentas de cada color. A medida que m tiende a infinito, la probabilidad de que el collar se pueda dividir utilizando ⌊(t + 1)/2⌋ cortes o menos tiende a cero, mientras que la probabilidad de que sea posible dividir con ⌊(t + 1)/2⌋ + 1 cortes está acotada desde cero. Más precisamente, siendo X  =  X ( t , m ) el número mínimo de cortes necesarios para dividir el collar. Lo siguiente se cumple cuando m tiende a infinito. Para cualquier ${\displaystyle s<(t+1)/2}$

${\displaystyle \mathbb {P} (X=s)=\Theta {\big (}m^{s-(t+1)/2}{\big )}.}$

Para cualquier ${\displaystyle (t+1)/2<s\leq t}$

${\displaystyle \mathbb {P} (X=s)=\Theta (1).}$

Finalmente, ¿cuándo es impar y ${\displaystyle t}$ ${\displaystyle s=(t+1)/2}$

${\displaystyle \mathbb {P} (X=s)=\Theta {\big (}(\log m)^{-1}{\big )}.}$

También se puede considerar el caso en el que el número de colores tiende a infinito. Cuando m=1 y t tiende a infinito, el número de cortes necesarios es como máximo 0,4t y como mínimo 0,22 t con alta probabilidad. Se conjetura que existe algún 0,22 <  c  < 0,4 tal que X ( t ,1)/ t   converge a c en la distribución.

Un corte menos del 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 t − 1 cortes, el matemático húngaro Gábor Simonyi ^[5] demuestra 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 ninguna división t , entonces para cualesquiera dos subconjuntos D ₁ y D ₂ de { 1, 2, ...,   t  }, no ambos vacíos , tales que , existe una división ( t  − 1) tal que: ${\displaystyle D_{1}\cap D_{2}=\varnothing }$

• Si el color es i , entonces la partición 1 tiene más cuentas del color i que la partición 2; ${\displaystyle i\in D_{1}}$
• Si es de color , entonces la partición 2 tiene más cuentas de color i que la partición 1; ${\displaystyle i\in D_{2}}$
• Si el color i no está en ninguna partición, ambas particiones tienen la misma cantidad de cuentas del color i .

Esto significa que si los ladrones tienen preferencias en forma de dos conjuntos de "preferencias" D ₁ y D ₂ , no ambos vacíos, existe una división ( t  − 1) de modo que el ladrón 1 obtiene más cuentas de los tipos en su conjunto de preferencias D ₁ que el ladrón 2; el ladrón 2 obtiene más cuentas de los tipos en su conjunto de preferencias D ₂ que el ladrón 1; y el resto son iguales.

Simonyi atribuye a Gábor Tardos el haber notado que el resultado anterior es una generalización directa del teorema del collar original de Alon en el caso k = 2. O bien el collar tiene una división ( t  − 1) o no la tiene. Si la tiene, no hay nada que demostrar. Si no la tiene, podemos añadir cuentas de un color ficticio al collar y hacer que D ₁ consista en el color ficticio y D ₂ vacío. Entonces el resultado de Simonyi muestra que hay una división t con cantidades iguales de cada color real.

Resultado negativo

Para cada hay una coloración medible de la línea real tal que ningún intervalo puede dividirse de manera justa utilizando como máximo cortes. ^[6] ${\displaystyle k\geq 1}$ ${\displaystyle (k+3)}$ ${\displaystyle k}$

Partiendo collares multidimensionales

El resultado se puede generalizar a n medidas de probabilidad definidas en un cubo de dimensión d con cualquier combinación de n ( k  − 1) hiperplanos paralelos a los lados para k ladrones. ^[7]

Algoritmo de aproximación

Un algoritmo de aproximación para dividir un collar se puede derivar de un algoritmo de consenso para dividirlo a la mitad . ^[8]

Véase también

• Collar combinatorio
• Problema del collar
• División exacta

Referencias

1. Alon, Noga (1987). "Dividiendo collares". Avances en Matemáticas . 63 (3): 247–253. doi : 10.1016/0001-8708(87)90055-7 .
2. Alon, Noga; West, Douglas B. (diciembre de 1986). "El teorema de Borsuk-Ulam y la bisección de collares" . Actas de la American Mathematical Society . 98 (4): 623–628. doi : 10.1090/s0002-9939-1986-0861764-9 .
3. I. Barany y S. B. Shlosman 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. 
4. Alón, Noga; Elboim, Dor; Tardos, Gábor; Pach, János (2021). "Los collares aleatorios requieren menos cortes". arXiv : 2112.14488 [matemáticas.CO].
5. Simonyi, Gábor (2008). "Bisección de collar con un corte menos del necesario". Revista Electrónica de Combinatoria . 15 (N16). doi : 10.37236/891 .
6. Alon, Noga (25 de noviembre de 2008). "Collares de división y coloraciones mensurables 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.
7. de Longueville, Mark; Rade T. Živaljević (2008). "Dividiendo collares multidimensionales". Avances en Matemáticas . 218 (3): 926–939. arXiv : math/0610800 . doi : 10.1016/j.aim.2008.02.003 .
8. Simmons, bosque W.; Su, Francis Edward (febrero de 2003). "Reducción del consenso a la mitad mediante 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

• "Sneaky Topology" en YouTube, un vídeo introductorio que presenta el problema con su solución topológica.