A puzzle

Randall Munroe (the writer of xkcd) posed an interesting problem on G+ a short while ago I thought I would share.  Quote:

You have a rectangular chocolate bar marked into m × n squares, and you wish to break up the bar into its constituent squares. At each step, you may pick up one piece and break it along any of its marked vertical or horizontal lines. Prove that every method finishes in the same number of steps.

From the author's comments:

This ridiculously easy puzzle has been known to stump some very high-powered mathematicians for as much as a full day, until the light finally dawns amid groans and beatings of heads against walls.


I thought to myself thought I, I am a dude who knows some math, I can figure this out!


Initially I assumed that a proof by induction would be the easiest way to solve the problem.  If we assume that a mxn chocolate bar always finishes in the same number of steps then can we prove that a mx(n+1) chocolate bar does the same?  


I won't be perfectly rigorous here, rather I will just outline the proof.


The mxn bar has a series of breaks that will separate it entirely.  This series of breaks, if performed on the mx(n+1) bar, will leave m pieces that are composed of precisely two squares each.  This means that we would need m additional breaks to completely break the new bar.  If there are some breaks along the line between the new squares and the old squares then for each such break we will separate q squares where q is between 1 and m of the new squares from the original bar.  In this case the q squares can be fully separated by q-1 breaks.  Any number of these breaks can occur but the total number of squares that can be separated in this way is equal to m.  Since each q squares require q breaks to separate regardless of the order of operations then the mx(n+1) bar always breaks in (the number of breaks required for mxn) + m.


Great, so I have a proof that isn't super rigorous but certainly works.  I believe it was Barrel Plug who always told me to try a proof by induction first; you can do an end run around all kinds of tricky problems with induction.  It's like cheating!


Then I began to think about it for real and hit my 'groan and smash head' moment.


So the chocolate bar has 1 piece.  Each time we break it we add 1 to the number of pieces.  We must get m*n pieces, so no matter how we break it we must perform exactly m*n-1 breaks.  Oy.  So this is in fact a truly simple proof that relies on no mathematical training at all but which can be solved in much more complex ways if you want to.


I like this problem.  Easy solution that everyone can understand but which most people will never think of because they approach it the wrong way.