Skip to main content
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$.
Source Link
Hugh Thomas
  • 6.3k
  • 27
  • 50

I think the answer is "no". Let's restrict to the case of $p=2$. Clearly, if $d=2$, then any necklace at all requires $2=d(p-1)$ cuts.

Let's now 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

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 each of the two partsmiddle part must correspond to a lattice walkswalk that sumsums 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.

I think the answer is "no". Let's restrict to the case of $p=2$. Clearly, if $d=2$, then any necklace at all requires $2=d(p-1)$ cuts.

Let's now 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). 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.

Note that, if the division is fair, then each of the two parts must correspond to lattice walks that sum to zero. This requires that the two points at which we cut the walk must correspond to the same point in the plane.

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.

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.

Source Link
Hugh Thomas
  • 6.3k
  • 27
  • 50

I think the answer is "no". Let's restrict to the case of $p=2$. Clearly, if $d=2$, then any necklace at all requires $2=d(p-1)$ cuts.

Let's now 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). 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.

Note that, if the division is fair, then each of the two parts must correspond to lattice walks that sum to zero. This requires that the two points at which we cut the walk must correspond to the same point in the plane.

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.