[Math] Minimum number of cuts to separate all pieces of an $m\times n$ chocolate bar when stacking is allowed

Question

Inspired by this question, where stacking the cut off pieces wasn't allowed.

We want a function $F(m,n)=k$ for $\{m,n,k\}\in\mathbb{N}$ that gives the number of cuts or foldings $k$ required to transform the $m\times n$ chocolate bar into $mn$ square, separate pieces.

For instance, for $2\times 2$, you could fold the bar over its middle two times to get a tower $4$ (separated) pieces high. So $F(2,2)=2$. In general, $F(2^n,2^n)=2n$.

However, for more asymmetrical cases, I'm unable to make much progress. I guess one would need to construct an optimal algorithm and take the calculations from there, so any help in constructing that would also be much appreciated!

Answer 1

A simple optimal algorithm would be

Imagine extending the initial chocolate bar to the right and top as necessary to make each dimension a power of $2$ and then use the obvious cut-in-halves algorithm on the extended bar. In each of the cuts you're guaranteed that there will be some real chocolate to cut through, namely the part that contains the original bottom-left corner.

This gives $F(n,m) = \lceil\log_2 n\rceil + \lceil \log_2 m\rceil$.

We can see that it is impossible to get by with fewer steps by long induction on $n+m$. No matter how you make the initial cut, the larger of the pieces that are left will have a $\lceil\log_2 n\rceil + \lceil \log_2 m\rceil$ that has decreased by at most $1$ -- and so by induction, getting that piece down to individual squares is going to take at least $\lceil\log_2 n\rceil + \lceil \log_2 m\rceil - 1$ additional cuts, no matter which way you choose to stack parts of the smaller piece into those additional cuts.

We see that having freedom to turn pieces by $90^\circ$ before stacking will never save cuts, nor will having the ability to un-stack pieces after cutting.