4

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

destroted
  • 41
  • 1
  • 1
  • 4
  • 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. – Hayden Mar 20 '14 at 05:17
  • 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.) – André Nicolas Mar 20 '14 at 05:41

3 Answers3

6

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$.

André Nicolas
  • 507,029
5

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.

user333060
  • 51
0

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.

Himanshu Pandey
  • 1