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 x 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 x 1 + 2 x 2 = 7.

enter image description here

What is the optimal solution for the general problem?

Thanks, Humberto.

  • 4
    $\begingroup$ What do you think? Have you tried solving this problem? $\endgroup$ Oct 14, 2016 at 15:54
  • 2
    $\begingroup$ I like the answer, because I like big chunks of chocolate, but in this case you could have done with 5 cuts. $\endgroup$
    – gnasher729
    Oct 14, 2016 at 15:59
  • 3
    $\begingroup$ Please define your cost measure. What is "optimal" here? $\endgroup$
    – Raphael
    Oct 14, 2016 at 17:41
  • 3
    $\begingroup$ If I arrange bars in a 2D plane and then use a very long knife to cut them simultaneously, is that one cut? $\endgroup$
    – orlp
    Oct 14, 2016 at 18:25
  • $\begingroup$ Is it required to give equally big chunks to each person? or you may give (e.g.) 5/6 of a bar to 5 and 5x1/6 to the last? $\endgroup$ Oct 14, 2016 at 19:42

2 Answers 2


If optimal means having less cuts, can do this:

1. Line the chocolate bar up.
   [bar 0][bar 1][bar 2]

2. Treat that as a big bar.
   [big bar            ]

3. Divide the big bar equally. 

Only about N cuts needed (if B < N)

If B > N, just give everyone equal number of bars. Then divide the remaining bars with the above algorithm.

Or 1 cut:

[bar 0]
  [bar 1]
    [bar 2]

cut vertically once.

I am sure there might be easier way to line it up... if optimal means that we don't need to use a ruler to measure the chocolates in real life.


Considering the minimum common multiple of N and B: mcm, it is the worse case for the given N and B. (You will find no N+B where the optimal cut is worse than its MCM)

e.g. B=5, N=6 -> mcm = 30

The value of mcm can be factorized into prime numbers (factors). Each of the mcm little chunks could be grouped using those values and minimize the number of cuts.

Each factor can be used or not depending of your custom rules, in this case, allowing only chunks of equal size for all N persons.

Example of algorithm:

remainingB = B
foreach (f in factors)
    while ( acceptChunkGrouping( f ) ) // yes, can be flattened easily.
        distributeToEachPerson( f*B/mcm )
        remainingB -= N *  (f*B/mcm )

Following your example of B=5, N=6, mcm=30: factorization of 30 is: (1), 2, 3, 5, 6:

  • Chunks of 6*(1/6) -> rejected as there are no N x (1/6) chunks available.
  • Chunks of 5*(1/6) -> rejected as there are no N x (5/6) chunks available.
  • Chunks of 3*(1/6) -> Allowing N x (3/6) -> remaining 2 bars.
  • Chunks of 2*(1/6) -> Allowing N x (2/6) -> remaining 0 bars.
  • chunks of 1*(1/6) -> rejected as there are no N x (1/6) chunks available.

To force each person having chunks of the same size, the test could be:

var chunksPerBar = floor(1 / (factor*B/mcm))
if (chunksPerBar*remainingB >= N) then acceptTheFactor
else rejectTheFactor

An other example:

  • B=26, N=4;
  • mcm = 52;
  • factors: 13, 2, (2), 1
    • 13 is rejected.
    • 2 is accepted, giving 6 full bars to each N persons.
    • 1 is accepted, giving 0.5 bars to each N persons.
  • Each person get 6 full bars + 1/2 bar.
  • $\begingroup$ The least common multiple isn't the worst case, because there is no worst case. You could cut each chocolate bar into a million pieces and give everybody the appropriate amount of chocolate dust. $\endgroup$ Oct 24, 2016 at 7:51
  • $\begingroup$ Is the worse case meaning: you will not find any case which optimal cut is worse than the MCM. $\endgroup$ Oct 24, 2016 at 7:56

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.