Why do we need strong induction for the chocolate bar splitting puzzle?

Question

This answer uses strong induction to prove the solution to the chocolate bar splitting puzzle.

I'm trying to understand strong induction in general, and also specifically why it is needed in this case. What problem would we run into if we used simple induction? I.e. The base case is that for k=1 (k is the number of pieces we want), 0 cuts are needed, now show that for k+1 pieces, k cuts are needed.

Answer 1

Let $\mathcal P(n)$ be a statement whose expression depends on an integer $n\in\mathbb N$. You want to prove that it is true for all $n\in\mathbb N$. A proof by simple induction means that you show the following:

(i) $\mathcal P(0)$ is true

(ii) For all $n\in\mathbb N$, the fact that $\mathcal P(n)$ holds implies that $\mathcal P(n+1)$ holds too.

A proof by strong induction means that you show the following:

(i) $\mathcal P(0)$ is true

(ii)' For all $n\in\mathbb N$, the fact that $\mathcal P(m)$ holds for all $m<n$ implies that $\mathcal P(n+1)$ holds.

Fundamentally there is no difference between those two reasonings. It is mainly a matter of presentation. When you speak of a proof by strong induction, it is mainly to bring to the reader's attention that the induction step will not only consider one but potentially several step backwards. Personally I never liked the distinction between strong and simple induction, for me they are the same. And I am sceptical about the pedagogical interest of such a distinction, because it might make students think the strong one is a more powerful reasoning, whereas it is not...

Back to your chocolate bar splitting puzzle, it is required because if you have a rectangle composed of $n$ units squared, you will not be able to break it into two rectangles of respective sizes $n-1$ and $1$, unless the original rectangle is composed of a unique row of $n$ squares. Take for example a rectangle of $6$ squares, with $2$ rows and $3$ columns. You will have to break into two rectangles of respective sizes either $2\times2$ and $2\times1$, or twice $3\times1$.

Answer 2

Given any chocolate bar with $k$ pieces and dimensions $x*y$, an easy and efficient way to cut it is to first cut the bar into strips with width 1, then slice those strips into unit squares. This would require $(x-1)$ cuts at first, and then $x(y-1)$ cuts. Adding these together we get

$(x-1)+x(y-1) =$

$x-1+xy-x =$

$xy-1 =$

$k-1$

Thus showing that it takes $k-1$ cuts to completely slice the bar this way.

To prove that it is impossible to do it in less cuts, take a look at what happens when you make a cut. One piece becomes sliced, and then becomes two pieces. Therefore, every cut makes the total number of pieces increase by 1. So if you start with one piece, and want a total of $k$ pieces, you must use at least $k-1$ cuts.

Answer 3

You do understand the regular weak Induction, right? There you assume $P(k)$ is true and prove $P(k+1)$ is true. In strong Induction, you simply assume $P(m)$ is true for all $m\in \{1,2,3,\dots ,k\}$ and prove $P(k+1)$ is true. That's all there is more to Strong induction.

Now,

What problem would we run into if we used simple induction?

It can be proved that Strong Induction and Weak Induction are equivalent. So, there's no mathematical problem as such, only that as you can see, Strong Induction allows you to make (apparrntly) a much stronger assumption. And often, things become extremely difficult without having these "extra" assumptions.

One example is the properties of Fibonacci Numbers, which by definition, use the previous two terms to define the present term. So, if you want to prove some property of related to this, you have to at least assume $P(k-1)$ and $P(k-2)$ to get to $P(k)$.

Could I make myself clear? Feel free to ask anything you want to.