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:
“Any solution to a problem changes the problem.”
—R.W. (Richard William)
“Coming out, all the way out, is offered more and more as the political solution to our oppression. The argument goes that, if people could see just how many of us there are, some in very important places, the negative stereotype would vanish overnight. ...It is far more realistic to suppose that, if the tenth of the population that is gay became visible tomorrow, the panic of the majority of people would inspire repressive legislation of a sort that would shock even the pessimists among us.”
—Jane Rule (b. 1931)
“Theres one solution that ends all lifes problems.”
—Chinese proverb.