*** Welcome to piglix ***

Necklace splitting problem


Necklace splitting is a picturesque name given to several related problems in combinatorics and measure theory. Its name and solutions are due to mathematicians Noga Alon and Douglas B. West.

The basic setting involves a necklace with beads of different colors. The necklace should be divided between several partners, such that each partner receives the same amount of every color. Moreover, the number of cuts should be as small as possible (in order to waste as little as possible of the metal in the links between the beads).

The following variants of the problem have been solved in the original paper:

Each problem can be solved by the next problem:

The case can be proved by the Borsuk-Ulam theorem.

When is an odd prime number, the proof involves a generalization of the Borsuk-Ulam theorem.

When is a composite number, the proof is as follows (demonstrated for the measure-splitting variant). Suppose . There are measures, each of which values the entire necklace as . Using cuts, divide the necklace to parts such that measure of each part is exactly . Using cuts, divide each part to parts such that measure of each part is exactly . All in all, there are now parts such that measure of each part is exactly . The total number of cuts is plus which is exactly .


...
Wikipedia

...