Necklace problem

The necklace problem is a problem in recreational mathematics concerning the reconstruction of necklaces (cyclic arrangements of binary values) from partial information.

Formulation

The necklace problem involves the reconstruction of a necklace of ${\displaystyle n}$ beads, each of which is either black or white, from partial information. The information specifies how many copies the necklace contains of each possible arrangement of ${\displaystyle k}$ black beads. For instance, for ${\displaystyle k=2}$, the specified information gives the number of pairs of black beads that are separated by ${\displaystyle i}$ positions, for ${\displaystyle i=0,\dots \lfloor n/2-1\rfloor }$. This can be made formal by defining a ${\displaystyle k}$-configuration to be a necklace of ${\displaystyle k}$ black beads and ${\displaystyle n-k}$ white beads, and counting the number of ways of rotating a ${\displaystyle k}$-configuration so that each of its black beads coincides with one of the black beads of the given necklace.

The necklace problem asks: if ${\displaystyle n}$ is given, and the numbers of copies of each ${\displaystyle k}$-configurations are known up to some threshold ${\displaystyle k\leq K}$, how large does the threshold ${\displaystyle K}$ need to be before this information completely determines the necklace that it describes? Equivalently, if the information about ${\displaystyle k}$-configurations is provided in stages, where the ${\displaystyle k}$th stage provides the numbers of copies of each ${\displaystyle k}$-configuration, 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?

Upper bounds

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 and, in a followup paper, that for odd n, 4 is sufficient. He conjectured that 4 is again sufficient for even n greater than 10, but this remains unproven.

See also

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

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". In Bari, Ruth A.; Harary, Frank (eds.). Graphs and Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University, June 18–22, 1973. Lecture Notes in Mathematics. 406. pp. 339–349. doi:10.1007/BFb0066456. ISBN 978-3-540-06854-9.