|
|
|
|
|
Necklace ProblemMoreau's necklace-counting function treats a problem that is not only recreational.
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 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.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|