“Necklace problem”的意思、由来-开放百科全书

词条

Necklace problem

释义

Formulation
Solution
References
See also

{{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, solved in the early 21st century.

Formulation

The necklace problem involves the reconstruction of a necklace of n beads, each of which is either black or white, from partial information. A k-configuration in a necklace is a subset of k positions in the necklace; two configurations are isomorphic if one can be obtained from the other by a rotation of the necklace. At stage k of the reconstruction process, the partial information available at that stage is a count, for each k-configuration, of the number of k-configurations that are isomorphic to it and that contain only black beads. The necklace problem is: given n, 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?

Solution

Alon, Caro, Krasikov and Roditty showed that 1 + log₂(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.

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 |pages=153–161 |doi=10.1016/0095-8956(89)90016-6}}
{{cite journal |author1=Radcliffe, A. J. |author2=Scott, A. D. |title=Reconstructing subsets of Z_n |journal=J. Combin. Theory Ser. A |volume=83 |year=1998 |pages=169–187 |doi=10.1006/jcta.1998.2870}}
{{cite journal |author=Pebody, Luke |title=The reconstructibility of finite abelian groups |journal=Combin. Probab. Comput. |volume=13 |year=2004 |pages=867–892 |doi=10.1017/S0963548303005807}}
{{cite journal |author=Pebody, Luke |title=Reconstructing Odd Necklaces |journal=Combin. Probab. Comput. |volume=16 |year=2007 |pages=503–514 |doi=10.1017/S0963548306007875}}
{{cite journal |author=Paul K. Stockmeyer |title=The charm bracelet problem and its applications |journal=Lecture Notes in Mathematics |volume=406 |year=1974 |pages=339–349 |doi=10.1007/BFb0066456}}

Formulation

Solution

References

See also