The necklace problem is a problem in recreational mathematics

Recreational mathematics

Recreational mathematics is an umbrella term, referring to mathematical puzzles and mathematical games.Not all problems in this field require a knowledge of advanced mathematics, and thus, recreational mathematics often attracts the curiosity of non-mathematicians, and inspires their further study...

, solved in the early 21st century

21st century

The 21st century is the current century of the Anno Domini era or the Common Era in accordance with the Gregorian calendar. The century began on January 1, 2001 and will end on December 31, 2100. The years from 2001 to 2010 are historical; the years from 2011 to 2100 are subject to futurology and...

.

Formulation

Suppose that a person you are in contact with has a necklace

Necklace (combinatorics)

In combinatorics, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations as equivalent...

 of n beads, each of which is either black or white. You wish to identify the order in which 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 will you have to go through in order to be able to distinguish any different necklaces?

Solution

Alon

Noga Alon

Noga Alon is an Israeli mathematician noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.- Academic background :...

, Caro, Krasikov and Roditty showed that 1 + log₂(n) is sufficient, using a cleverly enhanced inclusion-exclusion principle

Inclusion-exclusion principle

In combinatorics, the inclusion–exclusion principle is an equation relating the sizes of two sets and their union...

.

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

Luke Pebody

Luke Thomas Pebody is a mathematician who solved the necklace problem. Educated at Rugby School, and competing three times in the International Mathematical Olympiad, Luke Pebody was admitted to Cambridge University at the age of 14 to read mathematics...

 showed that for any n, 6 is sufficient.

See also

• Necklace (combinatorics)
  Necklace (combinatorics)
  In combinatorics, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations as equivalent...
  
  
• Bracelet (combinatorics)
• Moreau's necklace-counting function
• Necklace splitting problem
  Necklace splitting problem
  In mathematics, and in particular combinatorics, the necklace splitting problem arises in a variety of contexts including exact division; its picturesque name is due to mathematicians Noga Alon and Douglas B. West....