Hershey bar

[bonanova]

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.

[hhh3]

hmm... there are 42 views and no answer... then i guess i missed the whole complexity of the Q somwer... here's a soln thats more like a

(m-1)*(n-1)

[jordge]

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.

[Rob_Gandy]

(n-1)+(m-1) or n+m-2. It says you can't stack them, but it doesn't say that you can't hold the bar together as if it wasn't broken.

[joef1000]

mn-1

It is in my 'Professor Layton and the mysterious village' game.

[Emil]

Hi all, this is my first try...ever:

Is this a possible answer?:

(n-1) + (m-1)*n

[nakulendu]

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

[jordge]

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

[Prof. Templeton]

Stacking is not allowed, and the breaks are always made along a straight line.

Only stacking in a third dimension is not allowed? Cut pieces may be moved around on the plane or rotated to be cut further?

What about flipping of pieces? (although I fail to see how that may be advantageous at this point)

[curr3nt]

Are we allowed to warp the fabric of space and time?

[hhh3]

OMG.... warp what??!!

[curr3nt]

OMG.... warp what??!!

Sure. Chocolate bars possess strange and wonderful properties that we are still working to understand.

[bonanova]

Only stacking in a third dimension is not allowed? Cut pieces may be moved around on the plane or rotated to be cut further?

What about flipping of pieces? (although I fail to see how that may be advantageous at this point)

Rotating and flipping is OK.

[superprismatic]

I can prove that it can be done in ceiling(log₂n)+ceiling(log₂m)-1. My conjecture is that this is minimal.

[Prof. Templeton]

I can prove that it can be done in ceiling(log₂n)+ceiling(log₂m). 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.

[bonanova]

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.

[Prof. Templeton]

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.

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.

[curr3nt]

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?

[Prof. Templeton]

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.

[Izzy]

(m-1) + m(n-1), or mn - 1

*edit* Unless I'm misunderstanding the no stacking thing, since I'm considering breaking again over an already broken section "stacking".

Edited October 12, 2012 by Izzy

[bonanova]

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.

[Prof. Templeton]

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.