5
$\begingroup$

You have $n$ congruent sticks (they have the same length). You want to divide them equaly among $m$ friends. To avoid envy, each friend should receive congruent parts, that is, the set of cutted sticks of one friend is exactly the same of any other friend.

Questions: Which is the minimal number of cuts in terms of $n$ and $m$? Is there an algorithm to decide where to cut?

Without the congruence restriction on the received cutted sticks, the problem was solved here.

$\endgroup$
3
  • 1
    $\begingroup$ Can we throw away bits? If yes, how much can we throw away? Must our cuts be all 'proper': orthogonal to the sticks main direction and all the way through, or may we do arbitrary cuts at angles and arbitrary distances? Can we align bars to cut multiple at once with a single slice? We need a bit more information about how cuts are modeled in general. $\endgroup$
    – orlp
    Dec 28, 2016 at 17:17
  • $\begingroup$ Have you tried working through some examples? For instance, have you tried tabulating the minimum value for all combinations of $1 \le n,m \le 10$, and then looking for patterns in the result? I suspect the most interesting cases will be the ones where $\gcd(n,m)=1$, i.e., where $n$ and $m$ have no common factor. $\endgroup$
    – D.W. ♦
    Jan 4, 2017 at 1:02
  • $\begingroup$ @orlp, the cuts must be orthogonal to the sticks main direction (so, the problem is "unidimensional": sticks may be replaced by straight line segments). No, the idea is to solve to problem withtout throwing bits away. $\endgroup$
    – Humberto José Bortolossi
    Jan 5, 2017 at 12:58

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.