Assume that a chocolate bar consists of n squares arranged in a rectangular pattern. The entire bar, a 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. Use strong induction to prove your answer.

Question

Asma Vang · Accepted Answer

Step 1   Given: A chocolate bar that consists of n squares arranged in a rectangle.   To proof: We make n−1 breaks to break a chocolate bar.   PROOF BY STRONG INDUCTION   Let P(n) be &quot;We make n−1 breaks to break a chocolate bar.&quot;   Basis step n=1   Let us consider a chocolate bar that consists of 1 square. The chocolate bar is then already completely broken into pieces and thus we require 0=1−1=n–1 breaks to completely break the chocolate bar.   Thus P(1) is true.   Inductive step We assume that P(1), P(2), .... , P(k) are all true, thus we make i breaks to break a chocolate bar consisting of i squares (i=1,2,…,k).   We then need to prove that P(k+1) is true. Let us consider a chocolate bar with k+1 squares.   Let m and q be positive integers such that k+1=mg and such that the squares of the chocolate bar form a rectangle with m rows and q columns.   Let the first break be breaking off the last column of the rectangle. Then we divide the chocolate bar in a (m–1)×q rectangle and in a 1×q rectangle.   Since P((m–1)q) is true, we require (m−1)g−1 breaks to break the (m−1)×q rectangle.  Since P(q) is true, we require q−1 breaks to break the 1×q rectangle.   We then note that we require (m–1)q−1+(q–1)+1 break to complete break the chocolate bar consisting of k+1 squares.   Step 2  (m–1)q–1+(q−1)+1=mq–q−1=mq–1=(k+1)–1  Thus we require (k+1)–1 breaks to break the chocolate bar with k+1 squares and thus P(k+1) is true.  Conclusion By the principle of strong induction, P(n) is true for all positive integers n.  Note: The inductive hypothesis in this proof contains more true statements than a proof using (not-strong) mathematical induction.   Answer  We make n−1 breaks to break a chocolate bar.

Assume that a chocolate bar consists of n squares arranged in a rectangular patt

Answered question

Answer & Explanation

New Questions in High school probability