The reason beind mn - 1 can be understood like this. Forget about any grid for a moment, just imagine a simple piece of paper. Any cut on the paper will give rise to a new piece. If you make 1 cut to a single piece, it will give rise to 1 extra piece. If you further make a cut on any of those pieces, your count increases by one. In total, we need mn pieces, given each is 1x1. We don't have to make mn cuts, because there is already one piece at the beginning. So, we make mn - 1 cuts.

Make sure you have enough memory to store the numbers ;)

Each time a piece of paper is cut it becomes 2 pieces, adding 1 to the total number of pieces. Therefore to make x pieces from 1 piece there needs to be x-1 cuts, so the final answer is (n*m)-1.

Interestingly, this principle means that the cuts can be made in any order and configuration.

For this problem to be ranked easy, it would be nice to see an example that wasn't one-dimensional solved all the way thru, to ensure we understand the rules for cutting. That is, sure, you can't fold or place them on top of eachother, but it is unclear whether you can hold multiple pieces of paper side by side as you cut. It seemed perfectly logical that one could, so I think an example where m, n both >1 would have cleared that question about the rules right up.

The answer is always one less than the number of 1x1 squares. Proof by induction: a single square takes zero cuts. If you have a rectangle of n squares that takes n-1 cuts, if you add a row or column of m squares, you are increasing the number of cuts by m as well, so the property is invariant.