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.