Editing Necklace problem

{{about|identifying the order of jewels on a necklace|the combinatorial [[fair division]] problem|Necklace splitting problem}}

The '''necklace problem''' is a problem in [[recreational mathematics]] concerning the reconstruction of [[Necklace (combinatorics)|necklaces]] (cyclic arrangements of binary values) from partial information.

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

The necklace problem asks: if <math>n</math> is given, and the numbers of copies of each <math>k</math>-configuration are known up to some threshold <math>k\le K</math>, how large does the threshold <math>K</math> need to be before this information completely determines the necklace that it describes? Equivalently, if the information about <math>k</math>-configurations is provided in stages, where the <math>k</math>th stage provides the numbers of copies of each <math>k</math>-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 ==
[[Noga Alon|Alon]], [[Yair Caro|Caro]], [[Ilia Krasikov|Krasikov]] and [[Yehuda Roditty|Roditty]] showed that 1 + log<sub>2</sub>(''n'') is sufficient, using a cleverly enhanced [[inclusion–exclusion principle]].

[[Jamie Radcliffe|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.

==See also==

* [[Necklace (combinatorics)]]
* [[Bracelet (combinatorics)]]
* [[Moreau's necklace-counting function]]
* [[Necklace splitting problem]]

== References ==
* {{cite journal |author1=Alon, N. |author2=Caro, Y. |author3=Krasikov, I. |author4=Roditty, Y. |title=Combinatorial reconstruction problems |journal=[[J. Combin. Theory Ser. B]] |volume=47 |year=1989 |issue=2 |pages=153–161 |doi=10.1016/0095-8956(89)90016-6|doi-access=free |citeseerx=10.1.1.300.9350 }}
* {{cite journal |author1=Radcliffe, A. J. |author2=Scott, A. D. |title=Reconstructing subsets of ''Z''<sub>''n''</sub> |journal=[[J. Combin. Theory Ser. A]] |volume=83 |year=1998 |issue=2 |pages=169–187 |doi=10.1006/jcta.1998.2870|doi-access=free }}
* {{cite journal |author=Pebody, Luke |title=The reconstructibility of finite abelian groups |journal=[[Combin. Probab. Comput.]] |volume=13 |year=2004 |issue=6 |pages=867–892 |doi=10.1017/S0963548303005807|doi-broken-date=11 March 2025 |s2cid=37756823 }}
* {{cite journal |author=Pebody, Luke |title=Reconstructing Odd Necklaces |journal=Combin. Probab. Comput. |volume=16 |year=2007 |issue=4 |pages=503–514 |doi=10.1017/S0963548306007875|doi-broken-date=11 March 2025 |s2cid=13278945 }}
* {{cite conference |author=Paul K. Stockmeyer |contribution=The charm bracelet problem and its applications |title=Graphs and Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University, June 18–22, 1973 | series=Lecture Notes in Mathematics |volume=406 |year=1974 |pages=339–349 |doi=10.1007/BFb0066456| isbn = 978-3-540-06854-9|editor1-first=Ruth A.|editor1-last= Bari|editor1-link=Ruth Aaronson Bari|editor2-first=Frank|editor2-last=Harary|editor2-link=Frank Harary }}

[[Category:Combinatorics on words]]
[[Category:Recreational mathematics]]