Problema de división del collar

Ejemplo de división de collar con k = 2 (es decir, dos socios) y t = 2 (es decir, dos tipos de cuentas, aquí 8 rojas y 6 verdes). Se muestra una división en 2: un socio recibe la sección más grande y el otro 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 marco 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 uno 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 enlaces 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 número entero positivo. Divida el collar en partes (no necesariamente contiguas), cada una de las cuales tenga exactamente cuentas del color i . Usar en la mayoría de los cortes. Tenga en cuenta que si las cuentas de cada color son contiguas en el collar, entonces al menos se deben hacer cortes dentro de cada color, lo cual 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 Lebesgue y tiene longitud , donde es un número real no negativo. Divida el intervalo en partes (no necesariamente contiguas), de modo que en cada parte, la longitud total del color sea exactamente . Usar en la mayoría de los 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 medida : ^{[1] : Th 1.2} El collar es un intervalo real. Existen diferentes medidas sobre el intervalo, todas absolutamente continuas respecto a la longitud. La medida de todo el collar, según medida , es de . Divida el intervalo en partes (no necesariamente contiguas), de modo que la medida de cada parte, según la medida , sea exactamente . Usar en la mayoría de los 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 se puede resolver 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 realicen sólo 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 una coloración de un intervalo en colores se puede convertir en medidas establecidas, de modo que la medida mida 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} ${\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 demostración 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). Suponer . Hay medidas, cada una de las cuales valora el collar completo como . Usando cortes, divida el collar en partes de modo que la medida de cada parte sea exactamente . Usando cortes, divida cada parte en partes de manera que la medida de cada parte sea exactamente . Con todo, ahora hay partes cuyas medidas son exactamente iguales . 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}$

Otros resultados

Dividiendo collares al azar

En algunos casos, los collares aleatorios se pueden dividir en partes iguales 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 uniformemente al azar un collar del conjunto de collares con t colores y m cuentas de cada color. Como m tiende al infinito, la probabilidad de que el collar se pueda dividir usando ⌊(t + 1)/2⌋ cortes o menos tiende a cero, mientras que la probabilidad de que sea posible dividirlo con ⌊(t + 1)/2⌋ + 1 los cortes están acotados desde cero. Más precisamente, sea 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, cuando 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 requeridos es como máximo 0,4 t y al menos 0,22 t con alta probabilidad. Se conjetura que existe algo de 0,22 <  c  < 0,4 tal que X ( t ,1)/ t   converge a c en la distribución.

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 sólo  se dispone de cortes t − 1, el matemático húngaro Gábor Simonyi ^[5] muestra que los dos ladrones pueden realizar una división casi justa en el siguiente sentido.

Si el collar está dispuesto de manera que no sea posible una división t , entonces, para dos subconjuntos cualesquiera D ₁ y D ₂ de { 1, 2, ...,   t  }, no ambos están vacíos , de modo que a ( t  − 1) -split existe tal que: ${\displaystyle D_{1}\cap D_{2}=\varnothing }$

• Si el color es , entonces la partición 1 tiene más cuentas de color i que la partición 2; ${\displaystyle i\in D_{1}}$
• Si el color es , 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 de las particiones, ambas particiones tienen la misma cantidad de cuentas de 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 obtenga más cuentas de tipos en su conjunto de preferencias. D ₁ que ladrón 2; el ladrón 2 obtiene más cuentas de tipos en su conjunto de preferencias D ₂ 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. Si es así, no hay nada que demostrar. Si no es así, podemos agregar cuentas de un color ficticio al collar y hacer que D ₁ esté formado por el color ficticio y D ₂ vacío. Entonces el resultado de Simonyi muestra que hay una división t con números iguales de cada color real.

Resultado negativo

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

Dividiendo collares multidimensionales

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

Algoritmo de aproximación

Se puede derivar un algoritmo de aproximación para dividir un collar a partir de un algoritmo para dividir a la mitad por consenso . ^[8]

Ver también

• Collar combinatorio
• Problema con el collar
• división exacta

Referencias

1. Alon, Noga (1987). "Rompiendo collares". Avances en Matemáticas . 63 (3): 247–253. doi : 10.1016/0001-8708(87)90055-7 .
2. Alon, Noga; Oeste, Douglas B. (diciembre de 1986). "El teorema de Borsuk-Ulam y la bisección de collares" . Actas de la Sociedad Matemática Estadounidense . 98 (4): 623–628. doi : 10.1090/s0002-9939-1986-0861764-9 .
3. 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. 
4. Alon, 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). "Collar bisección 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). "Collar dividido y coloración medible de la línea real". Actas de la Sociedad Matemática Estadounidense . 137 (5): 1593-1599. arXiv : 1412.7996 . doi : 10.1090/s0002-9939-08-09699-8 . ISSN  1088-6826.
7. de Longueville, Marcos; Rade T. Živaljević (2008). "Dividir collares multidimensionales". Avances en Matemáticas . 218 (3): 926–939. arXiv : matemáticas/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.