Necklace problemThe 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.