El problema del collar es un problema de matemáticas recreativas que trata de la reconstrucción de collares (disposiciones cíclicas de valores binarios) a partir de información parcial.
El problema del collar implica la reconstrucción de un collar de cuentas, cada una de las cuales es negra o blanca, a partir de información parcial. La información especifica cuántas copias contiene el collar de cada posible disposición de cuentas negras. Por ejemplo, para , la información especificada proporciona el número de pares de cuentas negras que están separadas por posiciones, para . Esto se puede formalizar definiendo una -configuración como un collar de cuentas negras y cuentas blancas, y contando el número de formas de rotar una -configuración de modo que cada una de sus cuentas negras coincida con una de las cuentas negras del collar dado.
El problema del collar plantea la siguiente pregunta: si se proporciona , y se conocen los números de copias de cada configuración hasta un cierto umbral , ¿qué tan grande debe ser el umbral para que esta información determine por completo el collar que describe? De manera equivalente, si la información sobre las configuraciones se proporciona en etapas, donde la etapa n proporciona los números de copias de cada configuración, ¿cuántas etapas se necesitan (en el peor de los casos) para reconstruir el patrón preciso de cuentas blancas y negras en el collar original?
Alon , Caro, Krasikov y Roditty demostraron que 1 + log 2 ( n ) es suficiente, utilizando un principio de inclusión-exclusión inteligentemente mejorado .
Radcliffe y Scott demostraron que si n es primo, 3 es suficiente, y para cualquier n , 9 veces el número de factores primos de n es suficiente.
Pebody demostró que para cualquier n , 6 es suficiente y, en un artículo posterior, que para n impar , 4 es suficiente. Conjeturó que 4 es suficiente nuevamente para n par mayor que 10, pero esto aún no se ha demostrado.
