Person tears her test (1 sheet). She takes a piece & tears it into 4 or 6 smaller pieces. Prove she can tear the test into any no. of pieces $>$8

Question

Question

Person is tearing her test (1 sheet of paper) into small pieces. She picks up a piece of paper and tears it into 4 or 6 smaller pieces. Prove that she can tear the test into any number of pieces greater than 8.

What I did:

let n∈N. Consider a paper with n rips

There are two special cases. Use strong induction

1. If paper has n=4 rips, then 5 cuts are needed.
2. If paper has n = 6 rips, 3 cuts are needed After further experimentation, a pattern emerges: each time she tears a piece, the ttl no. of pieces increases by 3 or 5. Thus: we get a statement

---

From here, I can't find a statement to prove using strong induction. I don't know how to apply the pattern to get a statement. Hints would be appreciated greatly!

Answer 1

You've arrived at the conclusion that the total number of pieces increases by 3 or 5, so your next step is to prove that every number $n \geq 8$ can be represented as the sums of $3$s and $5$s.

Base Case: $n = 8$, which is trivial.

Inductive hypothesis: Suppose this statement is true for some $n > 8$.

Inductive step: We will show that this holds for $n + 1$. There are $2$ possible cases for $n$, where $n$ has a $5$ in its summation and one where it doesn't. For the first case, where $n$ has a $5$ in its summation we can prove the hypothesis for $n + 1$ by replacing the $5$ with two $3$s, and our statements holds true. For the case where there's no $5$ in $n$'s summation, we know that $n > 8$, so the summation must contain at least three $3$s. We can replace these with two $5$s, proving the second case for $n + 1$.

The proof that every number greater than $8$ contains either at least one $5$ or three $3$s is relatively trivial. If both of these conditions are false, this means the number can contain at most zero $5$s or two $3$s, meaning the largest number it could be is $6$.

Answer 2

Your observation that each time the number of pieces increases by 3 or 5 can be instrumental in the proof. There are three different cases, each of which are easy to prove by induction.

Case 1: $n\equiv0\pmod{3}$

For the base case, $6$ works, and for any $k$ is $k$ is possible then so is $k+3$ as one can simply tear a piece of paper into $4$ parts for that.

Case 2: $n\equiv1\pmod{3}$

Note that $4$ is possible, so by an argument similar to case 1, one can show that all such numbers are possible.

Case 3: $n\equiv2\pmod{3}$

$11$ is possible by tearing one sheet into 6 parts twice. The logic from previous cases can be extended here as well.