Results 1 to 6 of 6

Math Help - Induction

  1. #1
    Newbie Chief65's Avatar
    Joined
    Sep 2008
    From
    Denver
    Posts
    18

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,909
    Thanks
    773
    Hello, Chief65!

    You want to divide a bar of chocolate into 1\times1 squares.
    The starting bar is an m \times n rectangle.
    Show that it can be divided by cutting a minimum of 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 m horizontal strips with m-1 cuts. .**
    Code:
          *---*---* - - - *---*
          |   |   |       |   |
          *---*---* - - - *---*
     
          *---*---* - - - *---*
          |   |   |       |   |
          *---*---* - - - *---*
              .             .
              .             .
              .             .
          *---*---* - - - *---*
          |   |   |       |   |
          *---*---* - - - *---*

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


    There will be a minimum of: . (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.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    You start with a single mn 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 11). 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    Quote Originally Posted by Chief65 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 06:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 05:10 PM

Search Tags


/mathhelpforum @mathhelpforum