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.

Here is one way to show that (nm - 1) breaks are sufficient. (It does not, however, demonstrate that (nm - 1) breaks are necessary.)

The block of chocolate has (n-1) and (m-1) 'score lines' on each side, along which it can be broken. By making (n-1) breaks we can produce n long and thin pieces, of size 1 x m. We then need to make (m-1) breaks on each of these long and thin pieces to get them down to 1 x 1 size. ie, n(m-1) more breaks.

This gives us a total of (n-1) + n(m-1) breaks.

(n-1) + n(m-1)
= n - 1 + nm - n
= -1 + nm
= nm - 1
QED

Log in or register to write something here or to contact authors.