Problema de rotura del collar

La división del collar es un nombre pintoresco que se da a varios problemas relacionados en la combinatoria y la teoría de la medida. Su nombre y soluciones se deben a los matemáticos Noga Alon y Douglas B. West.El engaste básico consiste en un collar con cuentas de diferentes colores. El collar debe dividirse entre varios participantes (por ejemplo, ladrones), de modo que cada uno reciba la misma cantidad de cada color. Además, el número de cortes debe ser el menor posible (para minimizar el desperdicio de metal en los eslabones de las cuentas).Las siguientes variantes del problema se han resuelto en el artículo original:

1. Discreta división: El collar tiene ${\displaystyle k\cdot n}$ cuentas. Las cuentas entran ${\displaystyle t}$ diferentes colores. Hay ${\displaystyle k\cdot a_{i}$ cuentas de cada color ${\displaystyle i}$, donde ${\displaystyle A_{i}$ es un entero positivo. Partición del collar en ${\displaystyle k}$ partes (no necesariamente contiguas), cada una de las cuales tiene exactamente ${\displaystyle A_{i}$ cuentas de color i. Uso al máximo ${\displaystyle (k-1)t}$ cortes. Tenga en cuenta que si las cuentas de cada color son contiguas en el collar, entonces al menos ${\displaystyle k-1}$ los cortes deben hacerse dentro de cada color, así que ${\displaystyle (k-1)t}$ es óptimo.
2. Dicción continua: El collar es el intervalo real ${\displaystyle [0,k\cdot n]$. Cada punto del intervalo es coloreado en uno de ${\displaystyle t}$ diferentes colores. Por cada color ${\displaystyle i}$, el conjunto de puntos de color ${\displaystyle i}$ es Lebesgue-measurable y tiene longitud ${\displaystyle k\cdot a_{i}$, donde ${\displaystyle A_{i}$ es un número real no negativo. Partición del intervalo a ${\displaystyle k}$ partes (no necesariamente contiguas), tal que en cada parte, la longitud total del color ${\displaystyle i}$ es exactamente ${\displaystyle A_{i}$. Uso al máximo ${\displaystyle (k-1)t}$ cortes.
3. Medida dividida: El collar es un intervalo real. Hay ${\displaystyle t}$ diferentes medidas en el intervalo, todo absolutamente continuo con respecto a la longitud. La medida del collar entero, según medida ${\displaystyle i}$, es ${\displaystyle k\cdot a_{i}$. Partición del intervalo a ${\displaystyle k}$ partes (no necesariamente contiguas), tal que la medida de cada parte, según medida ${\displaystyle i}$, es exactamente ${\displaystyle A_{i}$. Uso al máximo ${\displaystyle (k-1)t}$ cortes. Esta es una generalización del teorema Hobby-Rice, y se utiliza para conseguir una división exacta de un pastel.

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 a una coloración del intervalo real ${\displaystyle [0,k\cdot n]$ en el que cada intervalo de longitud 1 es coloreado por el color de la cuentas correspondiente. En caso de que la división continua trate de cortar las cuentas internas, los cortes se pueden deslizar gradualmente tal que se hacen sólo entre las cuentas.
• La división continua se puede resolver mediante la división de la medida, ya que una coloración de un intervalo en ${\displaystyle t}$ los colores se pueden convertir en un conjunto ${\displaystyle t}$ medidas, tal medida ${\displaystyle i}$ mide la longitud total del color ${\displaystyle i}$. Lo contrario también es cierto: la división de medidas se puede resolver mediante la división continua, utilizando una reducción más sofisticada.

El caso ${\displaystyle k=2}$ puede ser probado por el teorema Borsuk-Ulam.

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

Cuando ${\displaystyle k}$ es un número compuesto, la prueba es la siguiente (demuestrada para la variante de multiplicación de medidas). Suppose ${\displaystyle k=p\cdot q}$. Hay ${\displaystyle t}$ medidas, cada una de las cuales valora todo el collar como ${\displaystyle p\cdot q\cdot A_{i}$. Uso ${\displaystyle (p-1)\cdot t}$ cortes, dividir el collar para ${\displaystyle p}$ partes tales que miden ${\displaystyle i}$ de cada parte es exactamente ${\displaystyle q\cdot a_{i}$. Uso ${\displaystyle (q-1)\cdot t}$ cortes, dividir cada parte a ${\displaystyle q}$ partes tales que miden ${\displaystyle i}$ de cada parte es exactamente ${\displaystyle A_{i}$. En total, ahora hay ${\displaystyle pq}$ partes tales que miden ${\displaystyle i}$ de cada parte es exactamente ${\displaystyle A_{i}$. El número total de cortes es ${\displaystyle (p-1)\cdot t}$ más ${\displaystyle p(q-1)\cdot t}$ que es exactamente ${\displaystyle (pq-1)\cdot t}$.

En algunos casos, los collares aleatorios pueden dividirse por igual 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 requeridos para dividir un collar aleatorio entre dos ladrones. En el modelo que consideraron, un collar es elegido uniformemente al azar del conjunto de collares con t colores y m cuentas de cada color. As m tiende a la infinidad, la probabilidad de que el collar se puede dividir utilizando ⌊(t +1)/2⌋ cortes o menos tiende a cero mientras que la probabilidad de que es posible dividir con ⌊(t +1)/2⌋ + 1 los cortes están atados de cero. Más precisamente, dejando X = X()t,m) ser el número mínimo de cortes requeridos para dividir el collar. Lo siguiente sostiene como m tiende a la infinidad. Para cualquier ${\displaystyle s won(t+1)/2}$

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

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

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

Finalmente, cuando ${\displaystyle t}$ es extraño ${\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.4t y como mínimo 0.22t con alta probabilidad. Se conjetura que existe un 0.22 c 0.4 tal que X(t,1)/t converge a c en la distribución.

Un corte menor 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 t − 1 corte, el matemático húngaro Gábor Simonyi demuestra que los dos ladrones pueden lograr una división casi justa en el siguiente sentido.

Si el collar está arreglado para que no t- es posible, entonces para cualquier dos subconjuntos D₁ y D₂ de 1, 2,... t } no ambos vacíos, tal que ${\displaystyle D_{1}\cap D_{2}=\varnothing }$, at − 1)-split existe tal que:

• Si color ${\displaystyle i\in D_{1}$, entonces la partición 1 tiene más cuentas de color i que la partición 2;
• Si color ${\displaystyle i\in D_{2}$, entonces la partición 2 tiene más cuentas de color i que la partición 1;
• Si color i no está en ninguna partición, ambas particiones tienen igualmente muchas 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 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 observado que el resultado anterior es una generalización directa del teorema original del collar de Alon en el caso k = 2. O bien el collar tiene una división (t − 1), o bien 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₂ esté vacío. Entonces, el resultado de Simonyi muestra que hay una división t con el mismo número de cada color real.

Resultado negativo

Por todos ${\displaystyle k\geq 1}$ hay un mesurable ${\displaystyle (k+3)}$-coloración de la línea real tal que ningún intervalo puede ser bastante dividido usando a la mayoría ${\displaystyle k}$ cortes.

Collares multidimensionales de división

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

algoritmo de aproximación

Un algoritmo de aproximación para dividir un collar puede derivarse de un algoritmo de consenso para dividirlo a la mitad.

Véase también

• Collar combinado
• Problema de collar
• División exacta

Referencias

1. ^ a b c d e f Alon, Noga (1987). "Collares multiplicadores". Avances en Matemáticas. 63 3): 247 –253. doi:10.1016/0001-8708(87)90055-7.
2. ^ a b Alon, Noga; West, Douglas B. (diciembre de 1986). "El teorema Borsuk-Ulam y la bisección de collares". Proceedings of the 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". 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. ^ Alon, Noga; Elboim, Dor; Tardos, Gábor; Pach, János (2021). "Random collares requieren menos cortes". arXiv:2112.14488 [Math.CO].
5. ^ Simonyi, Gábor (2008). "Bisección de necklace con un corte menos de lo necesario". Electronic Journal of Combinatorics. 15 (N16). doi:10.37236/891.
6. ^ Alon, Noga (25 de noviembre de 2008). "Collares multiplicadores y colorantes mensurables de la línea real". Proceedings of the 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). "Collares multiplicadores multidimensionales". Avances en Matemáticas. 218 3): 926 –939. arXiv:matemáticas/0610800. doi:10.1016/j.aim.2008.02.003.
8. ^ Simmons, Forest W.; Su, Francis Edward (febrero de 2003). "Consensus-halving via theorems of Borsuk-Ulam and 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 video introductorio que presenta el problema con su solución topológica.