I own a book called Mathematical Puzzles: A Connoisseur’s Collection, by Peter Winkler. In it, there is the following problem:
Breaking a Chocolate Bar
You have a rectangular chocolate bar marked into m by 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.
In the back of the chapter, where he normally gives solutions, he instead says the following for this particular problem:
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. Risking accusations of sadism, I omit the solution.
Oh Winkler, you’re a sadist all right. A complete knee-biter. But fine, fine. Fine. I can solve the problem myself — I think.
I have come up with what I believe is a proof, enclosed in the spoiler box below. My questions to all of you are:
[ol]
[li]Is the proof valid?[/li][li]Assuming it’s valid, do you suppose this is what Winkler had in mind? From his “answer”, I’m guessing we’re meant to have some sort of epiphany and just see in our heads why it must be true, without really needing a written proof necessarily. But, if such a vision exists, I haven’t had it yet.[/li][li]In particular, is there a proof that doesn’t reveal (as mine does) how many steps will be needed, but merely proves only what the puzzle asks for?[/li][/ol]
Thanks for listening, and for any responses.
[spoiler](Proof goes by strong induction.)
Define function N(A) = A – 1. Let P(A) be the proposition that a rectangular bar of area A will be completely broken up into its constituent squares after exactly N(A) steps, no matter what choices are made about where to break the bar and its sub-bars at each step. (A “step” is defined as in the problem statement above.)
(1) Show P(1) is true. A bar of area 1 needs exactly 0 breaks to reduce it to individual squares — and indeed, N(1) = 0. Therefore P(1) is true.
(2) Show that if P(k) is true for all k < A, with A ≥ 2, then P(A) is also true. A rectangular bar of area A ≥ 2 clearly needs at least one break, so we break it along any available line. This counts as one step. There are now two rectangular sub-bars of areas A1 and A2, with A1 + A2 = A, and A1 and A2 both non-zero.
A1 and A2 are less than A, so both P(A1) and P(A2) are known to be true (within this induction step). Therefore, the total number of steps to break up the sub-bars is N(A1) + N(A2) = (A1–1) + (A2–1) = A1 + A2 – 2 = A – 2 = N(A) – 1. The total number of steps needed to break up the original bar of area A is 1 plus this quantity, or N(A). Therefore P(A) is true.
(3) Therefore, the number of steps that will break up a bar of area A into its constituent squares is exactly A – 1, for all A, and is independent of any method of breaking.
[/spoiler]
