Necklace problem

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

Formulation

Suppose that a person you are in contact with has a necklace of n beads, each of which is either black or white. You wish to identify the order in which the n beads go around the necklace. However, you are only given partial information. At stage k you are told, for each set of k beads, their relative location around the necklace.

The question is: given n, how many stages will you have to go through in order to be able to distinguish any different necklaces?

Solution

Alon, Caro, Krasikov and Roditty showed that 1 + log₂(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 Z_n". 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. 

See also

• Necklace (combinatorics)
• Bracelet (combinatorics)
• Moreau's necklace-counting function
• Necklace splitting problem