Hispanopedia Wiki
Articulo de referencia

Problema de rotura de collar

Ejemplo de división de un collar con k = 2 (dos socios) y t = 2 (dos tipos de cuentas, en este caso 8 rojas y 6 verdes). Se muestra una división en dos: un socio recibe la secci...

Hispanopedia WikiContenido en espanolLectura gratuita
Una imagen estilizada de un collar con 8 perlas rojas y 6 verdes. Las perlas están ensartadas en una curva elíptica negra incompleta que representa el hilo. El hueco en la curva representa el cierre (abierto en el diagrama), que se puede cerrar cuando el collar se coloca alrededor del cuello. Hay dos líneas cortas y gruesas que marcan las interrupciones en el hilo del collar. Empezando por la izquierda, el collar es: RRRGRBRRGRRGGBGG, donde "R" significa "perla roja", "G" significa "perla verde" y "B" significa "interrupción". Las interrupciones corresponden a las del texto.
Ejemplo de división de un collar con k = 2 (dos socios) y t = 2 (dos tipos de cuentas, en este caso 8 rojas y 6 verdes). Se muestra una división en dos: un socio recibe la sección más grande y el otro recibe las dos piezas restantes.

El problema de 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 juego consiste en un collar con cuentas de diferentes colores. El collar debe dividirse entre varios participantes (por ejemplo, ladrones), de manera que cada uno reciba la misma cantidad de cuentas de cada color. Además, el número de cortes debe ser mínimo (para minimizar el desperdicio 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 tienek⋅norte{\displaystyle k\cdot n}cuentas. Las cuentas vienen ent{\displaystyle t}diferentes colores. Hayk⋅ai{\displaystyle k\cdot a_{i}}cuentas de cada colori{\displaystyle i}, dóndeai{\displaystyle a_{i}}es un número entero positivo . Divide el collar enk{\displaystyle k}partes (no necesariamente contiguas), cada una de las cuales tiene exactamenteai{\displaystyle a_{i}}cuentas de color i . Usar como máximo(k−1)t{\displaystyle (k-1)t}cortes. Tenga en cuenta que si las cuentas de cada color son contiguas en el collar, entonces al menosk−1{\displaystyle k-1}Los cortes deben hacerse dentro de cada color, por lo que(k−1)t{\displaystyle (k-1)t}es óptimo.
  2. División continua : [ 1 ] : Th 2.1 El collar es el intervalo real[0,k⋅norte]{\displaystyle [0,k\cdot n]}Cada punto del intervalo está coloreado de uno de lost{\displaystyle t}diferentes colores. Para cada colori{\displaystyle i}, el conjunto de puntos coloreados pori{\displaystyle i}es medible según Lebesgue y tiene longitudk⋅ai{\displaystyle k\cdot a_{i}}, dóndeai{\displaystyle a_{i}}es un número real no negativo. Particione el intervalo ak{\displaystyle k}partes (no necesariamente contiguas), de tal manera que en cada parte, la longitud total del colori{\displaystyle i}es exactamenteai{\displaystyle a_{i}}. Utilizar como máximo(k−1)t{\displaystyle (k-1)t}cortes.
  3. División de medidas : [ 1 ] : Th 1.2 El collar es un intervalo real. Hayt{\displaystyle t}diferentes medidas en el intervalo, todas absolutamente continuas con respecto a la longitud. La medida de todo el collar, según la medidai{\displaystyle i}, esk⋅ai{\displaystyle k\cdot a_{i}}. Dividir el intervalo enk{\displaystyle k}partes (no necesariamente contiguas), de modo que la medida de cada parte, según la medidai{\displaystyle i}es exactamenteai{\displaystyle a_{i}}. Utilizar como máximo(k−1)t{\displaystyle (k-1)t}cortes. Esta es una generalización del teorema de Hobby-Rice y se utiliza 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.[0,k⋅norte]{\displaystyle [0,k\cdot n]}en el que cada intervalo de longitud 1 está coloreado con el color de la cuenta correspondiente. En caso de que la división continua intente cortar dentro de las cuentas, los cortes pueden deslizarse gradualmente de manera que se realicen solo entre las cuentas. [ 1 ] : 249
  • La división continua se puede resolver mediante la división de medidas, ya que una coloración de un intervalo ent{\displaystyle t}Los colores se pueden convertir a un conjunto.t{\displaystyle t}medidas, tales que la medidai{\displaystyle i}mide la longitud total del colori{\displaystyle i}Lo contrario también es cierto: la división de medidas puede resolverse mediante una división continua, utilizando una reducción más sofisticada. [ 1 ] : 252–253

Prueba

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

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

Cuandok{\displaystyle k}es un número compuesto , la demostración es la siguiente (demostrada para la variante de división de medidas). Supongamos quek=pag⋅q{\displaystyle k=p\cdot q}. Hayt{\displaystyle t}medidas, cada una de las cuales valora el collar completo comopag⋅q⋅ai{\displaystyle p\cdot q\cdot a_{i}}. Usando(pag−1)⋅t{\displaystyle (p-1)\cdot t}cortes, divida el collar enpag{\displaystyle p}partes tales que mideni{\displaystyle i}de cada parte es exactamenteq⋅ai{\displaystyle q\cdot a_{i}}. Usando(q−1)⋅t{\displaystyle (q-1)\cdot t}cortes, divida cada parte enq{\displaystyle q}partes tales que mideni{\displaystyle i}de cada parte es exactamenteai{\displaystyle a_{i}}En total, ahora haypagq{\displaystyle pq}partes tales que mideni{\displaystyle i}de cada parte es exactamenteai{\displaystyle a_{i}}. El número total de cortes es(pag−1)⋅t{\displaystyle (p-1)\cdot t}máspag(q−1)⋅t{\displaystyle p(q-1)\cdot t}que es exactamente(pagq−1)⋅t{\displaystyle (pq-1)\cdot t}.

Resultados adicionales

Dividir collares al azar

En algunos casos, los collares elegidos al azar se pueden dividir equitativamente con 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 elegido al azar entre dos ladrones. [ 4 ] En el modelo que consideraron, se elige un collar uniformemente 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 usando ⌊(t  +  1)/2⌋ cortes o menos tiende a cero, mientras que la probabilidad de que sea posible dividirlo con ⌊(t  +  1)/2⌋  +  1 cortes está acotada lejos de 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 s<(t+1)/2{\displaystyle s<(t+1)/2}

PAG(incógnita=s)=Θ(metros−(t+1)/2).{\displaystyle \mathbb {P} (X=s)=\Theta {\big (}m^{s-(t+1)/2}{\big )}.}

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

PAG(incógnita=s)=Θ(1).{\displaystyle \mathbb {P} (X=s)=\Theta (1).}

Finalmente, cuandot{\displaystyle t}es extraño ys=(t+1)/2{\displaystyle s=(t+1)/2}

PAG(incógnita=s)=Θ((registro⁡metro)−1).{\displaystyle \mathbb {P} (X=s)=\Theta {\big (}(\log m)^{-1}{\big )}.}

También se puede considerar el caso en 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,4t y como mínimo 0,22t con alta probabilidad. Se conjetura que existe algún 0,22  < c < 0,4 tal que X ( t ,1)/ t   converge a c en 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 ] muestra que los dos ladrones pueden lograr una división casi justa en el siguiente sentido.  

Si el collar está dispuesto de tal manera que no es posible ninguna división t , entonces para cualesquiera dos subconjuntos D 1 y D 2 de {  1,  2,  ..., t }, no ambos vacíos , tales que  D1∩D2=∅{\displaystyle D_{1}\cap D_{2}=\varnothing }, existe una división ( t − 1) tal que:  

  • Si el colori∈D1{\displaystyle i\in D_{1}}, entonces la partición 1 tiene más cuentas de color i que la partición 2;
  • Si el colori∈D2{\displaystyle i\in D_{2}}, entonces la partición 2 tiene más cuentas de color i que la partición 1;
  • 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 1 y D 2 , no ambos vacíos, existe una división ( t − 1) tal que el ladrón 1 obtiene más cuentas de tipos en su conjunto de preferencias D 1 que el 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 reconoce que Gábor Tardos observó que el resultado anterior es una generalización directa del teorema del collar original de Alon en el caso k = 2. 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, de modo que D1 consista en el color ficticio y D2 esté vacío. Entonces , el resultado de Simonyi muestra que existe una división t con igual número de cada color real.  

Resultado negativo

Por cadak≥1{\displaystyle k\geq 1}hay una cantidad medible(k+3){\displaystyle (k+3)}-coloración de la línea real de tal manera que ningún intervalo pueda dividirse de forma justa utilizando como máximok{\displaystyle k}cortes. [ 6 ]

Extensiones

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

Collares dinámicos: La división de collares en entornos dinámicos permite la reubicación, inserción y eliminación de cuentas, lo que contribuye a aplicaciones como mapas hash justos basados ​​en datos y un mejor equilibrio de carga entre múltiples servidores. [ 8 ]

Algoritmo de aproximación

Un algoritmo de aproximación para dividir un collar puede derivarse de un algoritmo para la división por la mitad por consenso . [ 9 ]

Véase también

Referencias

  1. 1 2 3 4 5 6 Alon, Noga (1987). "Splitting Necklaces" . Advances in Mathematics . 63 (3): 247– 253. doi : 10.1016/0001-8708(87)90055-7 .
  2. 1 2 Alon, Noga; West, Douglas B. (diciembre de 1986). "El teorema de Borsuk-Ulam y la bisección de collares" . Actas de la Sociedad Matemática Americana . 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". Journal of the London Mathematical Society . 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) N16. doi : 10.37236/891 .
  6. ↑ Alon, Noga (25 de noviembre de 2008). "División de collares y coloraciones medibles de la línea real" . Actas de la Sociedad Matemática Americana . 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). "División de collares multidimensionales" . Advances in Mathematics . 218 (3): 926– 939. arXiv : math/0610800 . doi : 10.1016/j.aim.2008.02.003 .
  8. ↑ Advani, Rishi; Abolfazl Asudeh; Mohsen Dehghankar; Stavros Sintos (2026). "División dinámica de collares" . 29.ª Conferencia Internacional sobre Teoría de Bases de Datos (ICDT 2026) . 365 (19): 1– 20. doi : 10.4230/LIPIcs.ICDT.2026.19 .
  9. ^ 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 . 
  • "Topología astuta" en YouTube , un vídeo introductorio que presenta el problema con su solución topológica.