Jump to content
BrainDen.com - Brain Teasers
  • 0

Hershey bar


bonanova
 Share

Question

You unwrap a giant Hershey bar. The type that is scored, so that it can be broken into smaller pieces. You note the bar has exactly m squares along its length and n squares along its width.

You wish to break the bar up into all small squares. How many breaks are required? Stacking is not allowed, and the breaks are always made along a straight line.

Link to comment
Share on other sites

21 answers to this question

Recommended Posts

  • 0

Every break increases the number of pieces by one by taking a larger piece and turning it into two smaller pieces. You start out with one large piece and continue breaking until all pieces are as small as allowed. If the total number of small pieces is n*m then the number of breaks to get that many is always (n*m)-1.

  • Upvote 1
Link to comment
Share on other sites

  • 0

mn-1. You can have it either a. Breaking the m rows first (m-1 breaks) and then breaking each of the m sticks into n pieces (total of m(n-1). In all mn-1 b. Breaking the n columns first (n-1 breaks) and then breaking each of the n sticks into m pieces (total of n(m-1). In all mn-1

There are actually more ways to break it up, not just do all m and then do all n. You could pick up any joined piece and break it in any order. But looking at your example for m first:

Break all the m rows: (m-1) breaks

Break all the m sticks into n pieces: m(n-1) breaks or (mn-m) breaks

Add all the breaks: (m-1) + (mn-m) = mn-1

Link to comment
Share on other sites

  • 0

I can prove that it can be done in ceiling(log2n)+ceiling(log2m). My conjecture is that this is minimal.

This is exactly my thought also.

to be related to the bit length. Perhaps an easier way to look at it would be to take the number of m (or n) and if it is odd then add 1 to it and if it is even divide it in half. Repeat until the result is one and count the number of division step required to get there. That would be the minimum for both m and n and they can be done separately and the steps added.

bn says we can rotate but that just transfers cuts required for m to n or vise versa.

Link to comment
Share on other sites

  • 0

If I understand their posts correctly, and I may not have,

sp's expression gives 5, and PT's algorithm gives 6, when, e.g., m=5 and n=7.

Neither seems possible without stacking, or, equivalently, holding two or more pieces together next to each other, so as to keep the configuration planar.

OP asks for the minimum straight-line breaks, simultaneous or not.

So as an aid to counting, it disallowed stacking.

Break a piece. Repeat. Count the steps.

Among the replies when applied to 5x7 are these results:

5, 6, 10, 24 and 34.

The correct answer [and expression(s)] are among the replies.

Link to comment
Share on other sites

  • 0

If I understand their posts correctly, and I may not have,

sp's expression gives 5, and PT's algorithm gives 6, when, e.g., m=5 and n=7.

Neither seems possible without stacking, or, equivalently, holding two or more pieces together next to each other, so as to keep the configuration planar.

These solutions took a loose interpretation of "stacking" where the cut pieces could not be laid on top of each other to create height. This was reinforced when you didn't address my question about only not stacking in a third dimension. Since we are dealing with an initial height of 1 the stipulation would have been a red herring. :rolleyes:

I didn't notice sp had a "-1" in there, but if we look at a simple case of 2 x 2, then sp's formula says that can be done in 1 cut. I don't see how that is possible even with stacking. Or an even simpler case of 1 x 1 would require -1 cuts instead of zero.

OP asks for the minimum straight-line breaks, simultaneous or not.

So as an aid to counting, it disallowed stacking.

Break a piece. Repeat. Count the steps.

Among the replies when applied to 5x7 are these results:

5, 6, 10, 24 and 34.

The correct answer [and expression(s)] are among the replies.

you might as well leave the pieces where they lie since rotating or flipping does not help in any way. I therefore will vote for (m-1) + (n-1) or 10 in the 5 x 7 case given.

Link to comment
Share on other sites

  • 0

Can I vote for warping space and time (mostly time) so that the chocolate bar is already separated so that 0 splits are now required?

On a serious note...

you might as well leave the pieces where they lie since rotating or flipping does not help in any way. I therefore will vote for (m-1) + (n-1) or 10 in the 5 x 7 case given.

Say you start with spliting the 5 using 4 splits. You now have 5 individual pieces that each require 6 splits. If you are allowed to split each piece together why not split the 5 one and move one of the pieces to line up the next split to split the two pieces into 4. One more split for the 5th piece for a total of 3 splits on the 5 side. Or is moving pieces not allowed?

Link to comment
Share on other sites

  • 0

Say you start with spliting the 5 using 4 splits. You now have 5 individual pieces that each require 6 splits. If you are allowed to split each piece together why not split the 5 one and move one of the pieces to line up the next split to split the two pieces into 4. One more split for the 5th piece for a total of 3 splits on the 5 side. Or is moving pieces not allowed?

Not Allowed because it would be equivalent to stacking. That was the basis of my first answer.

Link to comment
Share on other sites

  • 0

you might as well leave the pieces where they lie since rotating or flipping does not help in any way.

I therefore will vote for (m-1) + (n-1) or 10 in the 5 x 7 case given.

is undisputedly correct. But the second, (n-1) term is problematical. It must be executed for each of the m pieces produced by the first m-1 breaks. The alternative explanation is to note that you start with 1 and end with mn pieces. Each break increases the number of pieces by 1.

Link to comment
Share on other sites

  • 0

is undisputedly correct. But the second, (n-1) term is problematical. It must be executed for each of the m pieces produced by the first m-1 breaks. The alternative explanation is to note that you start with 1 and end with mn pieces. Each break increases the number of pieces by 1.

It would seem that, again, my definition of stacking was too loose. I was envisioning chopping pieces, even previously cut ones, where they lay without moving them.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...