Microsoft Paint Pintura En Spray De La Herramienta

Question

La siguiente pregunta está motivada por la herramienta de pintura en spray en Microsoft Paint. En un sentido, me estoy preguntando cuántos clics, en promedio, son necesarios para llenar cada uno de los píxeles dentro de la gama de la herramienta si dejamos el cursor fijo. La siguiente es una más precisa declaración de la pregunta:

Considere la posibilidad de $n$ dados, cada uno con $k$ lados. Un rollo consiste en tirar todos los $n$ dados. Determinar el $E(n,k)$, se espera que el número de rollos necesarios para que todos los números de $1,\ldots,k$ han aparecido en algunos de rollo.

La traducción de pintura en spray puede ser visto por suponiendo que el rango de la herramienta de pintura en spray es $k$ píxeles, y cada clic pinturas $n$ de los píxeles aleatorios.

Recuerdo que buscan en este problema de hace años, y sólo parcialmente la resolución de la misma. Creo que he trabajado en el caso de $n=1$:

$$E(1,k)=kH_k=k\sum_{i=1}^k\frac{1}{i}$$

Aquí $H_k$ $k$ésimo número armónico. No estoy totalmente convencido de que se de este resultado. Para $n=2$ sólo pude encontrar una forma cerrada para el comportamiento asintótico como $k$ se grande. Mi memoria de la solución es un poco difusa, aunque.

Answer 1

Para $n \gt 1$ te puedes imaginar el morir de los rollos en un lote de $n$ son secuenciales. Excepto por el último censo, la situación es la misma, por lo $E(n,k) \approx \frac 1nE(1,k)$. Realmente va a ser un poco más alto que este, como usted (en efecto) mantener rodando hasta el siguiente múltiplo de $n$, cuando con $n=1$ le gustaría dejar de fumar. La heurística respuesta sería que, en promedio, que sería un desperdicio de la mitad de los rollos, por lo $E(n,k) \approx \frac 1nE(1,k)+\frac 12$. Para hacerlo mejor, creo que se tendría que evaluar la probabilidad de finalización en cada múltiplo de $n$.