Necklace problem
From Wikipedia, the free encyclopedia
The necklace problem is a problem in recreational mathematics, solved in the early 21st century.
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 you will have to go through in order to be able to distinguish any different necklaces?
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.
[edit] References
- Alon, N.; Caro, Y.; Krasikov, I.; Roditty, Y. Combinatorial reconstruction problems. J. Combin. Theory Ser. B 47 (1989), 153–161.
- Radcliffe, A. J.; Scott, A. D. Reconstructing subsets of Zn. J. Combin. Theory Ser. A 83 (1998), 169–187.
- Pebody, Luke, The reconstructibility of finite abelian groups, Combin. Probab. Comput. 13 (2004), 867–892.
