Necklace problem explained
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
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
black beads. For instance, for
, the specified information gives the number of pairs of black beads that are separated by
positions, for
i=0,...,\lfloorn/2-1\rfloor
.This can be made formal by defining a
-configuration to be a necklace of
black beads and
white beads, and counting the number of ways of rotating a
-configuration so that each of its black beads coincides with one of the black beads of the given necklace.
The necklace problem asks: if
is given, and the numbers of copies of each
-configuration are known up to some threshold
, how large does the threshold
need to be before this information completely determines the necklace that it describes? Equivalently, if the information about
-configurations is provided in stages, where the
th stage provides the numbers of copies of each
-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 + 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 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
References
- Alon, N. . Caro, Y. . Krasikov, I. . Roditty, Y. . Combinatorial reconstruction problems . . 47 . 1989 . 2 . 153–161 . 10.1016/0095-8956(89)90016-6. free . 10.1.1.300.9350 .
- Radcliffe, A. J. . Scott, A. D. . Reconstructing subsets of Zn . . 83 . 1998 . 2 . 169–187 . 10.1006/jcta.1998.2870. free .
- Pebody, Luke . The reconstructibility of finite abelian groups . . 13 . 2004 . 6 . 867–892 . 10.1017/S0963548303005807. 37756823 .
- Pebody, Luke . Reconstructing Odd Necklaces . Combin. Probab. Comput. . 16 . 2007 . 4 . 503–514 . 10.1017/S0963548306007875. 13278945 .
- Paul K. Stockmeyer . The charm bracelet problem and its applications . 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 . 1974 . 339–349 . 10.1007/BFb0066456. 978-3-540-06854-9. Ruth A.. Bari. Ruth Aaronson Bari. Frank. Harary. Frank Harary .