El "problema de pizza de pepperoni"

Question

Este problema surgió en un contexto diferente, en el trabajo, pero me lo han traducido a la pizza.

Suponga que tiene una pizza circular de radio $R$. Sobre este disco, $n$ pepperoni serán distribuidos completamente al azar. Todos pepperoni tienen el mismo radio $r$.

Una de pepperoni es "libre" si no se sobrepone a cualquier otro de pepperoni.

Usted es libre de elegir $n$.

Supongamos que usted elija un pequeño $n$. La posibilidad de que cualquier pepperoni es gratis son muy grandes. Pero $n$ es pequeño, por lo que el número total de pepperoni es pequeño. Supongamos que usted elija de una gran $n$. La posibilidad de que cualquier pepperoni es gratis son pequeños. Pero hay un montón de ellos.

Claramente, para un determinado $R$ y $r$, hay algunos óptima $$ n que maximiza el número esperado de libre pepperoni. Cómo encontrar esta óptima?

Edit: al recoger la respuesta

Así que parece que leonbloy la respuesta que da la mejor aproximación en los casos que yo he mirado:

 r/R          n* by simulation     n_free (sim)     (R/2r)^2
 0.1581       12                   4.5              10
 0.1          29                   10.4             25
 0.01         2550                 929.7            2500

(Sólo hay un par de cientos de ensayos en el r=0.01 sim, por lo que 2550 podría no ser super preciso.) Así que me voy a recoger por la respuesta. Me gustaría agradecer a todos por sus aportes, esta ha sido una gran experiencia de aprendizaje.

Aquí están algunas fotos de una simulación para r/R = 0.1581, n=12:

Editar después de tres respuestas publicadas:

Escribí un poco de simulación. Voy a pegar el código de abajo, de modo que se puede comprobar (edito: se ha solucionado correctamente los puntos de recogida al azar en una unidad de disco). He mirado en dos de tres casos hasta el momento. Primer caso, r = 0.1581, R = 1, es decir p = 0,1 por mzp la notación. En estos parámetros conseguí n* = 12 (libre de pepperoni = 4.52). Arthur expresión no parece ser maximizada aquí. leonbloy la respuesta que daría 10. También hice r = 0.1, R = 1. Tengo n* = 29 (libre de pepperoni = 10.38) en este caso. Arthur expresión no fue maximizada aquí y leonbloy la respuesta que daría a 25. Finalmente, para r = 0.01 puedo obtener aproximadamente n*=2400, como se muestra aquí:

Aquí está mi (feo) de código, ahora editado correctamente de selección aleatoria de puntos en un disco:

from __future__ import division
import numpy as np
# the radius of the pizza is fixed at 1
r = 0.1   # the radius of the pepperoni
n_to_try = [1,5,10,20,25,27,28,29,30,31,32,33,35]  # the number of pepperoni
trials = 10000# the number of trials (each trial randomly places n pepperoni)

def one_trial():
    # place the pepperoni
    pepperoni_coords = []
    for i in range(n):
        theta = np.random.rand()*np.pi*2 # a number between 0 and 2*pi
        a = np.random.rand()           # a number between 0 and 1
        coord_x = np.sqrt(a) * np.cos(theta) # see http://mathworld.wolfram.com/DiskPointPicking.html
        coord_y = np.sqrt(a) * np.sin(theta)
        pepperoni_coords.append((coord_x, coord_y))

    # how many pepperoni are free?
    num_free_pepperoni = 0
    for i in range(n): # for each pepperoni
        pepperoni_coords_copy = pepperoni_coords[:]  # copy the list so the orig is not changed
        this_pepperoni = pepperoni_coords_copy.pop(i) 
        coord_x_1 = this_pepperoni[0]
        coord_y_1 = this_pepperoni[1]
        this_pepperoni_free = True
        for pep in pepperoni_coords_copy: # check it against every other pepperoni
            coord_x_2 = pep[0]
            coord_y_2 = pep[1]
            distance = np.sqrt((coord_x_1 - coord_x_2)**2 + (coord_y_1 - coord_y_2)**2)
            if distance < 2*r:
                this_pepperoni_free = False
                break
        if this_pepperoni_free:
            num_free_pepperoni += 1

    return num_free_pepperoni

for n in n_to_try:
    results = []
    for i in range(trials):
        results.append(one_trial())
    x = np.average(results)
    print "For pizza radius 1, pepperoni radius", r, ", and number of pepperoni", n, ":"
    print "Over", trials, "trials, the average number of free pepperoni was", x
    print "Arthur's quantity:", x* ((((1-r)/1)**(x-1) - (r/1)) / ((1-r) / 1))

Answer 1

Actualizado: ver más abajo (Update 3)

---

He aquí otra aproximación. Considerar el centro de los discos (pepperoni) como una homogénea punto de proceso de densidad de $\lambda = n/A$, donde $A=\pi R^2$ es la pizza de la superficie. Vamos a $D$ ser vecino más cercano distancia de un determinado centro. Entonces

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

Una de pepperoni es gratis si $D > 2r$. Vamos a $E$ ser el número esperado de libre peperoni.

A $$E= n\, P(D>2r) = n \exp (-n \,4 \, r^2/R^2) = n \exp(-n \, p)$$ donde $p=(2r)^2/R^2$ (misma notación como mzp la respuesta).

El máximo se alcanza para (ceil o en el piso de) $n^*=1/p=(R/2r)^2\etiqueta{2}$

Actualización 1: Fórmula de $(1)$ podría ser corregida por los efectos de la frontera, en la zona cerca de la frontera sería calculada como la intersección de dos círculos. Se ve bastante engorroso, sin embargo.

Actualización 2: En el de arriba, yo supuse que el centro de la salchicha puede ser colocado en cualquier lugar dentro de la pizza círculo. Si ese no es el caso, si el pepperoni debe estar completamente dentro de la pizza, luego $R$ debe ser reemplazado por el "radio efectivo" $R' = R-r$

---

Actualización 3: La distribución de Poisson enfoque no es realmente necesario. He aquí una solución exacta

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

(Equivalentemente, creo que de $t$ como la pizza de radio, y asumir una de pepperoni de radio de $1/2$). Deje que $g(x)$ ser el área de un círculo unitario, a una distancia de $x$ desde el origen, se cruzó con el círculo de radio $t$. Entonces

$$g(x)=\begin{casos}\pi & {\rm si}& x \le t-1\\ h(x) & {\rm si}& t-1<x \le t \end{casos} \etiqueta{3}$$ donde $$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]} \etiqueta{4}$$

Deje que la variable aleatoria $e_i$ $1$ si $i$ pepperoni es libre, $0$ lo contrario. Entonces

$$E[e_i \mid x] = \left(1- \frac{g(x)}{\pi \, t^2}\right)^{n-1} \etiqueta{5}$$ (resto de pepperoni caída en la zona libre). Y

$$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 \etiqueta{6}$$

La función objetivo (número esperado de libre pepperoni) es dado por:

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

Esto es exacto... pero (casi?) intratable. Sin embargo, se puede evaluar numéricamente [**].

También podemos tomar como aproximación $$g(x)=\pi$$ (negligencia efectos de borde) y, a continuación, se vuelve 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} \etiqueta{8}$$

Para maximizar, podemos escribir $$\frac{J(n+1)}{J(n)}= \frac{n+1}{n} \left(1- \frac{1}{t^2}\right)=1 $$ lo que da

$$ n^{*}= t^2-1 = \frac{R^2}{4 r^2}-1 \etiqueta{9}$$ muy similares a los de $(2)$.

Observe que, como $t \to \infty$, $J(n^{*})/n^{*} \e^{-1}$, es decir, la proporción de libre pepperoni (cuando se utiliza el número óptimo) es de alrededor de $36.7\%$. También, el "total de pepperoni área" es 1/4 de la pizza.

[**] Algunos Maxima código a evaluar (numéricamente) la solución exacta $(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]);

El primer resultado está de acuerdo con el OP de la simulación, el segundo está cerca: tengo $n^{*}=28$ en vez de $29$. Para el tercer caso, me sale $n^{*}=2529$ ($j(n)=929.1865331$)

Answer 2

Deje que $a \equiv \pi (2r)^2$, $A \equiv \pi R^2$ y $p \equiv \frac{a}{A}$. Denotamos por $P_i^n$ la probabilidad de tener $i$ gratis pepperoni cuando $n$ se distribuyen al azar (de acuerdo a una distribución uniforme) por encima de la pizza. Deje de $E_n$ denotar el número esperado de libre pepperoni dado $n$.

Voy a suponer que el pepperoni puede ser colocado en la pizza mientras su centro se encuentra dentro de él.

• $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$, es decir, la probabilidad de que ambos pepperoni tener sus centros dentro de una distancia de menos de $2r$, en cuyo caso se superponen;
  • $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$, ya que hay $C^3_2$ combinaciones de cómo $2$ de $3$ pepperoni podrían superponerse;
  • $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 $.

• Por inducción, por $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}$.

Por lo tanto el problema se convierte en el de la resolución de

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

Yo no era capaz de resolver esto en general, pero, por ejemplo, si $p=0.1$

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

De modo que el número óptimo de pepperoni es de $n^{*}=5$.

Answer 3

Aquí es una aproximación que utiliza sólo las áreas y no de la geometría. Mientras el pepperonies son bastante agradable (circular, por ejemplo) y la pizza es grande y redondo suficiente como para que el borde no importa, es una buena aproximación.

Dicen que hay $p$ pepperonies, tienen zona de $a$. La pizza tiene $1$. Luego, justo antes de poner la última de pepperoni, $(1-a)^{p-1}$ es la (esperada) área libre de pizza. La probabilidad, por tanto, que la última de pepperoni es gratis es $\frac{(1-a)^{p-1} -} {1}$.

Ya que todos los pepperonies son iguales, esta probabilidad es la misma para todos ellos. Deje de $X_i$ ser la variable aleatoria dada por $1$ si pepperoni número $i$ es libre, y $0$ si no lo es. A continuación, usted desea que el $p$, que maximiza $$ 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} -} {1} $$ que probablemente pueda encontrarse sólo numéricamente, pero si usted acepta esta aproximación, a continuación, un poco de análisis numérico no debería ser a la barra.

Answer 4

Una Primera Aproximación

Deje que $p$ ser la probabilidad de que una de pepperoni no está en conflicto con una colocados al azar de pepperoni, y $P$ la probabilidad de que una de pepperoni es libre.

La expresión exacta para $p$ es el ámbito adecuado para otro pepperoni sobre el total de la zona donde pepperoni puede ser colocado :

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

Donde $A$ es el área de la porción de un círculo de radio $2r$ centrado en el pepperoni centro que está dentro de la zona donde pepperoni puede ser colocado. Yo no podía encontrar una fórmula analítica para $Un$ cuando el pepperoni está cerca de la frontera. En su lugar, yo uso la aproximación, que el pepperoni siempre cubre la misma área, independientemente de donde se coloca.

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

Y tenemos :

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

Esta aproximación es buena cuando el radio de la pizza es grande en comparación con el radio de una de pepperoni.

Ahora, la probabilidad de que pepperoni $i$ es libre cuando $n$ pepperoni se colocan:

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

Y el número esperado de libre pepperoni es :

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

Esta función se parece a este.

Para obtener el máximo, se establece la derivada es igual a 0 :

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

El máximo es el techo o en el piso de este valor.

$$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\}$$

Ahora, algunos números : Si $R= de$30 cm, $r=2$cm, tenemos $p\aprox 0.98$. Entonces :

$$ 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 : Una Mejor Aproximación de Un

He encontrado una mejor manera de aproximado de $Un$, el promedio de la zona en la que otro de pepperoni no puede ser colocado. Es :

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

Donde $r'$ es la distancia entre el centro de la pizza y el centro de la salchicha. Creo que esta fórmula desserves un poco de explicación. Cuando el pepperoni es a una distancia de menos de $R-3r$ desde el centro de la pizza, todos los puntos en un $2r$ radio no son adecuados para una de pepperoni. Si la distancia es mayor que $R-3r$, algunos de los puntos en el círculo de $2r$ radio están fuera de la zona donde pepperoni puede ser colocado (el círculo de La $R-r$ radius).Cuando una de pepperoni es dentro de esa región, consideramos que el área no apto para otro pepperoni es, en promedio, la mitad del área del círculo. Este corresponden a hacer la aproximación de que el borde de la pizza es plana. De nuevo, para una pizza grande, esta aproximación se vuelve más insignificante.

Ahora, el promedio de $A$ se convierte en :

$$ \begin{align} A =& \frac{\int\limits_{0}^{2\pi} \int\limits_{0}^{R-r} (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} $$

Y la probabilidad de $p$ es :

$$ \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} $$

Y el resto de las ecuaciones permanecer sin cambios.

Ahora, cuando $r/R = 0.1$, me da un total de 112 pepperoni colocado, con un valor esperado de 31.74.

Para $r/R = 0.01$, tengo 2449 pepperoni colocado, con un valor esperado de 901.58.