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:
“What is history? Its beginning is that of the centuries of systematic work devoted to the solution of the enigma of death, so that death itself may eventually be overcome. That is why people write symphonies, and why they discover mathematical infinity and electromagnetic waves.”
—Boris Pasternak (1890–1960)
“There is a lot of talk now about metal detectors and gun control. Both are good things. But they are no more a solution than forks and spoons are a solution to world hunger.”
—Anna Quindlen (b. 1953)
“I can’t quite define my aversion to asking questions of strangers. From snatches of family battles which I have heard drifting up from railway stations and street corners, I gather that there are a great many men who share my dislike for it, as well as an equal number of women who ... believe it to be the solution to most of this world’s problems.”
—Robert Benchley (1889–1945)