El problema del collar

Piste bleue Le 17 août 2022  - Ecrit par  Frédéric Meunier
Le 20 septembre 2022  - Traduit par  Edgard Araya, Andrés Navas, Pilar Garcés
Article original : Le problème du collier Voir les commentaires
Lire l'article en  

Dos ladrones, Alice y Bob, acaban de sustraer un magnífico collar, compuesto por varios tipos de perlas. Ha llegado el momento de compartirlo... El teorema del collar asegura que una repartición justa será posible sin tener que cortar la cadena con demasiada frecuencia. Simple de enunciar, este teorema no conoce ninguna prueba elemental. Y no es porque sepamos que existe tal repartición equitativa que esta es fácil de determinar...

Aquí está el collar que Alice y Bob robaron y quieren compartir por igual.

JPEG - 21.9 ko
Un magnífico collar con tres tipos de perlas.

El collar está hecho de perlas de diferentes tipos (Akoya, Tahití, Hanadama, etc.), cuyo valor los ladrones desconocen. Por suerte, hay un número par de perlas de cada tipo. En el ejemplo de la figura anterior, hay tres tipos de perlas y exactamente cuatro perlas de cada tipo. La solución será que cada uno de los dos ladrones se lleve la mitad de las perlas de cada tipo, y la repartición será justa. Las perlas están firmemente fijadas en la cadena. Sin embargo, a Alice y Bob les gustaría no tener que cortarla con demasiada frecuencia, pues se trata de una operación delicada o simplemente porque la cadena en sí es preciosa y sería una pena dañarla más de lo necesario. Y aquí es donde ocurre el milagro matemático.

Siempre existe una repartición justa de un collar abierto con un número par de perlas por tipo que no requiere un número de cortes mayor al de tipos de perlas en el collar.

El collar de la figura de arriba presenta tres tipos de perlas, y bien puede ser compartido en partes iguales entre Alice y Bob mediante tres cortes :

JPEG - 38.5 ko
Una repartición equitable mediante tres cortes.

Incluso si el collar tiene trillones de perlas, mientras haya solo tres tipos de perlas y un número par de perlas por tipo, habrá una repartición justa en tres cortes como máximo. Por otro lado, no podemos esperar tener un teorema que asegure menos cortes : siempre existe un collar que requiere un número de cortes igual al número de tipos de perlas para obtener una partición justa. Un ejemplo de tal collar se muestra en la siguiente figura.

JPEG - 26.5 ko
Para este collar, toda partición equitable necesita al menos de tantos cortes como de tipos de perlas que posee.

Este teorema, encontrado a mediados de la década de 1980 por Alon, Goldberg y West [AW86,GW85], es sin duda fascinante. Pero lo que es aún más importante es que la demostración de este teorema es cualquier cosa menos elemental...

Demostración del teorema del collar

En la actualidad existen varias demostraciones del teorema del collar, pero todas ellas utilizan, explícitamente o no, el teorema de Borsuk-Ulam, o un resultado equivalente. El teorema de Borsuk-Ulam es un resultado avanzado de la topología (la disciplina de las matemáticas que estudia cómo se deforman los objetos), y su anunciado está más allá del nivel de este artículo. En otras palabras, incluso si todos pueden entender el enunciado del teorema del collar, solo las personas que hayan tomado cursos avanzados de matemáticas podrán entender la demostración. Hay un verdadero desafío para el matemático : ¿cómo es que un enunciado tan simple no tiene demostración elemental ?

El teorema de Borsuk-Ulam

Denotamos por $\mathcal{S}^d$ la esfera unitaria de dimensión $d$ centrada en $\boldsymbol{0}$. En otras palabras,
\[ \mathcal{S}^d=\left\{(x_1,\ldots,x_{d+1})\in\mathbb{R}^{d+1}\colon \sum_{i=1}^{d+1}x_i^2=1\right\}. \]
El teorema de Borsuk-Ulam se expresa entonces de la siguiente manera : Sea $f$ una función continua $\mathcal{S}^d\rightarrow\mathbb{R}^d$ tal que $f(-\boldsymbol{x})=-f(\boldsymbol{x})$ para todo $\boldsymbol{x}\in\mathcal{S}^d$ ; entonces existe $\boldsymbol{x}^*\in\mathcal{S}^d$ tal que $f(\boldsymbol{x}^*)=\boldsymbol{0}$.

Este teorema se entiende fácilmente en el caso de que $d=1$ : cuando tomamos la circunferencia unitaria y la desplegamos sobre la recta real para cubrir números reales de diferentes signos, necesariamente cubrimos $0$.

Una aplicación tradicional de este teorema es la siguiente : siempre hay dos puntos simétricos en la Tierra en los que la temperatura y la presión son idénticas. Para convencerse de esto, basta aplicar el teorema para $d=2$ y para
\[f:\boldsymbol{x}\mapsto\big(T(\boldsymbol{x})-T(-\boldsymbol{x}),P(\boldsymbol{x})-P(-\boldsymbol{x})\big)\]
donde $T(\cdot)$ y $P(\cdot)$ entregan respectivamente la temperatura y la presión en un punto del globo.

Dicho esto, hay casos especiales del teorema del collar que pueden demostrarse fácilmente. Por ejemplo, el caso con dos tipos de perlas, digamos rojas y azules, admite una prueba asequible. Considere una posible primera división de cortar el collar exactamente en el medio y darle la primera mitad a Alice y la segunda a Bob. Si la primera parte tiene exactamente la mitad de las perlas de cada tipo, la segunda también, y entonces tenemos una repartición justa que requiere solo un corte.

Aunque signifique darle la vuelta al collar, podemos suponer que la primera parte del collar tiene más de la mitad de las perlas rojas y menos de la mitad de las perlas azules. Para la segunda parte, es todo lo contrario : hay menos de la mitad de perlas rojas y más de la mitad de perlas azules. Ahora avancemos una ’’ventana’’ de longitud constante, desde la primera parte del collar hasta la segunda parte.

JPEG - 124.5 ko
Prueba del teorema del collar cuando hay dos tipos de perlas.

Cada vez que la ventana mueve una perla, el número total de perlas rojas en la ventana cambia como máximo en una. A medida que la ventana pasa de una posición en la que hay más de la mitad de las perlas rojas a una posición en la que hay menos de la mitad, la ventana necesariamente pasa por una posición en la que hay cruces con el número correcto de perlas rojas. Y dado que la ventana en esta posición contiene la mitad del número total de perlas, también contiene el número correcto de perlas azules. Entonces tenemos nuestra división del collar en dos cortes : simplemente corte el collar en los extremos de la ventana.

Otro caso que se prueba fácilmente y que se deja como un desafío para el lector es el caso en que el número de tipos de perlas es arbitrario, pero hay exactamente dos perlas de cada tipo.

Dos perlas de cada tipo

Repasamos las perlas, de izquierda a derecha. La perla en cuestión siempre se asigna al ladrón que va haciendo este repaso. Al principio, Alice es esta ladrona. Cuando se llega a un tipo de perla que ya tiene el ladrón que repasa, se cambia de ladrón. Los momentos en que se cambia de ladrón corresponden a los lugares de corte del collar.

en efecto, cuando se cambia el ladrón, la perla considerada es necesariamente la segunda ocurrencia de su tipo. Por lo tanto, cambiamos el ladrón como máximo un número de veces igual al número de tipos de perlas. De ahí el resultado.

¿Un algoritmo ?

Dado un collar abierto, con un número par de perlas por tipo, el teorema asegura que hay una división justa que no requiera más cortes que tipos. ¿Pero es fácil encontrar un corte así ? ¿Se puede encontrar rápidamente una repartición tan justa ? Una vez más, la situación es intrigante : no lo sabemos. Esta pregunta se puede formalizar matemáticamente con la noción de algoritmo. Un algoritmo es una secuencia de operaciones que se puede programar en una computadora, que toma datos y devuelve un resultado. Aquí los datos describen un collar con un número par de perlas por tipo, y el resultado es dónde cortar el collar para obtener una repartición justa como lo garantiza el teorema. Para un matemático, la pregunta es si existe un algoritmo que siempre logre encontrar una repartición tan justa sin hacer demasiadas operaciones. Hasta la fecha, el único algoritmo conocido para encontrar de forma fiable una repartición tan justa es enumerar todas las reparticiones con el número correcto de cortes y dar tantas perlas de cada tipo a Alice y Bob. Este no es un algoritmo satisfactorio porque realiza una cantidad de operaciones que crece exponencialmente con la cantidad de tipos de perlas : pasar a una instancia con un tipo más, incluso sin cambiar el número total de perlas, más que duplica la cantidad de operaciones a realizar para encontrar la repartición justa. Encontrar una repartición justa con dicho algoritmo para un collar con 30 tipos y 4 cuentas por tipo llevaría muchos miles de millones de años, incluso en las computadoras más poderosas del mundo.

La cuestión de la existencia de un algoritmo no exponencial, aunque planteada para un problema cuya relevancia práctica parece limitada, tiene una importancia teórica considerable. Hay muchos teoremas, como el del teorema del collar, donde se asegura la existencia de un objeto matemático sin tener información sobre cómo exhibirlo. Algunos de ellos tienen además un cierto interés práctico (en particular por los resultados que aseguran la existencia de equilibrios económicos). La teoría que se ocupa de los problemas algorítmicos y de exhibir tales objetos aún no se comprende del todo. Encontrar un algoritmo rápido para el problema del collar, o demostrar que no puede existir (sí, se puede demostrar bajo ciertas condiciones la inexistencia de algoritmos), sin duda mejoraría nuestra comprensión de esta teoría. También es posible que si algún día logramos encontrar una prueba elemental del teorema, esta prueba también dará un algoritmo rápido.

¿Qué pasa si hay tres ladrones (o incluso más) ?

Un matemático al que se le presente el teorema del collar y su demostración naturalmente hará las preguntas mencionadas anteriormente. ¿Existe una prueba elemental ? ¿Existe un algoritmo rápido que calcule una repartición tan justa ? Otra pregunta natural también vendrá inmediatamente a la mente : ¿es posible generalizar este teorema ? Por ejemplo, ¿existe un teorema que cubra el caso de los dos ladrones, pero también un caso de tres ladrones, cuatro ladrones, etc.? Podemos responder afirmativamente y el teorema, encontrado por Alon en 1987 [A87], es el siguiente : Sea $q$ el número de ladrones y $t$ el número de tipos, y suponga que el número de perlas por tipo es un múltiplo de $q$. Entonces siempre hay una repartición dando, para cada tipo, el mismo número de perlas a cada ladrón, es decir, una repartición justa.

Un collar abierto con $t$ tipos de perlas y tal que el número de perlas por tipo sea divisible por $q$ puede ser repartido equitativamente entre $q$ ladrones sin tener que cortarlo más de $t(q-1)$ veces.

Cuando solo hay dos ladrones, tenemos $q=2$ y el número de cortes necesarios es como máximo $t$.

Por supuesto, para el caso en que $q$ pueda ser arbitrario, la demostración recurre a herramientas matemáticas aún más avanzadas que el teorema de Borsuk-Ulam (excepto en casos simples, como el caso $t=2$ o como el caso en que cada tipo está presente exactamente $q$ veces : ambos quedan como un desafío para el lector). Y por supuesto, tampoco sabemos cómo encontrar una repartición justa de manera eficiente para esta generalización.

Dos tipos para cualquier número de ladrones

Probamos aquí el caso $t=2$ cuando $q$ es arbitrario. Como antes, los dos tipos considerados se denominan rojo y azul. La demostración funciona por inducción sobre $q$. Para $q=2$, el resultado se demostró anteriormente, con el argumento de la ventana de longitud constante moviéndose a lo largo del collar. Ahora supongamos que $q>2$. Consideramos una primera división potencial en $q$ partes, cortando el collar cada $n/q$ perlas, donde $n$ es el número total de perlas. Si cada una de las partes tiene el número correcto de perlas de cada uno de los dos tipos, tenemos una repartición justa en $q-1<2(q-1)$ cortes.

Por tanto, podemos suponer que hay una parte que tiene más de una fracción $1/q$ de las perlas rojas y otra menos. El mismo argumento de la ventana que se usó anteriormente lleva a la conclusión de que hay una posición (entre estas dos partes) que contiene el número correcto de perlas rojas (y, por lo tanto, el número correcto de perlas azules debido a su longitud). Retiramos las perlas contenidas en esta ventana, y aplicamos la hipótesis de inducción al resto del collar, para un número de ladrones igual a $q-1$, ya que las perlas extraídas ya han satisfecho a un ladrón. Los dos extremos de la ventana son dos cortes adicionales y, por lo tanto, tenemos un total de $2+2(q-2)=2(q-1)$ cortes como máximo, lo que completa la inducción.

Cada tipo se presenta exactamente $q$ veces

La prueba es casi idéntica a la del caso con dos ladrones y dos perlas por tipo dada en el recuadro de arriba. También se revisan las perlas, de izquierda a derecha, y siempre se asigna la perla en cuestión al ladrón actual. Cuando llegamos a un tipo que ya tiene el ladrón actual, elegimos otro ladrón actual que aún no tenga de este tipo. Tiene que haber uno, porque el número de perlas por tipo es igual al número de ladrones. El resto de la demostración es idéntica.

Incluso hay una generalización de esta generalización, en el caso de que el número de cuentas no sea un múltiplo de $q$. Los ladrones entonces estiman que una repartición es justa si, para cada tipo, ven que el número de perlas recibidas difiere como máximo en una unidad. Pero el teorema sigue siendo el mismo : siempre existe una repartición justa que no requiere más de $t(q-1)$ cortes.

En el origen : motivaciones prácticas

El teorema del collar y las preguntas asociadas con él son principalmente teoría. La repartición justa deseada por los ladrones es una forma de poner en escena el teorema y no es en absoluto una motivación práctica real. Dicho esto, son de hecho tales motivaciones las que están en su origen. Fue durante el trabajo en el diseño de circuitos integrados que dos investigadores estadounidenses, Bhatt y Leiserson [BL81], llegaron a formularlo como una conjetura a principios de la década de 1980. Esto último no les servía directamente, pero el caso particular con dos tipos de perlas les sirvió en un algoritmo para ordenar componentes electrónicos, y naturalmente se preguntaron el caso con más de dos tipos.

Lo curioso es que este teorema experimentó la misma historia por segunda vez. En la década de 2000, tres investigadores alemanes, Epping, Hochstättler y Oertel [EHO04], lo formularon nuevamente como una conjetura mientras realizaban un trabajo aplicado en un contexto de producción automotriz. No sabían que ya era un teorema, pero este desconocimiento no es tan sorprendente : la cantidad de resultados matemáticos que se publican cada año es tan gigantesca que es común perderse ciertos resultados, incluso relevantes para la propia investigación. Más concretamente, estaban interesados ​​en el problema de optimizar las operaciones de pintura en las líneas de montaje de automóviles. Un caso muy particular de su problema -demasiado particular para ser realista, aunque bastante natural- coincidió con el problema de dividir el collar a los $q$ ladrones, y naturalmente conjeturaron el límite $t(q-1)$.

Muchas aplicaciones concretas se benefician del poder de las herramientas matemáticas teóricas. Estas dos historias ilustran lo recíproco : la investigación fundamental en matemáticas a menudo se nutre de motivaciones prácticas.

Referencias

[AW86] N. Alon et D. West, The Borsuk-Ulam theorem and bisection of necklaces, Proceedings of the American Mathematical Society 98 (1986), 623-628.

[A87] N. Alon, Splitting necklaces, Advances in Mathematics 63 (1987), 247-253.

[BL81] S. N. Bhatt et C. E. Leiserson, How to assemble tree machines (extended abstract), Proceedings of the 14th Symposium on the Theory of Computing (1981), 99-104.

[EHO04] T. Epping, W. Hochstättler et P. Oertel, Complexity results on a paint shop problem, Discrete Applied Mathematics 136 (2004), 217-226.

[GW85] C. H. Goldberg et D. West, Bisection of circle colorings, SIAM Journal of Algebraic Discrete Methods 6 (1985), 93-106.

Post-scriptum :

El autor y los editores de Images des Maths quisieran agradecer a los revisores, agirand y François Guéritaud por su cuidadosa revisión y juiciosos comentarios.

Article original édité par Élise Janvresse

Partager cet article

Pour citer cet article :

Andrés Navas, Edgard Araya, Pilar Garcés — «El problema del collar» — Images des Mathématiques, CNRS, 2022

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?