I\'m confused with a proof on this question, can someone help out a little bit?

Question

I'm confused with a proof on this question, can someone help out a little bit?

Use mathematical induction to prove the following statement: Think of a chocolate bar as a rectangle made up of n squares of chocolate. When breaking a chocolate bar into pieces, we may only break it along one of the vertical or horizontal lines, never by breaking one of the squares themselves, and we must break it all the way across on that same line. Show that under these rules, it always takes n - 1 breaks to break up a chocolate bar into then separate squares. (Example of possible breaks:)

Explanation / Answer

Consider a chocolate bar made of two squares. It could be either 1x2 or 2x1. The former can be broken to two squares by cutting horizontally whereas the latter can be cut into 2 squares by cutting vertically. Notice that there is no other possibility to do this.

Let P(n) be the statement that reads ' To break down a chocolate bar made of n squares we always require n-1 cuts'.

In the above we established that this is true for n=2. That is P(2) is true. This shall be the base case of our proof by induction.

Now suppose the statement P(n) is true for every n upto a natural number k. That is upto k, to breakdown a chocolate of n squares into individual squares we require n-1 steps.

Let our chocolate bar is made up of k+1 squares. To break this bar we need to make cuts. Say our first cut breaks it into two pieces each with p and q squares. Notices that whether the cut is horizontal or vertical, we will end up with two rectangles made up of squares. Say the size of one such rectangle is p-squares and that of the other is q-squares. We certainly have p+q=k+1. But both p < k+1 and q <k+1. Since p and q are less than or equal to k, inductive hypothesis applies to both of them.

So to break down p size chocolate we require p-1 cuts and to break down q-size chocolate bar we require q-1 cuts. Remember that we had performed a cut earlier to obtain p-sized and q-sized bars from k+1 sized bar. So in total we require p-1+q-1+1 = k+1-1-1+1 = k cuts.

Thus assuming the statements upto P(k) is true we have established that P(k+1) is true. Since we earlier showed that P(2) is true, by induction the statement is true for all natural numbers.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.