Skip to main content

Chapter 12 Strong Induction

Exercises Practice Problems

1. Splitting a Chocolate Bar.

We have a \(r \times s\) chocolate bar that has \(n=rs\) squares of chocolate. Here is an example for \(r=4\) and \(s=9\text{:}\)

I can break a chocolate bar by splitting it along between any adjacent rows or any adjacent columns. For example, here are two possibilities:
Making one break at a time, I want to split the chocolate bar into its \(n=rs\) squares.

  1. Start with a \(3 \times 2\) chocolate bar. Convince yourself that regardless of the sequence of breaks that you choose, it will take you exactly 5 breaks to split the chocolate bar into its squares.

  2. Now use strong induction on \(n \geq 1\) to show that a rectangular chocolate bar with \(n\) squares requires \(n-1\) breaks to split it into \(n\) pieces, no matter what order of breaks you choose. Fill in the details of this proof.

    1. Base Case: \(n=1\text{.}\) The base case is a chocolate bar with \(n=1\) squares. (So it must be \(1 \times 1\text{.}\)) Solution.

      The chocolate bar is already "split" into squares. It takes \(0 = 1-1\) moves.

    2. Inductive Hypothesis: Assume the statement is true for \(1 \leq k < n\text{.}\) Explicitly write down this statement. Solution.

      Assume: \((\star)\) For \(1 \leq k < n\text{,}\) splitting a rectangular chocolate bar with \(k\) squares requires exactly \(k-1\) breaks.

    3. Inductive Step: Use \((\star)\) to prove true for \(n\text{.}\) Solution.

      Prove: Use \((\star)\) to prove that splitting a rectangular chocolate bar with \(n\) squares requires exactly \(n\) breaks.

      Break the chocolate bar along the \(k\)th column to get two chocolate bars: one \(k \times s\) and one \((r-k) \times s\text{.}\) By strong induction, it takes \(ks-1\) breaks to finish the left bar and it takes \((r-k)s -1\) breaks to finish the right one. The total number of breaks used is

      \begin{equation*} 1 + (ks-1) + ((r-k)s-1) = rs -1. \end{equation*}

2. Splitting Squares.

Given a square, you can cut the square into smaller squares by cutting along lines parallel to the sides of the original square (these lines do not need to travel the entire side length of the original square). For example, by cutting along the lines below, you will divide a square into 6 smaller squares:

Using strong induction to prove that you can cut a square into \(n\) smaller squares for any \(n \geq 6\text{.}\) Hint: You will need three base cases. This is a very good hint actually, as it suggests that to prove \(P(n)\) is true, you would want to use the fact that \(P(n-3)\) is true. So somehow you need to increase the number of squares by 3. Solution.

  • Base Cases: \(n=6,7,8\)

  • Inductive Hypothesis. For \(6 \leq k < n\text{,}\) a square can be split into \(k\) smaller squares.

  • Inductive Step: We want to split the square into \(n\) smaller squares. First, we split it into \(n-3\) smaller squares (which works by the inductive hypothesis). Next, pick any square and split it into 4 smaller squares by drawing the horizontal and vertical bisectors.

3. The Angles of a Polygon.

So a 3-gon is a triangle, a 4-gon is a square, a 5-gon is a pentagon, and so on.

Use strong induction to prove that the sum of the angles in an \(n\)-gon is equal to \(180 (n-2)\text{.}\) Here is how to start your inductive step:

  • Label the vertices as \(1,2, \ldots, n\text{.}\)

  • Pick some vertex \(k\) where \(3 \leq k \leq n-1\text{.}\)

  • Draw the diagonal connecting vertex 1 to vertex \(k\text{.}\)

  • Break the polygon apart along this diagonal to create two smaller polygons, and now use strong induction.

Solution.

  • Base Case: A \(3-gon\) is a triangle, whose angles sum to \(180 = (3-2) \cdot 180\) degrees.

  • Inductive Hypothesis: Assume that for \(3 \leq k < n\text{,}\) the sum of the angles in a \(k\)-gon is equal to \(180 (k-2).\)

  • Inductive Step: Prove that the sum of the angles in an \(n\)-gon is equal to \(180 (n-2).\) Label the vertices as \(1,2, \ldots, n\text{.}\) Pick the diagonal connecting vertex 1 to vertex \(k\) where \(3 \leq k \leq n-1\text{.}\) Break the polygon apart along this diagonal. This creates a \(k\)-gon \(P_1\) and an \((n-k+2)\)-gon \(P_2\text{,}\) where \(k \geq 3\text{.}\) (Note that we have added one more edge which is used twice: once in each polygon. So vertices 1 and \(k\) appear in both \(P_1\) and \(P_2\text{.}\)) By induction, the sum of the angles in these polygons is

    \begin{equation*} 180 (k-2) + 180 (n-k+2 - 2) = 180 (n-2). \end{equation*}

    When we add these angles, we get the sum of the angles in the original polygon.

4. Factoring a Number.

Use strong induction to prove that any integer \(n \geq 1\) can be written as \(n=2^r m\) where \(m\) is an odd integer (possibly \(m=1\)) and \(r \geq 0\text{.}\) Your inductive step will have two cases, depending on whether \(n\) is odd or even. Solution.

  • Base Case: \(n=1\text{.}\) We have \(1 = 2^0 \cdot 1\text{.}\)

  • Inductive Hypothesis: Assume that for \(1 \leq k < n\text{,}\) the positive integer \(k \geq 1\) can be written as \(k=2^s \ell\) where \(\ell\) is an odd integer (possibly \(\ell=1\)) and \(s \geq 0\text{.}\)

  • Inductive Step: Prove that \(n \geq 1\) can be written as \(n=2^r m\) where \(m\) is an odd integer (possibly \(m=1\)) and \(r \geq 0\text{.}\)

    There are two cases. If \(n\) is odd then \(n=2^0 \cdot n\text{,}\) and we are done (taking \(r=0\) and \(m=n\)). If \(n\) is even then \(n=2k\text{.}\) By induction, \(k=2^s \ell\) where \(\ell\) is an odd integer (possibly \(\ell=1\)) and \(s \geq 0\text{.}\) Therefore \(n=2^{s+1} \ell\text{.}\) Taking \(r=s+1\) and \(m=\ell\text{,}\) we are done.

5. Coin Removal Problem.

Let's play a coin flipping game. Start with \(n\) coins arranged in a row. Some show heads and some show tails. On each move, you must:

  • Pick a heads-up coin and remove it.

  • Then flip the coins still present in the (at most) two neighbor spots surrounding it.

This diagram shows all three valid moves from this starting postion:

Note that removing a coin leaves an empty space. So that coin is now missing, so the coins you flipped are now missing a neighbor.

The Question: For which arrangements of heads and tails can we remove all coins?

  1. Play the coin removal game with \(n\) coins for \(n=1,2,3\text{.}\) For each \(n\text{,}\) list the starting configurations that are winning and losing. Can you see the pattern? Solution.

    \begin{equation*} \begin{array}{c||c|c} & \mbox{winning} & \mbox{losing} \\ \hline 1 & H & T \\ 2 & HT TH & HH TT \\ 3 & HTT THT TTH HHH & HHT HTH THH TTT \\ \end{array} \end{equation*}

  2. Now play some games on \(n=4,5,6\) coins. Make a conjecture about which starting positions are winning and which ones are losing. Solution.

    • A starting position with an even number of heads is \underline{losing}.

    • A starting position with an odd number of heads is \underline{winning}.

  3. We now prove this by induction.

    Base Case: Your answers from part (a) are your base case for \(n=1,2,3\) (of course, you only need the base case \(n=1\) for a full proof).

    Inductive Hypothesis: When \(k < n\text{,}\) the winning positions and losing positions are as described in part (b).

    Inductive Step: Consider a starting position with \(n>1\) coins.

    1. Case 1: You start with an odd number of heads. Remove the leftmost heads up coin and flip its neighbors. This leaves two smaller lists of coins, \(L\) and \(R\text{,}\) which are to the left and right of the coin you removed. One of these sets could be empty; why? What can you say about the configuration of coins in each of \(L\) and \(R\text{?}\) Explain why this proves that the original configuration was winning/losing. Solution.

      • We start with an odd number of \(H\) in our game.

      • Find the leftmost \(H\text{.}\) There are zero heads to the left of this coin, and an even number to the right of it.

      • When you remove this coin, it creates two disjoint games (unless \(H\) is the first or last coin, in which case there is only one game after your move). The left game has a single \(H\) (because the rightmost coin changed from \(T\) to \(H\text{.}\) The right game has an odd number of \(H\) since the leftmost coin changed state.

      • Both of these games are smaller than the original game. By the induction hypothesis, both of these games are winning configurations. Therefore the original game has a winning strategy.

    2. Case 2: You start with an even number of heads. Pick any heads-up coin, remove it and flip its neighbors. Once again, this leaves two smaller lists of coins, \(L\) and \(R\text{.}\) Explain why one of these sets must contain an even number of heads-up coins. Explain why this proves that the original configuration was winning/losing. Solution.

      • We start with an even number of \(H\) in our game.

      • Pick any \(H\text{.}\) Since the total number of \(H\)'s is even, there must be an odd number \(H's\) either to the left or to the right of this coin.

      • When you remove this coin, it creates two disjoint games (unless \(H\) is the first or last coin, in which case there is only one game after your move). One of these two games now has an even number of heads.

      • The game with an even number of heads is smaller than \(n\text{.}\) By induction, this configuration is losing.

      • So no matter what coin we remove, we are sure to lose.