The necklace problem is a problem in recreational mathematics concerning the reconstruction of necklaces (cyclic arrangements of binary values) from partial information.
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
, the specified information gives the number of pairs of black beads that are separated by
white beads, and counting the number of ways of rotating a
The necklace problem asks: if
need to be before this information completely determines the necklace that it describes?
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?
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.
He conjectured that 4 is again sufficient for even n greater than 10, but this remains unproven.