# Necklace problem

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 $n$ 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 $k$ black beads. For instance, for $k=2$ , the specified information gives the number of pairs of black beads that are separated by $i$ positions, for $i=0,\dots \lfloor n/2-1\rfloor$ . This can be made formal by defining a $k$ -configuration to be a necklace of $k$ black beads and $n-k$ white beads, and counting the number of ways of rotating a $k$ -configuration so that each of its black beads coincides with one of the black beads of the given necklace.

The necklace problem asks: if $n$ is given, and the numbers of copies of each $k$ -configuration are known up to some threshold $k\leq K$ , how large does the threshold $K$ need to be before this information completely determines the necklace that it describes? Equivalently, if the information about $k$ -configurations is provided in stages, where the $k$ th stage provides the numbers of copies of each $k$ -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.