This is the
solution to
problem 6 on the
hard interview questions node. If you have not read the
question, the
following will make no
sense to you:
There is a simple, one line solution: since every break creates exactly one new piece, n*m-1 breaks are both necessary and sufficient to create n*m total pieces.
There's also a very long and annoying inductive solution, which I won't bother reproducing here.