2
$\begingroup$

I am trying to solve the following problem using proof by strong induction. the problem is:

Assume that a chocolate bar consists of n squares arranged in a rectangular pattern. The entire bar, or any smaller rectangular piece of the bar, can be broken along a vertical or a horizontal line separating the squares. Assuming that only one piece can be broken at a time, determine how many breaks you must successively make to break the bar into n separate squares

The farthest i have gotten is the basis step, but i dont even know if that is correct

Potential basis step that i got it is P(n), but besides that i am clueless

$\endgroup$
  • $\begingroup$ It doesn't seem to me like the problem is well-formed; you can't prove any induction formula because in general there are different approaches you could take. For the simplest example in which you can get different solutions, take $n=4$. We have two possible rectangular patterns; the first is a $2\times 2$ square, while the other is a $4\times 1$ rectangle. In the first case, we can use two breaks, while in the second we need three breaks. $\endgroup$ – Hayden Mar 20 '14 at 5:17
  • $\begingroup$ We need three breaks in each. Prove by induction that an $n$-square bar always requires $n-1$ breaks. (Actually, we find more. No matter how we break things, "clever" or not, we will do $n-1$ breaks.) $\endgroup$ – André Nicolas Mar 20 '14 at 5:41
4
$\begingroup$

We prove that a rectangular bar with $n$ squares always requires $n-1$ breaks.

Recall that a "break" divides a rectangle into two rectangles along score lines.

For the induction step, suppose that for all $m\lt n$, a bar with $m$ squares requires $m-1$ breaks. We show that a bar with $n$ squares requires $n-1$ breaks.

Break the $n$-bar into two rectangles, say of size $a$ and $b$, where $a+b=n$ and $a\lt n$, $b\lt n$.

The breaking used $1$ break. By the induction assumption, dissecting the $a$-rectangle into unit squares will use $a-1$ breaks, and the $b$-rectangle will use $b-1$ breaks, for a total of $1+(a-1)+(b-1)=n-1$.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

I know that this is not a proof by induction but it really is a nice solution to the problem. Suppose the bar consists of n pieces. We know that every cut always divides a large rectangle into two smaller pieces, thus creating exactly one new piece with every cut. Since we start with 1 big bar and we want n pieces, we have to break the bar exactly n-1 times.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

For n=1, we need 0 break. For n=2, we need 1 break. For n=3, we need 2 breaks. So say for n=j, its true and we need j-1 breaks and its true for all j>0&& j<=k. So a bar of k+1 squares can be broken down to 2 rectangles with squares < k , which is already true. Hence proved.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.