Skip to main content

Chapter 14 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{.}\))

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

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

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.

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.

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.

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?

  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.

  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.

    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.