5
$\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 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.

$\endgroup$
  • 4
    $\begingroup$ What do you think? Have you tried solving this problem? $\endgroup$ – Yuval Filmus Oct 14 '16 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 '16 at 15:59
  • 3
    $\begingroup$ Please define your cost measure. What is "optimal" here? $\endgroup$ – Raphael Oct 14 '16 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 '16 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$ – Adrian Maire Oct 14 '16 at 19:42
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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:

orderFactorsDecreasing(factors)
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.
| cite | improve this answer | |
$\endgroup$
  • $\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$ – David Richerby Oct 24 '16 at 7:51
  • $\begingroup$ Is the worse case meaning: you will not find any case which optimal cut is worse than the MCM. $\endgroup$ – Adrian Maire Oct 24 '16 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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