Necklace problem

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

This article is about identifying the order of jewels on a necklace. For the combinatorial fair division problem, see Necklace splitting problem.

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.

gollark: This is technically considered metalcore and I don't know what a DragonForce is.
gollark: Weird quirk of either Icecast, MPD or YouTube I think.
gollark: People have mentioned the volume thing. I have no idea how it does that.
gollark: I will consign you to beespace.
gollark: Rude.

See also

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". 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.