Necklace problem

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

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.

References

See also

This article is issued from Wikipedia - version of the Sunday, August 19, 2012. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.