From Phil DeOrsey comes a matter that is anything but cut and dried:
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?
Extra credit: Instead of 8.5 by 11-inch paper, what if the paper measures m by n inches? (And for a special case of this, what if the paper is square?)
Let $EV(m,n)$ represent the average number of cuts for an $m$ by $n$ sheet of paper.
Any sheet of paper where $0 < m,n \le 1$ will always be a completed strip, thus:
There are three cases for $m,n$
If a sheet is $1$ by $n$ half of the time it will be interpreted as a completed strip, and half the time it will receive a cut and result in a remaining sheet of $1$ by $n-1$.
In other words:
$$EV(1,n) = \dfrac{1}{2}(0) + \dfrac{1}{2}\big(1 + EV(1,n-1)\big)$$
$$= \dfrac{1}{2} + \dfrac{1}{2}EV(1,n-1)$$
$$= \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{1}{4}EV(1,n-2)$$
$$= \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{1}{8} + \cdots + \dfrac{1}{2^{n-1}} + \dfrac{1}{2^{n-1}}EV(1,1)$$
$$= \dfrac{1}{2}\left(1 + \dfrac{1}{2} + \dfrac{1}{4} + \cdots + \dfrac{1}{2^{n-2}}\right) + 0$$
$$= \dfrac{1}{2}\left(\dfrac{1- \left(\dfrac{1}{2}\right)^{n-1}}{1 - \dfrac{1}{2}}\right)$$
$$ = 1- \left(\dfrac{1}{2}\right)^{n-1}$$
Similar to above, if a sheet is $m$ by $1$, half of the time it will be interpreted as a completed strip, and half the time it will receive a cut and result in a remaining sheet of $m-1$ by $1$.
Thus,
$$EV(m, 1) = 1- \left(\dfrac{1}{2}\right)^{m-1}$$
The sheet can receive a cut, and either dimension will be reduced half the time.
$$EV(m, n) = 1 + \dfrac{1}{2}EV(m-1, n) + \dfrac{1}{2}EV(m, n-1)$$
A 9 inch by 11 inch sheet is equivalent to an 8.5 inch by 11 inch. Using my recursive algorithm, I achieved
$$EV(9,11) = \dfrac{1982289}{131072} \approx 15.123 \text{ cuts}$$Using my recursive algorithm, I achieved a partial table. I found no patterns besides the border cases ($m=1$ or $n=1$).
| n | |||||||
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| m | 1 | $$0$$ | $$\dfrac{1}{2}$$ | $$\dfrac{3}{4}$$ | $$\dfrac{7}{8}$$ | $$\dfrac{15}{16}$$ | $$\dfrac{31}{32}$$ |
| 2 | $$\dfrac{1}{2}$$ | $$\dfrac{3}{2}$$ | $$\dfrac{17}{8}$$ | $$\dfrac{5}{2}$$ | $$\dfrac{87}{32}$$ | $$\dfrac{91}{32}$$ | |
| 3 | $$\dfrac{3}{4}$$ | $$\dfrac{17}{8}$$ | $$\dfrac{25}{8}$$ | $$\dfrac{61}{16}$$ | $$\dfrac{273}{64}$$ | $$\dfrac{583}{128}$$ | |
| 4 | $$\dfrac{7}{8}$$ | $$\dfrac{5}{2}$$ | $$\dfrac{61}{16}$$ | $$\dfrac{77}{16}$$ | $$\dfrac{709}{128}$$ | $$\dfrac{387}{64}$$ | |
| 5 | $$\dfrac{15}{16}$$ | $$\dfrac{87}{32}$$ | $$\dfrac{273}{64}$$ | $$\dfrac{709}{128}$$ | $$\dfrac{837}{128}$$ | $$\dfrac{1867}{256}$$ | |
| 6 | $$\dfrac{31}{32}$$ | $$\dfrac{91}{32}$$ | $$\dfrac{583}{128}$$ | $$\dfrac{387}{64}$$ | $$\dfrac{1867}{256}$$ | $$\dfrac{2123}{256}$$ | |
I looked at common denominators by diagonal as well.
| n | |||||||
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| m | 1 | $$0$$ | $$\dfrac{1}{2}$$ | $$\dfrac{3}{4}$$ | $$\dfrac{7}{8}$$ | $$\dfrac{15}{16}$$ | $$\dfrac{31}{32}$$ |
| 2 | $$\dfrac{1}{2}$$ | $$\dfrac{6}{4}$$ | $$\dfrac{17}{8}$$ | $$\dfrac{40}{16}$$ | $$\dfrac{87}{32}$$ | $$\dfrac{182}{64}$$ | |
| 3 | $$\dfrac{3}{4}$$ | $$\dfrac{17}{8}$$ | $$\dfrac{50}{16}$$ | $$\dfrac{122}{32}$$ | $$\dfrac{273}{64}$$ | $$\dfrac{583}{128}$$ | |
| 4 | $$\dfrac{7}{8}$$ | $$\dfrac{40}{16}$$ | $$\dfrac{122}{32}$$ | $$\dfrac{308}{64}$$ | $$\dfrac{709}{128}$$ | $$\dfrac{1548}{256}$$ | |
| 5 | $$\dfrac{15}{16}$$ | $$\dfrac{87}{32}$$ | $$\dfrac{273}{64}$$ | $$\dfrac{709}{128}$$ | $$\dfrac{1674}{256}$$ | $$\dfrac{3734}{512}$$ | |
| 6 | $$\dfrac{31}{32}$$ | $$\dfrac{182}{64}$$ | $$\dfrac{583}{128}$$ | $$\dfrac{1548}{256}$$ | $$\dfrac{3734}{512}$$ | $$\dfrac{8492}{1024}$$ | |
It was not clear, but Phil's daughter could consider a $1$ by $n$ or $m$ by $1$ sheet a strip, and thus the first two cases would result in $0$.
This would change the answer to
$$EV(9,11) = \dfrac{234137}{16384} \approx 14.29 \text{ cuts}$$