# 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 ${\displaystyle 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 ${\displaystyle k}$ black beads. For instance, for ${\displaystyle k=2}$, the specified information gives the number of pairs of black beads that are separated by ${\displaystyle i}$ positions, for ${\displaystyle i=0,\dots \lfloor n/2-1\rfloor }$. This can be made formal by defining a ${\displaystyle k}$-configuration to be a necklace of ${\displaystyle k}$ black beads and ${\displaystyle n-k}$ white beads, and counting the number of ways of rotating a ${\displaystyle 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 ${\displaystyle n}$ is given, and the numbers of copies of each ${\displaystyle k}$-configuration are known up to some threshold ${\displaystyle k\leq K}$, how large does the threshold ${\displaystyle K}$ need to be before this information completely determines the necklace that it describes? Equivalently, if the information about ${\displaystyle k}$-configurations is provided in stages, where the ${\displaystyle k}$th stage provides the numbers of copies of each ${\displaystyle 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.