Strips by a million cuts

One morning, Phil was playing with my daughter, who loves to cut paper with her safety scissors. She especially likes cutting paper into “strips,” which are rectangular pieces of paper whose shorter sides are at most $1$-inch long.

Whenever Phil gives her a piece of standard printer paper ($8.5$ inches by $11$ inches), she picks one of the four sides at random and then cuts a $1$-inch wide strip parallel to that side. Next, she discards the strip and repeats the process, picking another side at random and cutting the strip. Eventually, she is left with nothing but strips.

On average, how many cuts will she make before she is left only with strips?

Let's define $S(m,n)$ as the expected number of strips for an $m$ by $n$ sheet of paper. By definition, we have $S(m,n) = 0$ for all $m , n \gt 0$ such that $\min \{ m, n \} \leq 1.$ Since there is a $0.5$ probability that the length side is reduced and $0.5$ probability that the width side is reduced by the next cut, we have the following recursion formula: $$S(m,n) = \frac{1}{2} S(m-1, n) + \frac{1}{2} S(m, n-1) + 1.$$

After using the fact that $S(m,n) = S(n,m)$ for all $m,n \gt 0$ and seeding the cache with $S(1,k) = 0$ for $k = 1, \dots, 11$, a recursive function needs $52$ calls to arrive at $$S(8.5,11) = 14.29058837890625.$$

We can muck about with the recursive definition to note a few things about this function $S(m,n).$ Firstly, we get $$S(m,n) = 2 - \frac{1}{2^{\lceil n \rceil -2}}, \,\, \forall m \in (1,2], n > 0.$$ Let's focus on $n \in \mathbb{N}$ as the extension to all $n > 0$ is trivial. The base case holds by the boundary condition since $S(m,1) = 2 - \frac{1}{2^{-1}} = 0.$ If the equation holds for some $n \in \mathbb{N}$ then since $m \in (1,2],$ $S(m-1,\cdot) \equiv 0,$ so \begin{align*} S(m,n+1) &= \frac{1}{2} S(m-1, n+1) + \frac{1}{2} S(m, n) + 1 \\ &= \frac{1}{2} \left( 2 - \frac{1}{2^{n-2}} \right) + 1 \\ &= 2 - \frac{1}{2^{n-1}}. \end{align*}

We can similarly use the recursion formula and induction to build up $$S(m,n) = 4 - \frac{\lceil n\rceil +3}{2^{\lceil n\rceil-1}}, \,\, \forall m \in (2,3], n > 0$$ and $$S(m,n) = 6 - \frac{\lceil n \rceil^2 + 7\lceil n \rceil + 16}{2^{\lceil n \rceil+1}}, \,\, \forall m \in (3,4], n > 0,$$ and so on. We can then also get the general asymptotic behavior again by induction, that $$S(m,n) = 2(\lceil m \rceil -1) - \frac{O\left(\lceil n\rceil^{\lceil m \rceil -2}\right)}{2^{\lceil n \rceil}}$$