Necklace problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about identifying the order of jewels on a necklace. For the combinatorial fair division problem, see Necklace splitting problem.

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

Formulation[edit]

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[edit]

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[edit]

  • 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. 

See also[edit]