Problema de restauración de cuentas
The Bead Restoration Problem es un entretenido problema matemático resuelto a principios del siglo XXI.
Redacción
El problema de recuperación de perlas requiere la recuperación de perlas que consisten en n perlas, cada una de las cuales es negra o blanca, dada la información parcial. Llamemos a una configuración k en cuentas un subconjunto de la posición k en cuentas. Dos configuraciones son isomorfas si una se puede obtener de la otra rotando cuentas. En el paso k del proceso de recuperación, se dispone de información parcial que contiene para cada k -configuración el número de k -configuraciones isomorfas a la misma , que contienen solo perlas negras. El problema es determinar el número de pasos para un n dado requerido (en el peor de los casos) para restaurar exactamente la alternancia de cuentas blancas y negras.
Solución
Alon , Karo, Krasikov y Roditti demostraron que los pasos son suficientes utilizando un principio de inclusión-exclusión ingeniosamente mejorado .
Radcliffe y Scott demostraron que en el caso de n primo, 3 pasos son suficientes, y para n arbitrario , 9 veces el número de factores primos de n es suficiente .
Luke Pebody demostró que para cualquier n , 6 pasos son suficientes.
Véase también
- Pulsera y Abalorios
- Función de conteo de cuentas de Moro
- Problema de corte de collar
Notas
Literatura
- Alon N., Caro Y., Krasikov I., Roditty Y. Problemas de reconstrucción combinatoria // J. Combin. Teoría Ser. segundo _ - 1989. - T. 47 . — S. 153–161 . - doi : 10.1016/0095-8956(89)90016-6 .
- Radcliffe A. J., Scott AD Reconstrucción de subconjuntos de Z n // J. Combin. Teoría Ser. A._ _ - 1998. - T. 83 . — S. 169–187 . -doi : 10.1006/ jcta.1998.2870 .
- Lucas Pebody. La reconstructibilidad de grupos abelianos finitos // Combin. probable computar . - 2004. - T. 13 . — S. 867–892 . -doi : 10.1017/ S0963548303005807 .
- Lucas Pebody. Reconstruyendo collares impares // Combin. probable Informática.. - 2007. - T. 16 . — S. 503–514 . -doi : 10.1017/ S0963548306007875 .