Leçon
Compléter une collection prend plus de temps que tu ne le penses
Remplir les derniers éléments d'une collection coûte beaucoup plus cher que les premiers, car les doubles s'accumulent vers la fin.
Par l'équipe de rédaction de Math Says Yes
Examiné par des humains selon nos normes en matière de sources et de corrections.
Comment nous évaluons le contenu
La règle de n·ln n
Il semble naturel de supposer que collecter n articles différents prend environ n essais. Ce n'est pas le cas. Lorsque chaque essai te donne un article uniformément aléatoire, compléter la collection prend environ n fois le logarithme népérien de n. Pour une collection de 50, cela fait environ 225 essais, pas 50. La raison est que tu continues à tirer des articles que tu possèdes déjà. Au début, presque chaque tirage est nouveau, donc le compte grimpe rapidement, mais la progression ralentit fortement à mesure que la collection se remplit, car la de tirer un article manquant ne cesse de diminuer. Plus la collection est grande, pire devient cet écart entre n et n·ln n.
La queue cruelle
La fin est là où le coût se cache. Supposons que tu possèdes n - 1 articles sur n (il ne t'en manque qu'un). Chaque tirage donne l'article manquant avec une de 1 sur n, et n'importe quoi d'autre est un doublon. Le nombre d'essais dont tu as besoin découle de cette unique chance : en , il faut environ n tirages rien que pour obtenir ce dernier article. Ainsi, dans un ensemble de 50 articles, le dernier autocollant à lui seul prend en moyenne environ 50 paquets, tandis que la première moitié de l'ensemble est arrivée en une petite fraction de cela. La queue de n'est pas un détail négligeable. C'est la partie la plus coûteuse de tout l'effort, et c'est exactement celle que notre planification a tendance à ignorer.
Pourquoi l'échange l'emporte
Si les doublons rendent la fin coûteuse, s'en débarrasser la rend bon marché. Lorsque tu échanges un article en double avec un autre collectionneur qui en a besoin contre un qu'il te manque, tu élimines la partie lente du problème. Deux collectionneurs qui échangent leurs doubles évitent l'attente pénible des quelques articles rares, car ton surplus est le manque de quelqu'un d'autre et vice versa. C'est la logique mathématique derrière la culture de l'échange d'autocollants : la tradition de la cour d'école consistant à échanger des doubles n'est pas seulement sociale, c'est le moyen le plus efficace de battre le coût n·ln n. Un marché de troc transforme une queue de individuelle brutale en une fin collective rapide.
Où cela apparaît
La même forme apparaît bien au-delà des albums d'autocollants. Les coffres mystères et les jeux gacha distribuent des récompenses aléatoires, donc compléter une liste de personnages ou de cartes se heurte exactement à cette queue de , ce qui explique en partie pourquoi les derniers sont si frustrants à obtenir. Les tests logiciels y sont aussi confrontés : si un programme a de nombreux chemins de code rares et que tes entrées les atteignent au hasard, tous les couvrir prend beaucoup plus de temps que le nombre de chemins ne le suggère, et la dernière branche non testée peut s'avérer obstinément difficile à déclencher. Chaque fois que tu as besoin de chaque article d'un ensemble fixe et que tu les collectionnes au hasard, attends-toi à ce que la ligne d'arrivée soit beaucoup plus éloignée que ne le laisse supposer la taille de l'ensemble.
FAQ
Un ensemble plus grand devient-il disproportionnellement plus difficile à terminer ?
Oui. L'achèvement évolue proportionnellement à n fois ln n plutôt qu'à n, donc doubler la taille de l'ensemble multiplie par plus de deux les essais nécessaires en moyenne. Le facteur logarithmique croît avec n, ce qui explique pourquoi les grandes collections semblent si pénibles vers la fin.
Pourquoi l'échange de doubles aide-t-il autant ?
Parce que les doublons sont précisément ce qui rend la fin coûteuse. Échanger tes doubles contre des articles qui te manquent supprime la longue attente des pièces rares manquantes, puisque ton surplus comble le vide d'un autre collectionneur et que le sien comble le tien. Un marché d'échange convertit une fin individuelle lente en une fin partagée rapide.
Teste l'idée
Collectionneur de coupons
Ouvre des paquets et regarde les toute dernière vignettes stagner.
0%
% complété
0
paquets ouverts
91
estimé pour finir
Les premières vignettes arrivent vite, mais vers la fin, presque chaque paquet est un doublon — le dernier article à lui seul demande à peu près autant de paquets que la collection entière compte d'articles.
Vérification rapide
Tu as 49 autocollants sur 50. Avec 1 autocollant aléatoire par tirage, combien de tirages faut-il de plus pour obtenir le dernier, en moyenne ?
A
Environ 50 tirages.
B
Environ 2 tirages.
C
Environ 5 tirages.