3
$\begingroup$

You are going to meet your school friends after four years. You are very excited about it. You have planned to gift everyone a chocolate.

On the day of get-together you meet everyone and feel happy to share the sweet old memories. Everyone is glad to meet old pals, there are hugs all around, cheers and laughter and smile. Suddenly, you see that girl you had a crush on. All those nostalgic feelings about your shyness and fantasies are revived. You come back to your senses and you decide that you will give most of the chocolates to her and distribute rest chocolates as supper.

As the dinner is about to start in about half an hour, you have to start the job of cutting chocolates into smaller pieces quickly.

A chocolate is a cuboid of size $10$cm x $4$cm x $2$cm .

You go to your room of the hotel and cut chocolates as following:

  1. You open the wrappers of half the chocolates(as the half would be used to impress your 'first love').
  2. You put some pieces of chocolate together on the table and cut them with a knife at one time. You can cut as many pieces of chocolate as you want to give to others.
  3. Then you think that it'd be better to get unit-size pieces(cubes of size $1$×$1$×$1$) and then give the pieces accordingly.

Since you are really short of time, you want to calculate the minimum number of cuts required for the above said method. The question is:

What should be your strategy for minimum cuts of chocolates? (and what is minimum no. of cuts for this)

Assumptions:

  • The exact number of friends who will come to party is not known. Assume it to be $S$ (where $S \ge 10$) and you have bought $S$ chocolates...
  • Your cutting speed is constant throughout.
  • Knife is long enough to cut in one swing ( or imagine you have a katana)!
  • Half of the chocolates will be gifted to that special girl ;)
Improve this question
$\endgroup$
3
  • $\begingroup$ What is the $S$ mentioned in the assumptions? $\endgroup$
    – Shagnik
    Jun 18, 2016 at 22:38
  • $\begingroup$ Also, is your knife sufficiently long that there are no limits to how many pieces you can cut simultaneously? $\endgroup$
    – Shagnik
    Jun 18, 2016 at 22:40
  • $\begingroup$ @Shagnik Edited for $s$ and yes, knife is long enough , you can assume that too. $\endgroup$
    – ABcDexter
    Jun 19, 2016 at 1:33

3 Answers 3

Reset to default
5
$\begingroup$

7 cuts

like this

  1. first cut - stack them on edge, draw your samurai sword and slice them into 10x4
  2. stack and cut those into 10x2
  3. stack and cut in half again to make 2x5x1 bars
  4. stack and cut those to make 2x3 and 3x2
  5. cut the 3x2 down to 2x2 and 2x1
  6. stack all the 2x2 and cut to make 2x1
  7. stack all the 2x1 and cut to to make 1x1

this probably works better with fudge than it would with hard chocolate.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is a good answer, can you generalise it for any $s$ $\endgroup$
    – ABcDexter
    Jun 19, 2016 at 15:07
  • 2
    $\begingroup$ @ABcDexter The answer doesn't depend on S. $\endgroup$
    – f''
    Jun 19, 2016 at 15:51
  • $\begingroup$ @f'' Please read the first assumption, "You have bought $S$ chocolates" and according to the method, $S/2$ chocolates are to be cut, so is $7*S/2$ optimal solution? (7 is as shown in other answer ) $\endgroup$
    – ABcDexter
    Jun 20, 2016 at 4:27
  • $\begingroup$ @ABcDexter Is this question from somewhere? It seems like you don't understand it yourself. $\endgroup$
    – f''
    Jun 20, 2016 at 4:41
  • $\begingroup$ This is the original problem, I just changed it a bit. $\endgroup$
    – ABcDexter
    Jun 20, 2016 at 6:39
5
$\begingroup$

I think we can show that Jasen's answer of

7 cuts

is the best you can possibly do.

It suffices to consider what happens to a single block of chocolate, because all the other blocks can be handled in parallel. When cutting this block, consider the dimensions of the largest piece we obtain. Each cut can reduce one of the dimensions by at most half. We start with dimensions 10 x 4 x 2. It takes one cut to reduce the 2 to a 1, two cuts to reduce the 4 to a 1, and at least four cuts to reduce the 10 to a 1. Since these cuts are all in different directions (recall that we are considering a single sub-block of chocolate at all times), they must be distinct, showing that at least seven cuts are required.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You're quite right, can you use the $S$ here, and make it a generic solution ? $\endgroup$
    – ABcDexter
    Jun 19, 2016 at 15:11
  • 1
    $\begingroup$ The answer shouldn't depend on $S$. In terms of a generic solution, if you want to take blocks of size $a \times b \times c$ and cut them into $1 \times 1 \times 1$ pieces, it should take $\lceil \log_2 a \rceil + \lceil \log_2 b \rceil + \lceil \log_2 c \rceil$ cuts. $\endgroup$
    – Shagnik
    Jun 19, 2016 at 15:58
  • 1
    $\begingroup$ You should be able to cut any number of chocolates in $7$ cuts, by simply stacking all the pieces you have to cut on top of each other. The cuts then treat each piece of chocolate the same way, and so the answer for cutting $S/2$ pieces is the same as for cutting a single piece. $\endgroup$
    – Shagnik
    Jun 20, 2016 at 5:51
  • $\begingroup$ Yes, absolutely correct, I was overthinking :/ $\endgroup$
    – ABcDexter
    Jun 20, 2016 at 6:30
3
$\begingroup$

Few cuts, much ridiculousness:

0. Lay out all the chocolates that you want to turn into 1x1x1 cubes, end to end.
1. Turn the knife parallel to the table and cut through the middle to go from 1 layer 2cm thick to 2 layers each 1 cm thick.
2. Cut the long way once in the middle to go from 1 stripe 4cm thick to 2 stripes each 2cm thick.
3. Stack those on top of each other and cut down the middle again. Now the stripes are 1cm thick.
4. Make several stacks of those stripes, and/or line them up so the long edges touch, and cut down the middle to go from 1 band 10 cm wide to 2 bands 5cm wide.
5. Line up those and make a cut to divide them into 2cm and 3cm wide stripes.
6. Line up those and cut off 1 cm.
7. Cut the pieces that remain 2cm wide in half.

In 7 ridiculous cuts, you've got all your cubes.
More generally, where l is the length of each chocolate, w is the width, and h is the height (all in units of the final size), the minimum number of cuts is ceil(log2(l))+ceil(log2(w))+ceil(log2(h)).
ceil() is the ceiling function, aka rounding up to the nearest integer,
and log2() is the base-2 logarithm. It's base 2 because 1 cut divides a chunk into 2 pieces. If you had an adjustable multi-blade knife, you could change the base.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Good, but not the optimal solution. Please see that you can stack up the layers of chocolates and it will significantly reduce the no. of cuts. $\endgroup$
    – ABcDexter
    Jun 19, 2016 at 15:08
  • 2
    $\begingroup$ And, I now see there were other solutions posted. I still don't see what the girl has do to with this puzzle. $\endgroup$
    – WBT
    Jun 19, 2016 at 17:28
  • 2
    $\begingroup$ if the girl was to receive half of each chocolate fewer cuts would be needed. but that was not how the the problem was stated. $\endgroup$
    – Jasen
    Jun 19, 2016 at 21:23
  • 1
    $\begingroup$ 6 cuts (cut all S blocks in prallel), cut the 10 dimension to make 6+4 then 6+2+2 then 5+1+1+1+1+1, then 2 cuts in the 4 dimension and 1 in the 2 dimension. $\endgroup$
    – Jasen
    Jun 20, 2016 at 5:42
  • 1
    $\begingroup$ Though the problem is stated that "You open the wrappers of half the chocolates(as the half would be used to impress your 'first love')." So it seems that the girl gets half of the original chocolates, whole as 10x4x2 wrapped up, and the rest of the problem proceeds with S /2 (and the solution does not depend on S so that's not really relevant). +1 to @Jasen's first comment. $\endgroup$
    – WBT
    Jun 20, 2016 at 13: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.