Necklace problem
≈ 2 min read
Names in other languages
- Українськазадача про відновлення намиста
- РусскийЗадача о восстановлении бус
- EnglishNecklace problem
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The necklace problem is a problem in recreational mathematics concerning the reconstruction of necklaces (cyclic arrangements of binary values) from partial information.
The necklace problem is a problem in recreational mathematics concerning the reconstruction of necklaces (cyclic arrangements of binary values) from partial information. 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\le 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?
See also
Necklace (combinatorics) Bracelet (combinatorics) Moreau's necklace-counting function Necklace splitting problem
Text derived from https://en.wikipedia.org/w/index.php?oldid=1369243004 under CC BY-SA 4.0; modifications have been made.