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,659
    Thanks
    600
    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
    737
    Thanks
    1
    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
    737
    Thanks
    1
    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, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum