Necklace 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 order to reconstruct the precise pattern of black and white beads in the original necklace?

Solution

, Caro, Krasikov and Roditty showed that 1 + log2 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.