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:
“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)
“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)
“To the questions of the officiously meddling police Falter replied absently and tersely; but, when he finally grew tired of this pestering, he pointed out that, having accidentally solved “the riddle of the universe,” he had yielded to artful exhortation and shared that solution with his inquisitive interlocutor, whereupon the latter had died of astonishment.”
—Vladimir Nabokov (1899–1977)