Podemos obtener uppper y los límites inferiores en el número esperado de pequeñas plazas necesarias para cubrir un $N \times N$ gran plaza. Para el límite inferior:
Consideremos el conjunto a $K$ de los puntos de $(k_x,k_y)$ $k_x$ $k_y$ ambos enteros en $[0,N]$.
Hay $(N+1)^2$ dichos puntos. Cualquier completa que abarca, al menos, cubrir todos los puntos de $K$, y cualquier colocado pequeña plaza con casi seguramente (que es, con probabilidad 1) cubrir exactamente un punto en $K$. Así, un límite inferior para el problema se reduce a la siguiente:
Dada una secuencia $s_i$ de los enteros $n_i$ uniformemente al azar en el intervalo de $J \equiv [1,j]$. Encontrar el valor esperado $T_j$ del valor mínimo de $i$ tal que $\bigcup s_i = J$.
Podemos encontrar que el valor esperado mirando a la función de $t_j(p)$, el tiempo de espera para cubrir el $J$ si $p$ de los enteros ya están cubiertos. (Lo $T_j = t_j(0)$.
Toma en promedio $\frac{j}{j-p}$ intenta golpear en un número que no era de los que ya están cubiertos. Por lo $t_j(j-1) = j$, y para todos los $0 \leq p < j-1$
$$
t_j(p) = \frac{j}{j-p} + t_j(p+1)
$$
Así
$$
t_j(p) = \sum_{p=p}^{j-1} \frac{j}{j-q} = j \sum_{p=p}^{j-1} \frac{1}{j-q}
= j \sum_{i=1}^{j-p} \frac{1}{i} = j H_{j-p}
$$
donde $H_n$ es la suma de armónicos $\frac{1}{1}+\frac{1}{2} +\ldots + \frac{1}{n}$.
Observe que al aislar el efecto que nos importa de cualquier pequeña plaza a sólo un punto en $K$, hemos cambiado más difícil 2-D problema a una más fácil 1-D problema.
Sin embargo, los $1\times 1$ plazas, mientras que abarque todos los puntos de la cuadrícula en $K$, podría dejar huecos en los puntos entre los puntos de la cuadrícula.
Por lo tanto un límite inferior para el tiempo de espera para la cobertura de la plaza de es
$$
T_{(N+1)^2} = t_{(N+1)^2}(0) = (N+1)^2 H_{(N+1)^2}
$$
que crece como $2N^2 \log N$.
Ahora para obtener un límite superior:
Consideremos el conjunto a $M$ de los puntos
$\left(\frac{m_x}{2}+\frac{1}{4}, \frac{m_x}{2}+\frac{1}{4}\right)$ $m_x$ $m_y$ ambos enteros en $[0,2N-1]$.
Hay $(2N)^2$ dichos puntos. Cualquier unidad de la plaza con una probabilidad de 1 cubre totalmente el
$\frac{1}{2}\times\frac{1}{2}$ cuadrados centrada en un punto en $M$ más cercano a la unidad centro de la plaza. Por lo tanto, si todos los miembros de $M$ está cubierto por una plaza para el cual es el más cercano al centro, a continuación, toda la $N\times M$ plaza está cubierta.
Así que un límite superior para el problema se reduce a que el mismo problema de encontrar la espera que cubre tiempo para un conjunto de números enteros, sólo que esta vez necesitamos $T_{4N^2}$.
Por lo tanto un límite superior para el tiempo de espera para la cobertura de la plaza de es
$$
T_{4N^2} = 4N^2 H_{4N^2}
$$
que crece como $8N^2 \log N$.
Así como se espera, la expectativa de la cubierta el tiempo crece como $N^2 \log N$, y como cuestión de hecho, el coeficiente entre el$2$$8$.
