Which necklaces require maximal cuts?

Question

Given an unclasped necklace with $d$ types of beads and $p$ people it is well known we can fairly divide the necklace with at most $d(p-1)$ cuts. A fair division means that each person is given the same number of beads of type $i$ where $i \in \{1, \dots, d\}$. We also assume that the number of beads of type $i$ is divisible by $p$ for all $i \in \{1, \dots, d\}$.

I am curious if it is known which necklaces require $d(p-1)$ cuts. I cannot seem to find it in any of the literature but maybe one of you is aware of this result. Clearly a necklace which groups all of the beads of a type together will require the maximum number of cuts. You can also vary this idea and repeat a necklace of this type a specific number of times based on $p$. Is this it?

Edit: The proof of $d(p-1)$ cuts being optimal for $p$ people and $d$ beads is located here: http://ac.els-cdn.com/0001870887900557/1-s2.0-0001870887900557-main.pdf?_tid=ab3e4b8a-6bf5-11e7-8a41-00000aab0f27&acdnat=1500409034_155853417bd79ecefa7dbb07d38e83e9

Answer 1

I think the answer is "no".

Let's consider $p=2,d=3$. Suppose that we have a necklace which can be fairly divided using only 2 cuts (one less than the maximum number that may be required).

Let the types of the beads be 0, 1, and 2, and let the number of beads of type $i$ be $2a_i$.

Choose three vectors in the plane $v_0, v_1, v_2$ such that $\sum_i v_ia_i = 0$.

Represent the necklace as a walk in the plane: each time you see a bead of type $i$, take a step of direction $v_i$. Our choice of vectors means that this walk will return to its starting point.

We may as well assume that middle segment is one person's share: otherwise, one of the two cuts is serving no purpose, and we can delete it.

Note that, if the division is fair, then the middle part must correspond to a lattice walk that sums to zero. This requires that the two points at which we cut the walk must correspond to the same point in the plane.

In the event that we deleted a cut as above, then the position of the cut must coincide with the starting/ending point of the walk.

Therefore any closed, self-avoiding walk in the plane using $2a_i$ steps in the $v_i$ direction for each $i$, requires at least 3 cuts.

I haven't analyzed the situation for larger values of $d$ and $p$, but I don't see why it should become more regular.

EDIT SUMMARY: After clarification that the necklace was intended to start off as a line not a loop, I removed the case $d=2$, $p=2$, and revised the case $d=3$, $p=2$. Somewhat surprisingly, it still works almost the same way.

Answer 2

If you take an example when the beads of different types are grouped, and there are many beads of each type, then you can "perturbate" this example by adding a few more beads no matter where.

More generally, I don't think that the necklaces that require the most number of cuts have been classified.