4
$\begingroup$

What is the optimal way to cut $B$ chocolate bars to share equally between $N$ people?

Here is an example of different cuts for $B = 5$ chocolate bars and $N = 6$ people.

Strategy 1: cut each chocolate bar in $6$ equal parts and, then, give $5$ parts for each person. Number of cuts: $5 \times 5 = 25$.

enter image description here

Strategy 2: cut $3$ bars in $2$ equal parts and cut $2$ parts in $3$ equal parts and, then, give $1/2$ bar and $1/3$ bar for each person. Number of cuts: $3 \times 1 + 2 \times 2 = 7$.

enter image description here

What is the optimal solution for the general problem?

Thanks, Humberto.

$\endgroup$
4
  • 1
    $\begingroup$ For the case $B=5$, $N=6$, you can cut $1/6$ off each bar, and give $5/6$ to each person. With 5 cuts, this is clearly optimal, in terms of minimizing the number of cuts, since you must cut each bar at least once. $\endgroup$ Oct 14, 2016 at 15:30
  • $\begingroup$ It's possible to get $N-\gcd{B,N}$ - arrange the bars in the line, flush against each other, and cut at integer multiples of $1/N$ times the length of the line, omitting any cuts that pass through the gaps between bars. This generalises the 5 in the case 5,6 from Joel's solution, and I believe it is always optimal though I don't have a proof. $\endgroup$
    – Will Sawin
    Oct 14, 2016 at 15:33
  • $\begingroup$ Are we assuming the bars are all identical? And that we can have perfect precision with measuring? And that people will agree on the measurements and the value of the pieces? Of course, there is a rich literature on division procedures if you deny these. But I take the problem here more naively. $\endgroup$ Oct 14, 2016 at 15:35
  • $\begingroup$ If we are allowed to cut through multiple bars at once, then do we regard my solution for the $5,6$ case as having only one cut? $\endgroup$ Oct 14, 2016 at 15:39

1 Answer 1

5
$\begingroup$

It takes $N - \gcd(B,N)$ cuts. To show this is sufficient, do as I said in a comment: - arrange the chocolate bars in a line, imagining them as giant chocolate bars, and cut them into pieces of length the total length over $N$, omitting cuts that pass through the gaps between the bars. The number of cuts needed is $N- \gcd(B,N)$.

To show this is necessary, suppose there are $N-C$ cuts, producing $N+B-C$ pieces. Draw a graph where the vertices are indexed by bars and people, with an edge connecting a bar to a person if and only if that person ate a piece of that bar. Because it has $N+B$ vertices and $N+B-C$ edges, there are at least $C$ connected components. But each connected component with $k$ bars and $l$ people must itself be a fair distribution and thus satisfy $k/B =l /N$, which implies that $k$ is divisible by $B/\gcd(B,N)$. Hence there are at most $\gcd(B,N)$ components, so $C \leq \gcd(B,N)$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.