Necklace problem

Necklace problem

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

Contents

Formulation

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 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, Caro, Krasikov and Roditty showed that 1 + log2(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

  • Alon, N.; Caro, Y.; Krasikov, I.; Roditty, Y. (1989). "Combinatorial reconstruction problems". J. Combin. Theory Ser. B 47: 153–161. doi:10.1016/0095-8956(89)90016-6. 
  • Radcliffe, A. J.; Scott, A. D. (1998). "Reconstructing subsets of Zn". J. Combin. Theory Ser. A 83: 169–187. doi:10.1006/jcta.1998.2870. 
  • Pebody, Luke (2004). "The reconstructibility of finite abelian groups". Combin. Probab. Comput. 13: 867–892. doi:10.1017/S0963548303005807. 
  • Pebody, Luke (2007). "Reconstructing Odd Necklaces". Combin. Probab. Comput. 16: 503–514. doi:10.1017/S0963548306007875. 
  • Paul K. Stockmeyer (1974). "The charm bracelet problem and its applications". Lecture Notes in Mathematics 406: 339–349. doi:10.1007/BFb0066456. 

See also


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • 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 [1] and Douglas B. West.[2] Suppose a necklace, open …   Wikipedia

  • 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. It represents a structure with n circularly connected beads of up to k different colors …   Wikipedia

  • Necklace — For other uses, see Necklace (disambiguation). A bead crochet necklace made from crochet lace, sterling silver, and freshwater pearls. A necklace is an article of jewellery which is worn around the neck. Necklaces are frequently formed from a… …   Wikipedia

  • Necklace (disambiguation) — A necklace is an article of jewelry worn around the neck. Necklace may also refer to: Necklace (combinatorics) or fixed necklace, a concept in combinatorial mathematics The Necklace , a short story by Guy de Maupassant The Necklace , an episode… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

  • List of mathematics articles (N) — NOTOC N N body problem N category N category number N connected space N dimensional sequential move puzzles N dimensional space N huge cardinal N jet N Mahlo cardinal N monoid N player game N set N skeleton N sphere N! conjecture Nabla symbol… …   Wikipedia

  • Luke Pebody — Luke Thomas Pebody (born 1977) is a mathematician who solved the necklace problem. Educated at Rugby School, Luke Pebody was admitted to Cambridge University at the age of 14 to read mathematics. He went up when he was 16, making him one of the… …   Wikipedia

  • Inclusion-exclusion principle — In combinatorial mathematics, the inclusion exclusion principle (also known as the sieve principle) states that if A 1, ..., A n are finite sets, then:egin{align}iggl|igcup {i=1}^n A iiggr| {} =sum {i=1}^nleft|A i ight sum {i,j,:,1 le i < j… …   Wikipedia

  • Topological combinatorics — The discipline of combinatorial topology used combinatorial concepts in topology and in the early 20th century this gradually turned into the field of algebraic topology. In 1978 the situation was reversed when methods from algebraic topology… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”