Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Necklace problem

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated August 13, 2026

The necklace problem is a problem in recreational mathematics concerning the reconstruction of necklaces (cyclic arrangements of binary values) from partial information.

01Formulation

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 kth 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?

02Upper 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.

Watch videos about Necklace problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Necklace problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Necklace (combinatorics)

In combinatorics, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads which have k available colors.

Necklace (combinatorics)

In combinatorics, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads which have k available colors.

Necklace polynomial

In combinatorial mathematics, the necklace polynomial, or Moreau's necklace-counting function, introduced by C. Moreau, counts the number of distinct necklaces of n {\displaystyle n} colored beads chosen out of k {\displaystyle k} available colors, arranged in a cycle. Unlike the usual problem of graph coloring, the necklaces are assumed to be aperiodic (not composed from a repeated subsequence), and counted up to rotation (rotating the beads around the necklace counts as the same necklace), but without flipping over (reversing the order of the beads counts as a different necklace).