De combien d'autocollants ai-je besoin pour terminer mon album FIFA Panini?

30

Je joue à l' Album d'autocollants en ligne FIFA Panini , qui est une adaptation Internet des albums Panini classiques qui sont généralement publiés pour la coupe du monde de football, le championnat d'Europe et peut-être d'autres tournois.

L'album contient des espaces réservés pour 424 autocollants différents. Le but du jeu est de collecter les 424. Les autocollants sont livrés en paquets de 5, qui peuvent être obtenus à l'aide de codes trouvés en ligne (ou, dans le cas de l'album imprimé classique, achetés dans votre kiosque à journaux local).

Je fais les hypothèses suivantes:

  • Tous les autocollants sont publiés dans la même quantité.
  • Un paquet d'autocollants ne contient pas de doublons.

Comment puis-je savoir combien de packs d'autocollants je dois acheter pour être raisonnablement sûr (disons 90%) que j'ai tous les 424 autocollants uniques?

Vidar S. Ramdal
la source
2
Un certain nombre d'idées peuvent être tirées de la lecture d'autres questions relatives au problème du collecteur de coupons .
Glen_b -Reinstate Monica
3
Vous avez besoin de 700 packs; la chance d'acquérir les 424 autocollants équivaut alors à 90,0024%. 761 sont nécessaires pour porter la chance à 95% et 898 pour une chance de 99%. (En moyenne, près de 560 packs sont nécessaires pour compléter l'ensemble. Il est peu probable (moins d'une chance sur mille) que moins de 352 soient nécessaires.)
Whuber
1
Je ne suis pas sûr que la première hypothèse puisse être faite. Les "Shinies" ont tendance à être plus rares.
James
2
Hmm, d'après ce que j'ai pu lire du document publié par Asuranceturix, ils ont prouvé qu'il n'y avait pas de différence significative.
Vidar S. Ramdal
@ VidarS.Ramdal Je me tiens corrigé.
James

Réponses:

15

C'est un beau problème de collecteur de coupons, avec une petite touche introduite par le fait que les autocollants sont livrés en paquets de 5.

Si les autocollants ont été achetés individuellement, le résultat est connu, comme vous pouvez le voir ici .

Toutes les estimations pour une limite supérieure de 90% pour les autocollants achetés individuellement sont également des limites supérieures pour le problème avec un pack de 5, mais une limite supérieure moins étroite.

Je pense qu'obtenir une meilleure limite supérieure de probabilité de 90%, en utilisant le pack de 5 dépendances, deviendrait beaucoup plus difficile et ne vous donnerait pas un bien meilleur résultat.

Donc, en utilisant l'estimation de queue avec et , vous obtiendrez une bonne réponse. n = 424 n - β + 1 = 0,1P[T>βnlogn]nβ+1n=424nβ+1=0.1

MODIFIER :

L'article "Le problème du collectionneur avec les dessins de groupe" (Wolfgang Stadje), une référence de l'article apporté par Assuranceturix, présente une solution analytique exacte pour le problème du collecteur de coupons avec des "packs d'autocollants".

Avant d'écrire le théorème, quelques définitions de notation: serait l'ensemble de tous les autocollants possibles,. serait le sous-ensemble qui vous intéresse (dans l'OP, ), et. Nous allons dessiner, avec remplacement, sous-ensembles aléatoires de différents autocollants. sera le nombre d'éléments de qui apparaissent dans au moins un de ces sous-ensembles.s = | S | A S A = S l = | A | k m X k ( A ) ASs=|S|ASA=Sl=|A|kmXk(A)A

Le théorème dit que:

P(Xk(A)=n)=(ln)j=0n(1)j(nj)[(s+nljm)/(sm)]k

Ainsi, pour l'OP, nous avons et . J'ai fait quelques essais avec des valeurs de proches de l'estimation du problème du collecteur de coupons classiques (729 paquets) et j'ai eu une probabilité de 90,02% pour k égal à 700 .m = 5 kl=s=n=424m=5k

Ce n'était donc pas si loin de la limite supérieure :)

Jundiaius
la source
Et cette bonne réponse le ferait?
ziggystar
4
Environ 3642 autocollants aléatoires. Ainsi, la limite supérieure pour le "pack de 5 problèmes" serait quelque chose de moins de 729 packs.
Jundiaius
10

L'autre jour, je suis tombé sur un document qui répond à une question étroitement liée:

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

Si je l'ai bien compris, le nombre attendu de packs que vous devrez acheter serait:

(4245)j=1424(1)j+1(424j)(4245)(424j5)

Cependant, comme le souligne eqperes dans les commentaires, la question spécifique posée par le PO est en fait traitée en détail dans un autre document qui n'est pas en libre accès.

Leur conclusion finale suggère la stratégie suivante (pour un album de 660 autocollants):

  • Achetez une boîte de 100 paquets de 5 autocollants (500 autocollants, garantis tous différents)
  • Achetez 40 autres packs de 5 autocollants et échangez les doublons jusqu'à ce que vous ayez au plus 50 autocollants manquants.
  • Achetez les autocollants restants directement auprès de Panini (ceux-ci coûtent environ 1,5 fois plus).

Cela représente un total de 140 packs + jusqu'à 15 packs supplémentaires d'autocollants (par coût) achetés de manière ciblée, soit au maximum 155 packs .

Asuranceturix
la source
Génial! Il semble que l'argument central de leurs résultats serait dans l'article "Le problème du collectionneur avec les dessins de groupe" , qui n'est malheureusement pas en libre accès.
Jundiaius
Haha, c'est super! Ils entrent également dans le détail sur la façon dont l'échange affecte le résultat (ce que j'ai laissé de côté). Très intéressant, merci!
Vidar S. Ramdal
3
Pouvez-vous résumer la solution au problème du PO fournie par le document? Les liens expirent parfois et cette réponse deviendra alors moins utile.
Andy
@Andy: J'ai modifié la réponse pour répondre à votre préoccupation, mais ce n'est pas exactement la réponse à la question d'origine. Malheureusement, le document original qui fournit cette réponse est trop difficile à lire pour moi, désolé.
Asuranceturix
Je doute d'une boîte de 100 packs contenant uniquement des autocollants distincts. Il semble que cela entraînerait des complications de fabrication énormes et inutiles pour peu d'avantages.
jwg