El problema del collar es un problema de las matemáticas recreativas que se refiere a la reconstrucción de collares (arreglos cíclicos de valores binarios) a partir de información parcial.
Formulación
El problema del collar implica la reconstrucción de un collar decuentas, 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 deperlas negras. Por ejemplo, para, la información especificada da el número de pares de cuentas negras que están separadas por posiciones, para . Esto puede formalizarse definiendo un-configuración para ser un collar de cuentas negras y cuentas blancas, y contando el número de formas de rotar un -configuración para que cada una de sus cuentas negras coincida con una de las cuentas negras del collar dado.
El problema del collar pregunta: si se da, y el número de copias de cada -Las configuraciones se conocen hasta cierto umbral , ¿qué tan grande es el umbral ¿Necesita estar antes de que esta información determine completamente el collar que describe? De manera equivalente, si la información sobre-configuraciones se proporcionan en etapas, donde el La etapa proporciona el número 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?
Límites superiores
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 de seguimiento, que para n impar , 4 es suficiente. Conjeturó que de nuevo 4 es suficiente incluso para n mayor que 10, pero esto sigue sin probarse.
Ver también
Referencias
- Alon, N .; Caro, Y .; Krasikov, I .; Roditty, Y. (1989). "Problemas de reconstrucción combinatoria" . J. Combin. Teoría Ser. B . 47 (2): 153-161. doi : 10.1016 / 0095-8956 (89) 90016-6 .
- Radcliffe, AJ; Scott, AD (1998). "Reconstrucción de subconjuntos de Z n ". J. Combin. Teoría Ser. Una . 83 (2): 169–187. doi : 10.1006 / jcta.1998.2870 .
- Pebody, Luke (2004). "La reconstruibilidad de grupos abelianos finitos". Combin. Probab. Computación. 13 (6): 867–892. doi : 10.1017 / S0963548303005807 .
- Pebody, Luke (2007). "Reconstruyendo collares impares". Combin. Probab. Computación . 16 (4): 503–514. doi : 10.1017 / S0963548306007875 .
- Paul K. Stockmeyer (1974). "El problema de las pulseras con dijes y sus aplicaciones". En Bari, Ruth A .; Harary, Frank (eds.). Gráficos y combinatoria: Actas de la conferencia Capital sobre teoría de gráficos y combinatoria en la Universidad George Washington, 18-22 de junio de 1973 . Apuntes de clase en matemáticas. 406 . págs. 339–349. doi : 10.1007 / BFb0066456 . ISBN 978-3-540-06854-9.