Splitting necklaces (Q1097280)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Splitting necklaces |
scientific article |
Statements
Splitting necklaces (English)
0 references
1987
0 references
Let N be an opened necklace with \(k\cdot a_ i\) beads of color i, \(1\leq i\leq t\). A k-splitting of this necklace is a partition of the necklace into k parts, each consisting of a finite number of nonoverlapping intervals of beads whose union captures precisely \(a_ i\) beads of color i, \(1\leq i\leq t\). The size of the k-splitting is the number of cuts that form the intervals of the splitting, which is one less than the total number of these intervals. The main result is the following theorem: Every necklace with \(k\cdot a_ i\) beads of color i, \(1\leq i\leq t\), has a k-splitting of size at most (k-1)\(\cdot t\). The number (k-1)\(\cdot t\) is best possible. The author formulates the continuous version of the k-splitting problem and proves that it generalizes the discrete one. The proof of this version is topological.
0 references
necklace
0 references
splitting
0 references
partition
0 references