Problema de corte de collar

El problema del corte del collar es el nombre de una serie de problemas de combinatoria y teoría de la medida . El problema fue formulado y resuelto por los matemáticos Noga Alon [1] y Douglas B. West [2] .

Las condiciones básicas definen un collar con cuentas de diferentes colores. El collar debe dividirse entre varios participantes o ladrones (muchas veces se supone que el collar es robado), de modo que cada participante reciba una cierta cantidad de cuentas de cada color. Además, el número de cortes debe ser el menor posible (para perder la menor cantidad de metal posible en la cadena que conecta las perlas).

Variaciones

Las siguientes variantes del problema fueron resueltas en el artículo original:

Corte discreto [3] : El collar tiene cuentas. Las cuentas son de varios colores. Hay cuentas de cada color , donde es un número entero positivo. Debe cortar el collar en partes (no necesariamente continuas), cada una de las cuales tiene exactamente cuentas de color i . No se deben utilizar más cortes. Tenga en cuenta que si las cuentas de cada color están dispuestas de forma continua en el collar, necesitará al menos cortes dentro de cada color para que el valor sea óptimo. $k\cdot n$ $t$ $k\cdot a_{i}$ $i$ $ai}$ $k$ $ai}$ ${\ estilo de visualización (k-1) t}$ $k-1$ ${\ estilo de visualización (k-1) t}$
Corte continuo [4] : El collar es un segmento real . Cada punto del segmento está coloreado en uno de los colores. Para cualquier color, el conjunto de puntos coloreados por color es medible según Lebesgue y tiene longitud , donde es un número real no negativo. Debes dividir el segmento en partes (no necesariamente continuas), de modo que en cada parte la longitud total del color sea exactamente igual a . No use más cortes. ${\ estilo de visualización [0, k \ cdot n]}$ $t$ $i$ $i,$ $k\cdot a_{i}$ $ai}$ $k$ $i$ $ai}$ ${\ estilo de visualización (k-1) t}$
Partición por medida [5] : El collar es un segmento real. Hay varias medidas en un segmento, todas absolutamente continuas en longitud. La medida de todo el collar en medida es . El segmento debe dividirse en partes (no necesariamente continuas), de modo que la medida de cada parte en medida sea exactamente igual a . No use más cortes. Esta es una generalización del teorema de Hobby-Rice y se utiliza para obtener una división exacta del pastel . $t$ $i$ $k\cdot a_{i}$ $k$ $i$ $ai}$ ${\ estilo de visualización (k-1) t}$

Cada tarea se puede resolver de la siguiente manera:

Un corte discreto se puede solucionar con un corte continuo, ya que un collar discreto se puede reducir a una coloración de línea real en la que cada segmento de línea de longitud 1 se colorea con el color de la cuenta correspondiente. En el caso de que una partición continua intente cortar dentro de un cordón, el corte se puede cambiar para que los cortes sean solo entre los cordones [6] . ${\ estilo de visualización [0, k \ cdot n]}$
El corte continuo se puede hacer mediante la partición por medida, ya que la coloración de un segmento en colores se puede convertir en un conjunto de medidas, de modo que la medida refleje la longitud del color . Lo contrario también es cierto: se puede obtener una partición por medida mediante un corte continuo con la ayuda de una reducción más fina [7] . $t$ $t$ $i$ $i$

Prueba

El caso puede probarse mediante el teorema de Borsuk-Ulam [2] . $k=2$

Si es un primo impar , la prueba usa una generalización del teorema de Borsuk-Ulam [8] . $k$

Si es compuesto , la prueba será la siguiente (demostramos para la opción de dividir por medida). Supongamos que . Hay medidas, cada una de las cuales evalúa todo el collar como . Usando cortes, dividimos el collar en partes, de manera que la medida de cada parte sea exactamente igual a . Vamos a cortar cada parte en partes con la ayuda de , para que la medida de cada parte sea exactamente igual a . Ahora hay partes tales que la medida de cada parte es exactamente . El número total de cortes es , que es exactamente . $k$ $k=p\cdot q$ $t$ ${\displaystyle p\cdot q\cdot a_{i))$ ${\ estilo de visualización (p-1) \ cdot t}$ $pags$ $i$ ${\displaystyle q\cdot a_{i))$ ${\ estilo de visualización (q-1) \ cdot t}$ $q$ $i$ $ai}$ ${\ estilo de visualización pq}$ $i$ $ai}$ ${\ estilo de visualización (p-1) \ cdot t + p (q-1) \ cdot t}$ ${\ estilo de visualización (pq-1) \ cdot t}$

Otros resultados

Un corte menos de lo necesario

En el caso de dos ladrones [es decir, k = 2] y t colores, un corte justo requeriría como máximo t cortes. Sin embargo, si solo se permiten cortes, el matemático húngaro Gábor Szymonyi [9] demostró que dos ladrones pueden lograr una división casi justa en el siguiente sentido: ${\ estilo de visualización t-1}$

si las cuentas en el collar están dispuestas de tal manera que es posible un corte en t , entonces para dos subconjuntos D 1 y D 2 de los conjuntos , los cuales no están vacíos de manera que , hay un corte tal que: ${\ estilo de visualización \ {1,2, \ puntos, t \}}$ $D_{1}\cap D_{2}=\varnada$ ${\ estilo de visualización (t-1)}$

Si el color es , entonces la parte 1 tiene más cuentas del color i que la parte 2; ${\ estilo de visualización i \ en D_ {1}}$
Si el color es , entonces la parte 2 tiene más cuentas del color i que la parte 1; ${\ estilo de visualización i \ en D_ {2}}$
Si el color i no pertenece a ninguna de las partes y , ambas partes tienen el mismo número de cuentas del color i . $D_{1}$ $D_{2}$

Esto significa que si los ladrones tienen preferencias en forma de dos conjuntos de "preferencias" D 1 y D 2 , de los cuales al menos uno no está vacío, existe una partición tal que el ladrón 1 obtiene más cuentas de su conjunto de preferencias D 1 que el ladrón 2, el ladrón 2 obtendrá más cuentas de su conjunto de preferencias D 2 que el ladrón 1, y el resto será el mismo. ${\ estilo de visualización (t-1)}$

Simony atribuye a Gabor Tardos la observación de 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 un corte o no. En caso de que así sea, no hay nada que probar. Si no, podemos agregar una cuenta de color ficticio al collar y formar dos conjuntos, el conjunto D 1 consta de este color ficticio y el conjunto D 2 está vacío. El resultado de Simony muestra que existe un corte en t con igual número de colores de cada color real. ${\ estilo de visualización (t-1)}$

Resultado negativo

Para cualquier , existe una coloración medible en los colores de la línea real, de modo que ningún intervalo puede subdividirse de manera justa en la mayoría de los cortes [10] . $k\geqslant 1$ ${\ estilo de visualización (k + 3)}$ $k$

Cortando el Collar Multidimensional

El resultado puede extenderse a medidas de probabilidad n definidas en un cubo d - dimensional con cualquier combinación de hiperplanos paralelos a los lados para k ladrones [11] . $n(k-1)$

Algoritmo de aproximación

Se puede derivar un algoritmo de aproximación para cortar el collar a partir del algoritmo para reducir a la mitad consistentemente [12] .

Véase también

Notas

↑ Solo, 1987 , p. 247-253.
↑ 1 2 Alon, West, 1986 , pág. 623-628.
↑ Solo, 1987 , p. 247–253 Tom 1.1.
↑ Solo, 1987 , p. 247–253 Tom 2.1.
↑ Solo, 1987 , p. 247–253 Tom 1.2.
↑ Solo, 1987 , p. 249.
↑ Solo, 1987 , p. 252-253.
↑ Barany, Shlosman, Szucs, 1981 , pág. 158–164.
↑ Simonyi, 2008 .
↑ Solo, 2008 , p. 1593-1599
↑ de Longueville, Živaljević, 2008 , p. 926-939.
↑ Simmons, Domingo, 2003 , pág. 15–25.

Literatura

Noga Alon. Partiendo Collares // Avances en Matemáticas. - 1987. - T. 63 , núm. 3 . - doi : 10.1016/0001-8708(87)90055-7 .
Noga Alon, West DB El teorema de Borsuk-Ulam y la bisección de collares // Actas de la American Mathematical Society. - 1986. - Diciembre ( vol. 98 , número 4 ). -doi : 10.1090 / s0002-9939-1986-0861764-9 .
I. Barany, S. B. Shlosman, A. Szucs. Sobre una generalización topológica de un teorema de Tverberg // Journal of the London Mathematical Society. - 1981. - Vol. 2 , número. 23 . -doi : 10.1112 / jlms/s2-23.1.158 .
Gabor Simonyi. Bisección de collar con un corte menos del necesario // Electronic Journal of Combinatorics. - 2008. - T. 15 , núm. N16 .
Noga Alon. Collares divididos y coloraciones medibles de la línea real // Actas de la Sociedad Matemática Estadounidense. - 2008. - noviembre ( vol. 137 , número 5 ). — ISSN 1088-6826 . -doi : 10.1090 / s0002-9939-08-09699-8 . -arXiv : 1412.7996 . _
Mark de Longueville, Rade T. Zivaljević. Partiendo collares multidimensionales // Avances en Matemáticas. - 2008. - T. 218 , núm. 3 . -doi : 10.1016/ j.aim.2008.02.003 . -arXiv : matemáticas / 0610800 .
Bosque W. Simmons, Francis Edward Su. Reducción a la mitad del consenso a través de los teoremas de Borsuk-Ulam y Tucker // Ciencias sociales matemáticas. - 2003. - febrero ( vol. 45 , número 1 ). - doi : 10.1016/s0165-4896(02)00087-2 .

Enlaces

"Topología disimulada" en YouTube .