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.

Improve this question
$\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$
    – Joel David Hamkins
    Commented 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
    Commented 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$
    – Joel David Hamkins
    Commented 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$
    – Joel David Hamkins
    Commented Oct 14, 2016 at 15:39

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .