1. ## Induction

We just started the section on induction in Discrete Math. This was the first assigned question: You want to divide a piece of chocolate into 1"x1" square pieces to distribute to a group of children. The starting piece is an m"x n" rectangle. Show that it can be divided by breaking pieces of chocolate a total of mn-1 times, but not with fewer breaks. (Each "break" divides only one piece, and must be a straight line parallel to one of the sides of the piece.) I have no idea how to start. Any help would be appreciated, thanks.

2. Hello, Chief65!

You want to divide a bar of chocolate into $\displaystyle 1\times1$ squares.
The starting bar is an $\displaystyle m \times n$ rectangle.
Show that it can be divided by cutting a minimum of $\displaystyle mn-1$ times.

Each cut is a straight line parallel to one of the sides of the piece.
Code:
      *---*---* - - - *---*
|   |   |       |   |
*---*---* - - - *---*
|   |   |       |   |
*---*---* - - - *---*
:   :   :       :   :
:   :   :       :   :   m rows
:   :   :       :   :
*---*---* - - - *---*
|   |   |       |   |
*---*---* - - - *---*
n columns

Suppose we cut the bar into $\displaystyle m$ horizontal strips with $\displaystyle m-1$ cuts. .**
Code:
      *---*---* - - - *---*
|   |   |       |   |
*---*---* - - - *---*

*---*---* - - - *---*
|   |   |       |   |
*---*---* - - - *---*
.             .
.             .
.             .
*---*---* - - - *---*
|   |   |       |   |
*---*---* - - - *---*

Then each of the $\displaystyle m$ strips requires $\displaystyle n-1$ cuts to make unit squares.
. . This requires: .$\displaystyle m(n-1)$ cuts.

There will be a minimum of: .$\displaystyle (m - 1) + m(n-1) \;=\;\boxed{{\color{red}mn-1}\text{ cuts}}$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

**

If the initial cuts are made vertically, the numbers of cuts is the same.

3. You start with a single m×n block. After you make the first break, you'll have two (smaller) blocks. Each time you make a break, the number of blocks increases by 1. After k breaks you will have k+1 blocks (prove that by induction!). You want to finish with mn blocks (of size 1×1). So that will require mn-1 breaks.

The advantage of this argument is that it makes no difference in what order you make the breaks, horizontally or vertically. It will always take exactly mn-1 breaks, no more and no less.

4. Originally Posted by Chief65
We just started the section on induction in Discrete Math. This was the first assigned question: You want to divide a piece of chocolate into 1"x1" square pieces to distribute to a group of children. The starting piece is an m"x n" rectangle. Show that it can be divided by breaking pieces of chocolate a total of mn-1 times, but not with fewer breaks. (Each "break" divides only one piece, and must be a straight line parallel to one of the sides of the piece.) I have no idea how to start. Any help would be appreciated, thanks.
1. Chocolate is bad for children, especially a piece as big as that.

2. You can do it in a lot fewer breaks than that by stacking up the pieces you broke longways and snapping several at once.

5. A nice question I was once asked is this:

What is the minimum number of cuts needed to cut a 3x3x3 cake into 27 1x1x1 cakes. Each cut being straight, that is no corners.

RonL

6. 6.

You can of course do it with 6 cuts, and the fact that you always need as many as 6 cuts to separate the middle cube from all the rest gives you the proof that this is in fact the minimum.