The "pepperoni pizza problem"

Solution 1:

Updated: see below (Update 3)

Here's another approximation. Consider the center of the disks (pepperoni) as an homogeneous point process of density $\lambda = n/A$, where $A=\pi R^2$ is the pizza surface. Let $D$ be nearest neighbour distance from a given center. Then

$$P(D\le d) = 1- \exp(-\lambda \pi d^2)=1- \exp(-n \,d^2/R^2) \tag{1}$$

A pepperoni is free if $D > 2r$. Let $E$ be the expected number of free peperoni.

Then $$E= n\, P(D>2r) = n \exp (-n \,4 \, r^2/R^2) = n \exp(-n \, p)$$ where $p=(2r)^2/R^2$ (same notation as mzp's answer).

The maximum is attained for (ceil or floor of) $n^*=1/p=(R/2r)^2\tag{2}$

Update 1: Formula $(1)$ could be corrected for the border effects, the area near the border would be computed as the intersection of two circles. It looks quite cumbersome, though.

Update 2: In the above, I assumed that the center of the pepperoni could be placed anywhere inside the pizza circle. If that's not the case, if the pepperoni must be fully inside the pizza, then $R$ should be replaced by the "effective radius" $R' = R-r$

Update 3: The Poisson approach is really not necessary. Here's an exact solution

Let $$t = \frac{R}{2r}$$

(Equivalently, think of $t$ as the pizza radius, and assume a pepperoni of radius $1/2$). Assume $t>1$. Let $g(x)$ be the area of a unit circle, at a distance $x$ from the origin, intersected with the circle of radius $t$. Then

$$g(x)=\begin{cases}\pi & {\rm if}& 0\le x \le t-1\\ h(x) & {\rm if}& t-1<x \le t \\ 0 & {\rm elsewhere} \end{cases} \tag{3}$$ where $$h(x)=\cos^{-1}\left(\frac{x^2+1-t^2}{2x}\right)+t^2 \cos^{-1}\left(\frac{x^2+t^2-1}{2xt}\right) -\frac{1}{2}\sqrt{[(x+t)^2-1][1-(t-x)^2]} \tag{4}$$

Here's a graph of $g(x)/\pi$ for $t=5$

Let the random variable $e_i$ be $1$ if the $i$ pepperoni is free, $0$ otherwise. Then

$$E[e_i \mid x] = \left(1- \frac{g(x)}{\pi \, t^2}\right)^{n-1} \tag{5}$$ (remaining pepperoni fall in the free area). And

$$E[e_i] =E[E(e_i \mid x)]= \int_{0}^t \frac{2}{t^2} x \left(1- \frac{g(x)}{\pi \, t^2}\right)^{n-1} dx = \\ =\left(1- \frac{1}{t^2}\right)^{n-1} \left(1- \frac{1}{t}\right)^2 +\frac{2}{t^2} \int_{t-1}^t x \left(1- \frac{h(x)}{\pi\, t^2}\right)^{n-1} dx \tag{6}$$

The objective function (expected number of free pepperoni) is then given by:

$$J(n)=n E[e_i ] \tag{7} $$

This is exact... but (almost?) intractable. However, it can be evaluated numerically [**].

We can also take as approximation $$g(x)=\pi$$ for $0\le x < t$ (neglect border effects) and then it gets simple:

$$E[e_i ] =E[e_i \mid x]= \left(1- \frac{1}{t^2}\right)^{n-1}$$

$$J(n)= n \left(1- \frac{1}{t^2}\right)^{n-1} \tag{8}$$

To maximize, we can write $$\frac{J(n+1)}{J(n)}= \frac{n+1}{n} \left(1- \frac{1}{t^2}\right)=1 $$ which gives

$$ n^{*}= t^2-1 = \frac{R^2}{4 r^2}-1 \tag{9}$$ quite similar to $(2)$.

Notice that as $t \to \infty$, $J(n^{*})/n^{*} \to e^{-1}$, i.e. the proportion of free pepperoni (when using the optimal number) is around $36.7\%$. Also, the "total pepperoni area" is 1/4 of the pizza.

[**] Some Maxima code to evaluate (numerically) the exact solution $(7)$:

h(x,t) :=   acos((x^2+1-t^2)/(2*x))+t^2*acos((x^2-1+t^2)/(2*x*t))
  -sqrt(((x+t)^2-1)*(1-(t-x)^2))/2 $

j(n,t) := n * ( (1-1/t)^2*(1-1/t^2)^(n-1) 
  + (2/t^2) *  quad_qag(x * (1-h(x,t)/(%pi*t^2))^(n-1),x,t-1,t ,3)[1]) $

j0(n,t) := n *(1-1/t^2)^(n-1)$


tt : 1/(2*0.1581) $
j(11,tt);
4.521719308511862
j(12,tt);
4.522913706608645
j(13,tt);
4.494540361913981

tt : 1/(2*0.1) $
j(27,tt);
10.37509984083333
j(28,tt);
10.37692859747294
j(29,tt);
10.36601271146961

fpprintprec: 4$
nn : makelist(n, n, 2, round(tt^2*1.4))$
jnn : makelist(j(n,tt),n,nn) $ 
j0nn : makelist(j0(n,tt),n,nn) $

plot2d([[discrete,nn,jnn],[discrete,nn,j0nn]], 
    [legend,"exact","approx"],[style,[linespoints,1,2]],[xlabel,"n"],  [ylabel,"j(n)"],
[title,concat("t=",tt, "  r/R=",1/(2*tt))],[y,2,tt^2*0.5]);

The first result agrees with the OP simulation, the second is close: I got $n^{*}=28$ instead of $29$. For the third case, I get $n^{*}=2529$ ($j(n)=929.1865331$)

Solution 2:

Let $a \equiv \pi (2r)^2$, $A \equiv \pi R^2$, and $p \equiv \frac{a}{A}$. Denote by $P_i^n$ the probability of having $i$ free pepperoni when $n$ are distributed randomly (according to a uniform distribution) over the pizza. Let $E_n$ denote the expected number of free pepperoni given $n$.

I will assume that the pepperoni can be placed on the pizza as long as their center lies inside it.

• $n=1$:

  • $P_0^1 = 0$;
  • $P_1^1 = 1$;
  • $E_1= 0\cdot 0 +1\cdot 1 =1$.

• $n=2$:

  • $P_0^2 = p$, that is, the probability of both pepperoni having their centers within a distance of less then $2r$, in which case they overlap;
  • $P_1^2 = 0$;
  • $P_2^2 = 1- p$;
  • $E_2=p\cdot 0 +0\cdot 1+(1-p)\cdot 2 = 2(1-p) $.

• $n=3$:

  • $P_0^3 = p^2$;
  • $P_1^3 = C^3_2 p$, since there are $C^3_2$ combinations of how $2$ out of $3$ pepperoni could overlap;
  • $P_2^3 = 0$;
  • $P_3^3 = 1-p^2-C^3_2p$;
  • $E_3=p^2\cdot 0 +C^3_2 p\cdot 1+0\cdot 2 +(1-p^2-C^3_2p)\cdot 3 = 3(1-p^2)- 2C^3_2 p $.

• $n=4$:

  • $P_0^4 = p^3$;
  • $P_1^4 = C^4_3 p^2$;
  • $P_2^4 = C^4_2 p$;
  • $P_3^4 = 0$;
  • $P_4^4 = 1-p^3-C^4_3p^2-C^4_2p$;
  • $E_4=p^3\cdot 0 +C^4_3 p^2\cdot 1+C^4_2 p \cdot 2+0\cdot 3 +(1-p^3-C^4_3p^2-C^4_2p)\cdot 4 \\ \;\;\;\;= 4(1-p^3)- 3C^4_3 p^2- 2C^4_2 p $.

• By induction, for $n\ge 2$:

  • $E_n = n(1-p^{n-1})- \sum_{j=1}^{n-2} (n-j)C^n_{n-j}p^{n-1-j}$.

Hence the problem becomes that of solving

$$\max_{n \in\mathbb N} E_n$$

I was not able to solve this in general, but, for instance, if $p=0.1$ then

$$E_1 = 1, \; E_2 = 1.8, \; E_3 = 2.37, \; E_4 = 2.676, \; E_5 = 2.6795, \; E_6 = 2.3369, \; E_7 = 1.5991,\dots$$

So that the optimal number of pepperoni is $n^{*}=5$.

Solution 3:

Here is an approximation that uses only areas and no geometry. As long as the pepperonies are nice enough (circular, for instance) and the pizza is big and round enough that the edge doesn't matter, it is a good approximation.

Say there are $p$ pepperonies, they have area $a$. The pizza has area $1$. Then, right before you put down the last pepperoni, $(1-a)^{p-1}$ is the (expected) free area of pizza. The probability therefore that the last pepperoni is free is $\frac{(1-a)^{p-1}-a}{1-a}$.

Since all the pepperonies are equal, this probability is the same for all of them. Let $X_i$ be the random variable given by $1$ if pepperoni number $i$ is free, and $0$ if it is not. Then you want the $p$ that maximises $$ E(X_1+\cdots+X_p)=E(X_1)+\cdots +E(X_p)\\ =E(X_1)+\cdots +E(X_1)=pE(X_1)=p\frac{(1-a)^{p-1}-a}{1-a} $$ which can probably only be found numerically, but if you accept this approximation, then a little numerical analysis shouldn't be to bar.

Solution 4:

A First Approximation

Let $p$ be the probability that a pepperoni is not in conflict with one randomly placed pepperoni, and $P$ the probability that a pepperoni is free.

The exact expression for $p$ is the area suitable for another pepperoni over the total area where pepperoni can be placed :

$$ p = \frac{\pi (R-r)^2 - A}{\pi (R-r)^2} $$

Where $A$ is the area of the portion of a circle of radius $2r$ centered at the pepperoni center that is inside the area where pepperoni can be placed. I could not find an analytic formula for $A$ when the pepperoni is close to the border. Instead, I use the approximation that the pepperoni always covers the same area, regardless of where it is placed.

$$A \approx \pi (2r)^2$$

And we have :

$$ p = \frac{\pi (R-r)^2 - \pi (2r)^2}{\pi (R-r)^2} = \frac{(R-r)^2 - (2r)^2}{(R-r)^2} $$

This approximation is good when the radius of the pizza is large compared to the radius of a pepperoni.

Now, the probability that pepperoni $i$ is free when $n$ pepperoni are placed:

$$P = p^{n-1} $$

And the expected number of free pepperoni is :

$$E_n = n p^{n-1}$$

This function looks like this.

To obtain the maximum, we set the derivative equal to 0 :

$$p^{n-1} + np^{n-1} \ln(p) = 0 \implies n = \frac{-1}{ \ln(p)}$$

The maximum is either the ceiling or the floor of this value.

$$E_n = \max\left\{\left\lfloor \frac{-1}{ \ln(p)} \right\rfloor p^{\lfloor \frac{-1}{ \ln(p)} \rfloor - 1}, \left\lceil \frac{-1}{ \ln(p)} \right\rceil p^{\lceil \frac{-1}{ \ln(p)}\rceil - 1} \right\}$$

Now some numbers : If $R= 30$cm, $r=2$cm, we have $p\approx 0.98$. Then :

$$ E_{max} = \max\{48 \times 0.98^{48-1}, 49 \times 0.98^{49-1}\}\approx \max\{18.1678, 18.1669\} = \boxed{18.1678 }$$

Edit : A Better Approximation of A

I found a better way to approximate $A$, the average area in which another pepperoni cannot be placed. It is :

$$ A(r')= \left\{ \begin{array}{cc} \pi (2r)^2 & \mbox{ if } r' < R-3r \\ \frac{\pi (2r)^2}{2} & \mbox{ if } R-3r < r' < R-r \end{array} \right. $$

Where $r'$ is the distance between the center of the pizza and the center of the pepperoni. I think this formula desserves a bit of explaining. When the pepperoni is at distance less than $R-3r$ from the center of the pizza, all the points in a $2r$ radius are not suitable for a pepperoni. If the distance is larger than $R-3r$, some of the points in the circle of $2r$ radius are outside the zone where pepperoni can be placed (The circle of $R-r$ radius).When a pepperoni is inside that region, we consider that the area not suitable for another pepperoni is on average half the area of the circle. This correspond to making the approximation that the border of the pizza is flat. Again, for a large pizza, this approximation becomes more negligible.

Now, the average for $A$ becomes :

$$ \begin{align} A =& \frac{\int\limits_{0}^{2\pi} \int\limits_{0}^{R-r} A(r') r' dr' d\theta }{\int\limits_{0}^{2\pi} \int\limits_{0}^{R-r} r' dr' d\theta} \\ =& \frac{2\pi \left[\int\limits_{0}^{R-3r} \pi(2r)^2 r' dr' + \int\limits_{R-3r}^{R-r} \frac{\pi(2r)^2}{2} r' dr'\right]}{\pi (R-r)^2} \\ =& \frac{2\pi r^2}{(R-r)^2}\left[ (R-3r)^2 + (R-r)^2 \right] \end{align} $$

And the probability $p$ is :

$$ \begin{align} p =& \frac{\pi(R-r)^2 - \frac{2\pi r^2}{(R-r)^2}\left[ (R-3r)^2 + (R-r)^2 \right]}{\pi(R-r)^2} \\ =& 1-\frac{2r}{(R-r)^4}\left[ (R-3r)^2 + (R-r)^2 \right] \end{align} $$

And the rest of the equations stay unchanged.

Now, when $r/R = 0.1$, I get a total of 112 pepperoni placed, with an expected value of 31.74.

For $r/R = 0.01$, I get 2449 pepperoni placed, with an expected value of 901.58.