The "pepperoni pizza problem"

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$ enter image description here

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$)

enter image description here

enter image description here

enter image description here


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$.


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.

Tags:

Optimization

Probability

Geometric Probability

Circles

Related

Find $\lim_{x\to0}\frac{\sin\left(1-\frac{\sin(x)}{x}\right)}{x^2}$. Is my approach correct? Evaluate $\space\lim\limits_{n\to\infty}\sqrt{n}\int\limits_{-\infty}^{+\infty}\frac{\cos t}{\left(1+t^2\right)^n}dt$ Sum of the supremum and supremum of a sum What is the remainder of $\frac{2^{2015}}{36}$? Limits using L'Hopital's rule $\lim_{x\to0^+} (x^{x^x-1})$ Normal bundle to complete intersection in $\mathbb{P}^n$ How can I prove that $2^{\sqrt 7}$ is bigger than $5$? If $A$ and $B$ are normal such that $AB=0$, does it follows that $BA=0$? Different Applications of Sylow Theorems Continuous function that is uniformly continuous on a dense subset Easy way of memorizing or quickly deriving summation formulas Prove that matrix equation $AX-XA=I$ doesn't have a solution for any $A\in M_n(\mathbb{R})$

Recent Posts