A piece of paper repeatedly cut into 8 or 12 pieces

Question

You are given a piece of paper. It will be cut into 8 or 12 pieces. Each of those new pieces can be cut again into 8 or 12 pieces or left uncut. This process is (theoretically) repeated as often as you want.

What is the highest number of pieces that cannot be reached?

Answer 1

Sure. The cuts add 7 or 11 pieces, respectively, so we are in a situation where McNuggets come in boxes of 7 and 11, and we always get one extra.

Choosing only 7-piece boxes, we can handle any number with remainder 1 modulo 7. Adding an 11-box switches that remainder, and as we add more 11-boxes, that remainder goes through all the 7 possibilities (0-6) before returning to 1, because 7 and 11 are relatively prime.

So, as long as the number is big enough to fit 6 lots of 11, we can make any number with any remainder when divided by 7, so the set of numbers that cannot be reached is (very) finite (and non-empty, can't get to 2 pieces for example), so a maximum is guaranteed to exist.

(Since after 5 lots of 11 there is only one remainder that's out of reach, the largest impossible number must have the same remainder (mod 7) as 6*11+1, and the largest such number smaller than that is 66+1-7=60.)

Answer 2

This is essentially the Frobenius coin problem: what is the largest amount that cannot be obtained using only coins of specified denominations?

In your case, at each step you can either add 7 pieces of paper, or 11 pieces, to the initial single piece that we are start with. So, the allowed denominations (in the language of the Frobenius coin problem) are 7 and 11.

It turns out that a largest unobtainable amount exists when the greatest common divisor of the set of allowed denominations is equal to $1$, that is, they have no common factor. Since $\gcd(7,11) = 1$, the answer to your problem is: yes, there is a maximum number of pieces that cannot be reached.

Furthermore, it turns out that there is an exact formula for the maximum amount that cannot be obtained in the case when there are only two allowed denominations, $x$ and $y$, which is $xy - x - y$. (No formula is known when there are more than two allowed denominations.)

So, when $x = 7$ and $y = 11$, we have $xy - x - y = 7 \cdot 11 - 7 - 11 = 59$. Since we start with a single piece of paper to which we add multiples of $x = 7$ and $y = 11$, the maximum number of pieces that we cannot obtain is $59+1=60$.