¿Cuántos cromos necesito para completar mi álbum Panini de la FIFA?

Question

Estoy jugando al Álbum de cromos FIFA Panini Online que es una adaptación para Internet de los clásicos álbumes de Panini que se suelen publicar para el mundial de fútbol, la Eurocopa y posiblemente otros torneos.

El álbum tiene marcadores de posición para 424 pegatinas diferentes. El objetivo del juego es coleccionar los 424. Los cromos vienen en paquetes de 5, que pueden obtenerse a través de códigos que se encuentran en línea (o, en el caso del álbum clásico impreso, comprados en el quiosco local).

Hago las siguientes suposiciones:

• Todos los adhesivos se publican en la misma cantidad.
• Un paquete de pegatinas no contiene duplicados.

¿Cómo puedo saber cuántos paquetes de pegatinas tengo que adquirir para ser razonablemente seguro (digamos el 90%) que tengo las 424 pegatinas únicas?

Answer 1

Es un bonito problema de colección de cupones, con un pequeño giro introducido por el hecho de que las pegatinas vienen en paquetes de 5.

Si las pegatinas se compraron individualmente el resultado es conocido, como se puede ver ici .

Todas las estimaciones para un límite superior del 90% para las pegatinas compradas individualmente son también límites superiores para el problema con un paquete de 5, pero un límite superior menos cercano.

Creo que conseguir un mejor límite superior de probabilidad del 90%, utilizando la dependencia del paquete de 5, sería mucho más difícil y no le daría un resultado mucho mejor.

Por lo tanto, utilizando la estimación de la cola $ P[T>\beta n \log n] \leq n^{-\beta+1}$ con $n=424$ y $n^{-\beta+1} = 0.1$ llegarás a una buena respuesta.

EDITAR :

El artículo "El problema del coleccionista con los dibujos de grupo" (Wolfgang Stadje), una referencia del artículo aportado por Assuranceturix, presenta una solución analítica exacta para el Problema del Coleccionista de Cupones con "paquetes de pegatinas".

Antes de escribir el teorema, algunas definiciones de notación: $S$ sería el conjunto de todos los cromos posibles, $s = |S|$ . $A \subset S$ sería el subconjunto que le interesa (en el OP, $A = S$ ), y $l = |A|$ . Vamos a dibujar, con el reemplazo, $k$ subconjuntos aleatorios de $m$ diferentes pegatinas. $X_{k}(A)$ será el número de elementos de $A$ que aparecen en al menos uno de esos subconjuntos.

El teorema dice que:

$$ P(X_{k}(A) = n) = {l \choose n} \sum_{j=0}^{n}(-1)^j {n \choose j}[{s+n-l-j \choose m}/{s \choose m}]^k $$

Así, para el OP tenemos $ l=s=n=424$ y $m=5$ . Hice algunos intentos con valores de $k$ cerca de la estimación para el problema clásico del coleccionista de cupones (729 paquetes) y obtuve una probabilidad del 90,02% para k igual a 700 .

Así que no estaba tan lejos del límite superior :)

Answer 2

El otro día me encontré con un artículo que aborda una cuestión estrechamente relacionada:

http://www.unige.ch/math/folks/velenik/Vulg/Paninimania.pdf

Si lo he entendido bien, el número previsto de paquetes que habría que comprar sería:

$\binom{424}{5}\sum_{j=1}^{424}\left(-1\right)^{j+1}\frac{\binom{424}{j}}{\binom{424}{5}-\binom{424-j}{5}}$

Sin embargo, como señala eqperes en los comentarios, la cuestión específica que plantea el PO se trata en detalle en otro documento que no es de acceso abierto.

Su conclusión final sugiere la siguiente estrategia (para un álbum de 660 cromos):

• Compre una caja de 100 paquetes de 5 pegatinas (500 pegatinas, con garantía de ser todas diferentes)
• Compra otros 40 paquetes de 5 pegatinas e intercambia los duplicados hasta que tengas como máximo 50 pegatinas perdidas.
• Compra el resto de pegatinas directamente a Panini (cuestan aproximadamente 1,5 veces más).

Se trata de un total de 140 paquetes + hasta 15 paquetes adicionales de pegatinas (por su coste) comprados de forma selectiva, lo que equivale como máximo a 155 paquetes .