Necklace splitting problem

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

1. Discrete splitting:[1]^{: Th 1.1} The necklace has ${\displaystyle k\cdot n}$ beads. The beads come in ${\displaystyle t}$ different colors. There are ${\displaystyle k\cdot a_{i}}$ beads of each color ${\displaystyle i}$, where ${\displaystyle a_{i}}$ is a positive integer. Partition the necklace into ${\displaystyle k}$ parts (not necessarily contiguous), each of which has exactly ${\displaystyle a_{i}}$ beads of color i. Use at most ${\displaystyle (k-1)t}$ cuts. Note that if the beads of each color are contiguous on the necklace, then at least ${\displaystyle k-1}$ cuts must be done inside each color, so ${\displaystyle (k-1)t}$ is optimal.
2. Continuous splitting:[1]^{: Th 2.1} The necklace is the real interval ${\displaystyle [0,k\cdot n]}$. Each point of the interval is colored in one of ${\displaystyle t}$ different colors. For every color ${\displaystyle i}$, the set of points colored by ${\displaystyle i}$ is Lebesgue-measurable and has length ${\displaystyle k\cdot a_{i}}$, where ${\displaystyle a_{i}}$ is a non-negative real number. Partition the interval to ${\displaystyle k}$ parts (not necessarily contiguous), such that in each part, the total length of color ${\displaystyle i}$ is exactly ${\displaystyle a_{i}}$. Use at most ${\displaystyle (k-1)t}$ cuts.
3. Measure splitting:[1]^{: Th 1.2} The necklace is a real interval. There are ${\displaystyle t}$ different measures on the interval, all absolutely continuous with respect to length. The measure of the entire necklace, according to measure ${\displaystyle i}$, is ${\displaystyle k\cdot a_{i}}$. Partition the interval to ${\displaystyle k}$ parts (not necessarily contiguous), such that the measure of each part, according to measure ${\displaystyle i}$, is exactly ${\displaystyle a_{i}}$. Use at most ${\displaystyle (k-1)t}$ cuts. This is a generalization of the Hobby–Rice theorem, and it is used to get an exact division of a cake.

Each problem can be solved by the next problem:

• Discrete splitting can be solved by continuous splitting, since a discrete necklace can be converted to a coloring of the real interval ${\displaystyle [0,k\cdot n]}$ in which each interval of length 1 is colored by the color of the corresponding bead. In case the continuous splitting tries to cut inside beads, the cuts can be slid gradually such that they are made only between beads.[1]^: 249
• Continuous splitting can be solved by measure splitting, since a coloring of an interval in ${\displaystyle t}$ colors can be converted to a set ${\displaystyle t}$ measures, such that measure ${\displaystyle i}$ measures the total length of color ${\displaystyle i}$. The opposite is also true: measure splitting can be solved by continuous splitting, using a more sophisticated reduction.[1]^{: 252–253}

The case ${\displaystyle k=2}$ can be proved by the Borsuk-Ulam theorem.[2]

When ${\displaystyle k}$ is an odd prime number, the proof involves a generalization of the Borsuk-Ulam theorem.[3]

When ${\displaystyle k}$ is a composite number, the proof is as follows (demonstrated for the measure-splitting variant). Suppose ${\displaystyle k=p\cdot q}$. There are ${\displaystyle t}$ measures, each of which values the entire necklace as ${\displaystyle p\cdot q\cdot a_{i}}$. Using ${\displaystyle (p-1)\cdot t}$ cuts, divide the necklace to ${\displaystyle p}$ parts such that measure ${\displaystyle i}$ of each part is exactly ${\displaystyle q\cdot a_{i}}$. Using ${\displaystyle (q-1)\cdot t}$ cuts, divide each part to ${\displaystyle q}$ parts such that measure ${\displaystyle i}$ of each part is exactly ${\displaystyle a_{i}}$. All in all, there are now ${\displaystyle pq}$ parts such that measure ${\displaystyle i}$ of each part is exactly ${\displaystyle a_{i}}$. The total number of cuts is ${\displaystyle (p-1)\cdot t}$ plus ${\displaystyle p(q-1)\cdot t}$ which is exactly ${\displaystyle (pq-1)\cdot t}$.

• Combinatorial necklace
• Necklace problem
• Exact division

• "Sneaky Topology" on YouTube, an introductory video presenting the problem with its topological solution.