ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

# Necklace problem

The necklace problem is a problem in recreational mathematics, solved in the early 21st century.

Suppose that a person you are in contact with has a necklace of n beads, each of which is either black or white. You wish to identify in what order the n beads go around the necklace. However, you are only given partial information. At stage k you are told, for each set of k beads, their relative location around the necklace.

The question is, given n, how many stages you will have to go through in order to be able to distinguish any different necklaces.

Alon, Caro, Krasikov and Roditty showed that one more than the base two logarithm of n is sufficient, using a cleverly enhanced exclusion-inclusion 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.

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.