Trees Problem 4

Solution

Let's define n=pq to be the area of the chocolate bar. The claim we need to prove is that n-1 breaks are required to divide the bar into individual squares.

Proof by induction on n.

Base case: At n=1, the bar already consists of a single square. So we don't need to break it up further. That is, we need 0, i.e. n-1 breaks to divide it up. So the claim is true.

Inductive hypothesis: any chocolate bar of area n can be divided into individual squares using n-1 breaks, for n from 1 up through k-1.

Rest of inductive step: suppose that B is a chocolate bar of area k, where k is larger than 1. Let's break B along any grid line, creating two bars X and Y.

Let x and y be the areas of X and Y. Since we are mathematicians and broke the chocolate bar perfectly without leaving any flakes, we haven't lost any area. So x+y=k.

By the inductive hypothesis, we can reduce X to individual squares using x-1 breaks. Similarly, we can reduce Y to individual squares using y-1 breaks.

Therefore, to reduce B to individual squares, we use our initial break, then break up X and Y using x-1 and y-1 breaks. So the total number of breaks required to divide up B is $$1 + (x-1) + (y-1) = x + y -1 = k-1$$. So breaking up B requires k-1 breaks, which is what we needed to prove.

Self-check

Notice that the inductive step chooses some arbitrary line for making the initial break. If you make some specific choice (e.g. pick the top horizontal line first), then you'll only prove that that specific strategy requires n-1 breaks. Perhaps some other strategy would have required more breaks or fewer breaks?

The claim was about chocolate bars, so make sure that your proof is talking about chocolate bars. Your proof may also involve various equations, but they need to be related to the main topic of chocolate bars.