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.
Read more about this topic: Necklace Problem
Famous quotes containing the word solution:
“Give a scientist a problem and he will probably provide a solution; historians and sociologists, by contrast, can offer only opinions. Ask a dozen chemists the composition of an organic compound such as methane, and within a short time all twelve will have come up with the same solution of CH4. Ask, however, a dozen economists or sociologists to provide policies to reduce unemployment or the level of crime and twelve widely differing opinions are likely to be offered.”
—Derek Gjertsen, British scientist, author. Science and Philosophy: Past and Present, ch. 3, Penguin (1989)
“The Settlement ... is an experimental effort to aid in the solution of the social and industrial problems which are engendered by the modern conditions of life in a great city. It insists that these problems are not confined to any one portion of the city. It is an attempt to relieve, at the same time, the overaccumulation at one end of society and the destitution at the other ...”
—Jane Addams (1860–1935)
“I herewith commission you to carry out all preparations with regard to ... a total solution of the Jewish question in those territories of Europe which are under German influence.... I furthermore charge you to submit to me as soon as possible a draft showing the ... measures already taken for the execution of the intended final solution of the Jewish question.”
—Hermann Goering (1893–1946)