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¶
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 length-wise before you're done
maxw = ceiling(w)-1 #number of cuts width-wise before you're done
```
In [2]:
```
f = binomial(s+r-1,s) * (1-p)**(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+r-1,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+Y|Y <\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, maxw-1))
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 width-wise first we get, $$\begin{aligned} \text{E}[X+Y|X <\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, maxl-1))
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'}}$
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
## Leave a Reply. |
## About
Whenever I see an interesting 538 Riddler (specifically probability problems). I'll put my answers here ## Archives## Categories |