One morning, Phil was playing with his 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. The paper cutting problem: My solution¶We will approach this problem through two cases. First, we will find the expected number of cuts when she runs out of paper lengthwise, then width wise. Some notation we will use $$\begin{aligned} w &= \text{ The width of the paper } \\ \ell &= \text{ The length of the paper }\\ \lceil \cdot \rceil &:= \text{ The ceiling function that returns the next largest integer}\\ X &:= \text{ A random variable denoting the number of cuts made lengthwise}\\ Y &:= \text{ A random variable denoting the number of cuts made widthwise} \end{aligned}$$
In [1]:
from sympy import *
# define our symbols
w, l, p = symbols("w, \ell, p", positive=True)
k, k2 = symbols("k, k'", integer=True)
s, r = symbols("s, r", integers=True)
# some boundaries
maxl = ceiling(l)1 #number of cuts lengthwise before you're done
maxw = ceiling(w)1 #number of cuts widthwise before you're done
Note, the problem ends if she makes $\lceil w\rceil 1 = 8$ cuts widthwise or $\lceil \ell \rceil 1 = 10$ cuts lengthwise. We are interested in $$\text{E}[X+YY < \lceil w\rceil 1] +\text{E}[Y+XX < \lceil \ell \rceil 1]. $$ These can both be described using the negative binomial distribution. Before we continue, recall that the negative binomial probability mass function describes the probability of obtaining $s$ successes (obtained with probability $p$) before $r$ failures and can be written as
In [2]:
f = binomial(s+r1,s) * (1p)**(r) *p**s
f
Out[2]:
$\displaystyle p^{s} \left(1  p\right)^{r} {\binom{r + s  1}{s}}$
Note that here we have $p=1/2$ so $f$ becomes:
In [3]:
f = binomial(s+r1,s) * Rational("1/2")**(r+s)
f
Out[3]:
$\displaystyle 2^{ r  s} {\binom{r + s  1}{s}}$
First, we look for the expected number of total given given that she finishes the length side first. In negative binomial terms, the distribution is the probability cutting the width side between 0 to $\lceil w\rceil 2$ times ($k$ successes) before cutting the length side $\lceil \ell \rceil 1$ times ($r$ failures). $$\begin{aligned} \text{E}[X+YY <\lceil w\rceil 1] &= \sum_{k=0}^{\lceil w\rceil 2} f_{NB}(Y=k; r=\lceil \ell \rceil 1, p=1/2) (k+\lceil \ell \rceil 1) \end{aligned}$$
In [4]:
El = Sum(f.subs([(s,k), (r,maxl)])*(k+maxl), (k, 0, maxw1))
El
Out[4]:
$\displaystyle \sum_{k=0}^{\left\lceil{w}\right\rceil  2} 2^{ k  \left\lceil{\ell}\right\rceil + 1} \left(k + \left\lceil{\ell}\right\rceil  1\right) {\binom{k + \left\lceil{\ell}\right\rceil  2}{k}}$
Likewise, if she finishes widthwise first we get, $$\begin{aligned} \text{E}[X+YX <\lceil \ell\rceil 1] &= \sum_{k'=0}^{\lceil \ell\rceil 2} f_{NB}(X=k'; r=\lceil w \rceil 1, p=1/2) (k'+\lceil w \rceil 1) \end{aligned}$$
In [5]:
Ew = Sum(f.subs([(s,k2), (r,maxw)])*(k2+maxw), (k2, 0, maxl1))
Ew
Out[5]:
$\displaystyle \sum_{k'=0}^{\left\lceil{\ell}\right\rceil  2} 2^{ k'  \left\lceil{w}\right\rceil + 1} \left(k' + \left\lceil{w}\right\rceil  1\right) {\binom{k' + \left\lceil{w}\right\rceil  2}{k'}}$
Combining terms we get
In [6]:
E = El+Ew
E
Out[6]:
$\displaystyle \sum_{k=0}^{\left\lceil{w}\right\rceil  2} 2^{ k  \left\lceil{\ell}\right\rceil + 1} \left(k + \left\lceil{\ell}\right\rceil  1\right) {\binom{k + \left\lceil{\ell}\right\rceil  2}{k}} + \sum_{k'=0}^{\left\lceil{\ell}\right\rceil  2} 2^{ k'  \left\lceil{w}\right\rceil + 1} \left(k' + \left\lceil{w}\right\rceil  1\right) {\binom{k' + \left\lceil{w}\right\rceil  2}{k'}}$
Substituting $w=8.5$ and $\ell=11$ we get $$\begin{aligned} \text{E}[\text{# of words}]&= \end{aligned}$$
In [7]:
E.subs([(w,8.5), (l,11)])
Out[7]:
$\displaystyle \sum_{k=0}^{7} 2^{ k  10} \left(k + 10\right) {\binom{k + 9}{k}} + \sum_{k'=0}^{9} 2^{ k'  8} \left(k' + 8\right) {\binom{k' + 7}{k'}}$
In [8]:
E.subs([(w,8.5), (l,11)]).doit()
Out[8]:
$\displaystyle \frac{234137}{16384}$
In [9]:
E.subs([(w,8.5), (l,11)]).doit().evalf()
Out[9]:
$\displaystyle 14.2905883789063$
About 14.3 cuts on average. To get the general expressions for any rectangle and any square,we can set $w=n$ and $\ell=m$. $$\text{E}[\text{# of words}]=$$
In [10]:
n,m = symbols("n, m", positive=True)
E.subs([(w, "n"), (l,"m")])
Out[10]:
$\displaystyle \sum_{k=0}^{\left\lceil{n}\right\rceil  2} 2^{ k  \left\lceil{m}\right\rceil + 1} \left(k + \left\lceil{m}\right\rceil  1\right) {\binom{k + \left\lceil{m}\right\rceil  2}{k}} + \sum_{k'=0}^{\left\lceil{m}\right\rceil  2} 2^{ k'  \left\lceil{n}\right\rceil + 1} \left(k' + \left\lceil{n}\right\rceil  1\right) {\binom{k' + \left\lceil{n}\right\rceil  2}{k'}}$
and the square case of $w=\ell=n$ $$\text{E}[\text{# of words}] = $$
In [11]:
E.subs([(w, "n"), (l,"n")])
Out[11]:
$\displaystyle \sum_{k=0}^{\left\lceil{n}\right\rceil  2} 2^{ k  \left\lceil{n}\right\rceil + 1} \left(k + \left\lceil{n}\right\rceil  1\right) {\binom{k + \left\lceil{n}\right\rceil  2}{k}} + \sum_{k'=0}^{\left\lceil{n}\right\rceil  2} 2^{ k'  \left\lceil{n}\right\rceil + 1} \left(k' + \left\lceil{n}\right\rceil  1\right) {\binom{k' + \left\lceil{n}\right\rceil  2}{k'}}$
Note that the last output is just the same thing twice. You can just double the first line and get the answer you are looking for!
0 Comments

About
Whenever I see an interesting 538 Riddler (specifically probability problems). I'll put my answers here ArchivesCategories 