# Necklace problem

The necklace problem is a problem in recreational mathematics, solved in the early 21st century.

## Formulation

The necklace problem involves the reconstruction of a necklace of n beads, each of which is either black or white, from partial information. A k-configuration in a necklace is a subset of k positions in the necklace; two configurations are isomorphic if one can be obtained from the other by a rotation of the necklace. At stage k of the reconstruction process, the partial information available at that stage is a count, for each k-configuration, of the number of k-configurations that are isomorphic to it and that contain only black beads. The necklace problem is: given n, how many stages are needed (in the worst case) in order to reconstruct the precise pattern of black and white beads in the original necklace?

## Solution

Alon, Caro, Krasikov and Roditty showed that 1 + log2(n) is sufficient, using a cleverly enhanced inclusion-exclusion principle.

Radcliffe and Scott showed that if n is prime, 3 is sufficient, and for any n, 9 times the number of prime factors of n is sufficient.

Pebody showed that for any n, 6 is sufficient.

## References

• Alon, N.; Caro, Y.; Krasikov, I.; Roditty, Y. (1989). "Combinatorial reconstruction problems". J. Combin. Theory Ser. B 47: 153–161. doi:10.1016/0095-8956(89)90016-6.
• Radcliffe, A. J.; Scott, A. D. (1998). "Reconstructing subsets of Zn". J. Combin. Theory Ser. A 83: 169–187. doi:10.1006/jcta.1998.2870.
• Pebody, Luke (2004). "The reconstructibility of finite abelian groups". Combin. Probab. Comput. 13: 867–892. doi:10.1017/S0963548303005807.
• Pebody, Luke (2007). "Reconstructing Odd Necklaces". Combin. Probab. Comput. 16: 503–514. doi:10.1017/S0963548306007875.
• Paul K. Stockmeyer (1974). "The charm bracelet problem and its applications". Lecture Notes in Mathematics 406: 339–349. doi:10.1007/BFb0066456.