Nora prépare une collection fictive de quatre noms A,B,C,D sur des cartes de service. À chaque passage, un nom paraît, uniformément parmi les quatre et indépendamment des passages précédents. La carte reçue est notée puis la possibilité de tirer chaque nom reste intacte. Camille doit arrêter dès que tous les noms ont été reçus au moins une fois. Les passages ne sont ni minutes ni opérations réellement observées ; leurs chances appartiennent au protocole donné.
La notice337750 porte la catégorie Prints.
La notice337760 porte la catégorie Drawings.
La notice337770 porte la catégorie Drawings.
Ces catégories seules ont été lues. Les cartes, leurs chances et les décisions de collecte sont créées ici ; aucune image ou méthode d'artiste ne les fournit.
Quatre passages peuvent compléter la feuille sans en donner la certitude
Nora reçoit A,A,B,C aux quatre premiers passages. Elle a quatre inscriptions, mais D manque encore. Camille ne ferme pas la collection en donnant quatre comme son nombre de catégories. La seconde carte A reste dans le relevé des passages et n'ajoute aucun nom nouveau à la collection. À l'inverse, A,B,C,D fermerait effectivement la feuille au quatrième passage. Camille garde les deux histoires, avec la liste des noms acquis à côté du nombre de passages, pour que le même quatre ne désigne pas indifféremment ces deux quantités.
Il existe quatre puissance quatre, soit deux cent cinquante-six histoires équiprobables de quatre passages. Pour avoir déjà tous les noms, chacun doit apparaître exactement une fois : les vingt-quatre ordres des quatre noms passent. La chance de compléter en quatre est donc vingt-quatre sur deux cent cinquante-six, soit trois trente-deuxièmes. Nora refuse une feuille qui promettait la collection après quatre parce qu'il y a quatre noms possibles. Elle remet quatre comme première durée possible, avec sa chance précise, et conserve les deux cent trente-deux histoires qui n'ont pas encore fini à cette limite.
Une commande nouvelle impose une réserve contenant exactement une carte de chaque nom, tirée sans remettre les cartes. Les quatre passages y donnent forcément tous les noms. Les vingt-quatre ordres restent disponibles et sont équiprobables, mais A,A,B,C est maintenant impossible. Nora retient cette réserve si elle veut une fin certaine en quatre. Elle ne conserve pas simultanément l'ancienne possibilité de reprendre A après A : la remise des cartes entre les passages était précisément ce qui permettait les répétitions et retirait cette certitude.
L'attente d'un nom nouveau dépend de ce qui manque
Camille revient au protocole indépendant avec remise. Après le premier passage, un nom est acquis et trois manquent. La chance d'un nom nouveau au passage suivant vaut trois quarts. Si le nom reçu est encore le premier, la même chance trois quarts reste disponible au passage suivant : aucune couleur n'est renforcée. Le nombre moyen de passages jusqu'au prochain nom nouveau vaut donc quatre tiers. Après deux noms acquis, il vaut deux ; après trois, quatre. Nora garde ces attentes supplémentaires auprès des états de sa collection, sans attribuer quatre à chacun des quatre noms depuis le début.
Le premier nom arrive toujours en un passage. La somme des quatre étapes vaut donc un plus quatre tiers plus deux plus quatre, soit vingt-cinq tiers, environ huit et un tiers. Camille remet cette moyenne du nombre de passages nécessaires pour compléter, plutôt que seize obtenu en ajoutant quatre attentes de quatre. Les étapes ne portent pas sur quatre noms prédéterminés à rechercher l'un après l'autre : la première nouvelle carte peut être n'importe lequel, puis la suivante n'importe lequel des trois absents. Leurs chances de nouveauté diminuent avec la collection acquise, ce qui a produit les quatre termes différents.
Sur l'histoire A,A,B,C, Nora a trois noms après quatre passages. L'attente supplémentaire vaut alors quatre, car seul D manque et paraît avec un quart à chaque passage. Sur A,A,A,A, il lui manque trois noms : elle doit encore traverser les attentes quatre tiers,deux,quatre, de somme vingt-deux tiers. Camille n'ajoute donc pas uniformément quatre après n'importe quel relevé de quatre passages. Elle choisit l'attente depuis l'état réellement reçu. Le compte de passages seul n'avait pas conservé la liste nécessaire pour distinguer ces deux décisions de poursuite.
Une limite favorable à la plupart des histoires n'est pas leur nombre moyen
Nora demande de prévoir une limite donnant au moins une chance sur deux d'avoir complété la collection. Camille compte la probabilité qu'un nom manque après n passages. Chacun peut manquer avec trois quarts puissance n, mais additionner les quatre chances compterait plusieurs fois les histoires auxquelles manquent deux noms ou davantage. Les six paires de noms peuvent manquer avec une moitié puissance n ; les quatre triples avec un quart puissance n. Pour n positif, manquer les quatre est impossible. La chance d'avoir fini est ainsi un moins quatre fois trois quarts puissance n, plus six fois une moitié puissance n, moins quatre fois un quart puissance n.
À six passages, ce calcul donne cent quatre-vingt-quinze sur cinq cent douze, moins qu'une moitié. À sept, il donne cinq cent vingt-cinq sur mille vingt-quatre, un peu plus. Nora choisit donc sept comme première limite entière remplissant sa demande. La chance de finir ne diminue pas lorsque la limite est repoussée ; il suffit ainsi d'avoir écarté six pour fermer la recherche sur les limites plus petites. Camille ne transmet pas la moyenne vingt-cinq tiers arrondie comme si elle avait répondu à cette commande de proportion. Sept et vingt-cinq tiers sont deux réponses exactes à deux questions effectivement différentes.
La limite douze donne un million huit cent trente-quatre mille cinq cent trois sur deux millions quatre-vingt-dix-sept mille cent cinquante-deux. Cette fraction est encore inférieure à neuf dixièmes : dix fois son numérateur est inférieur à neuf fois son dénominateur. Nora refuse donc douze si la demande nouvelle est neuf histoires terminées sur dix en proportion. Elle ne garde pas douze sous la légende « presque toutes » pour éviter de montrer le reste. Le calcul précédent peut être repris pour chercher la nouvelle limite ; aucun passage de la liste ne garantit à lui seul la fin certaine sous la remise indépendante.
Avec des chances différentes, le nombre de noms acquis ne suffit plus
Une branche distincte possède trois noms A,B,C, avec les chances fixes une moitié, un tiers, un sixième. Chaque passage reste indépendant et n'ajoute aucun poids au nom reçu. Après avoir acquis A, les deux absents B et C ont des attentes isolées trois et six. Nora ne peut les additionner pour obtenir neuf : les mêmes futurs passages peuvent faire avancer les deux recherches, selon les noms rencontrés. Le premier des deux apparaît avec une moitié ; son attente vaut deux. Pour attendre les deux, l'identité maximum égale somme moins minimum des deux temps donne trois plus six moins deux, soit sept.
Après avoir acquis B, les noms A et C manquent. Leurs attentes isolées sont deux et six, et le premier des deux apparaît avec deux tiers, d'attente trois demis. La complétion future a donc une attente treize demis. Après avoir acquis C, A et B manquent ; deux plus trois moins six cinquièmes donnent dix-neuf cinquièmes. Camille remet sept,treize demis,dix-neuf cinquièmes avec les trois relevés à un nom. La fiche « un acquis » aurait conservé le même compte dans ces trois cas et perdu précisément l'identité qui change leur attente. Nora choisit de garder cette identité dans l'état transmis.
La présence préalable du nom rare C raccourcit ainsi l'attente restante à dix-neuf cinquièmes. Ce résultat ne prétend pas que C serait plus facile à obtenir : il vient d'avoir été acquis, donc sa longue attente six ne fait plus partie de la commande future. Si Nora reçoit plutôt A au premier passage, C reste à attendre avec B et la moyenne future vaut sept. Camille refuse d'écrire six pour l'attente restante de toute collection incomplète, au seul motif qu'un nom possède un sixième. Les noms déjà présents ne doivent plus recevoir gratuitement une seconde obligation d'apparition.
La feuille des sous-ensembles ferme le calcul depuis le départ
Camille note pour chaque ensemble acquis son attente restante E. Avec les trois noms, E vaut zéro. Avec A et B, seul C manque et E vaut six ; avec A et C, E vaut trois ; avec B et C, E vaut deux. Pour l'ensemble A seul, un passage coûte un, puis A laisse l'état identique avec une moitié, B laisse seulement C à attendre avec un tiers et C laisse seulement B avec un sixième. L'équation est E(A)=un plus une moitié de E(A), plus un tiers de six, plus un sixième de trois. Elle redonne sept après avoir déplacé le terme qui conservait l'ancien état.
Depuis B seul, l'équation donne E(B)=un plus un tiers de E(B), plus une moitié de six, plus un sixième de deux, donc treize demis. Depuis C seul, elle donne E(C)=un plus un sixième de E(C), plus une moitié de trois, plus un tiers de deux, donc dix-neuf cinquièmes. Nora peut ainsi reprendre les trois attentes depuis les états successeurs effectivement atteignables, au lieu de compter deux attentes isolées comme si leurs passages devaient être effectués dans deux séries séparées. La répétition d'un nom acquis conserve l'état ; elle ne supprime pas le passage de coût un.
Au départ vide, le premier passage donne A,B,C avec leurs trois chances. La moyenne complète est donc un plus une moitié de sept, plus un tiers de treize demis, plus un sixième de dix-neuf cinquièmes : soixante-treize dixièmes. Camille remet sept et trois dixièmes comme nombre moyen de passages. Une collection uniforme de trois noms aurait donné un plus trois demis plus trois, soit onze demis. Nora conserve le résultat uniforme dans sa branche propre, mais ne le réutilise pas après avoir rendu C plus rare. Les noms possibles sont restés trois ; leurs chances ont réellement changé l'attente calculée.
Une catégorie forcée ajoute une permission dont le prix doit être compté
Nora ouvre enfin une possibilité d'intervention. À n'importe quel état incomplet de la branche non uniforme, elle peut soit faire un passage indépendant de coût un, soit commander directement un nom absent pour un coût trois. Le nom forcé rejoint la collection avec certitude et la décision peut être reprise ensuite. Les coûts sont des unités stipulées, pas un temps matériel ni un tarif commercial. Camille cherche cette fois le coût moyen minimal jusqu'à la collection complète, et non le seul nombre de passages aléatoires. Un acte forcé coûte trois même si aucune nouvelle carte ne doit ensuite être attendue.
Avec A et B déjà acquis, attendre C au hasard coûte six en moyenne, tandis que forcer C coûte trois. Nora choisit l'intervention. Avec A et C, attendre B coûte trois, égal au coût de le forcer : elle dispose de deux choix de même coût moyen, l'un avec une fin immédiate stipulée et l'autre avec un nombre aléatoire de passages. Avec B et C, attendre A coûte deux, moins que trois ; elle garde les passages aléatoires. Camille remet les trois décisions avec leurs états. Une consigne « forcer toujours le nom manquant » aurait dépensé une unité de trop lorsque seul A manque.
Depuis A seul, Nora peut attendre le prochain nouveau nom. La répétition de A conserve l'état avec une moitié ; recevoir B laisse C à forcer pour trois, et recevoir C laisse B à obtenir pour trois. Le coût attendu de cette politique vaut un plus une moitié de lui-même, plus un tiers de trois, plus un sixième de trois, donc cinq. Forcer C d'emblée coûterait trois puis trois pour B, total six ; forcer B coûterait également six. Nora choisit donc de tirer d'abord depuis A, même si elle forcera C quand B aura ensuite paru. Le droit d'intervenir ne signifie pas que l'intervention doit précéder tous les tirages.
Depuis B seul, le même calcul utilise trois après A et deux après C. Le coût vaut un plus un tiers de lui-même, plus une moitié de trois, plus un sixième de deux, donc dix-sept quarts. Forcer C d'abord coûterait trois puis deux pour A, soit cinq ; forcer A coûterait trois puis trois pour C, soit six. Nora retient encore le passage aléatoire. Depuis C seul, les deux catégories restantes ne présentent aucune intervention moins coûteuse : le résultat demeure dix-neuf cinquièmes. Camille conserve ces trois coûts cinq,dix-sept quarts,dix-neuf cinquièmes auprès des ensembles A,B,C, plutôt que d'appliquer la décision prise depuis A à un ensemble portant un autre nom.
L'option la moins chère au départ peut attendre pour intervenir
Depuis l'ensemble vide, tirer d'abord coûte un puis laisse ces trois états avec leurs chances. Le total est un plus une moitié de cinq, plus un tiers de dix-sept quarts, plus un sixième de dix-neuf cinquièmes, soit cent onze vingtièmes. Forcer A d'abord coûterait trois plus cinq, soit huit. Forcer B coûterait trois plus dix-sept quarts, soit vingt-neuf quarts. Forcer C coûterait trois plus dix-neuf cinquièmes, soit trente-quatre cinquièmes. Nora choisit le premier passage aléatoire, de coût moyen cinq et onze vingtièmes sous les décisions ultérieures retenues.
La vérification d'optimalité garde toutes les actions disponibles dans chaque sous-ensemble. Forcer un nom absent avance vers un ensemble plus grand ; recevoir un nouveau nom au hasard fait de même ; recevoir un nom déjà acquis laisse le même état. Les valeurs des ensembles plus grands étaient donc déjà connues lorsque Camille comparait ces actes. L'équation de tirage isole sa répétition de l'état, puis la comparaison avec chaque coût forcé choisit le plus petit. Il n'existe pas une quatrième action consistant à recommander gratuitement un nom déjà reçu pour modifier ses chances futures : cette action ne fait pas partie de la permission donnée.
Le premier passage peut donner A, suivi de B. Nora intervient alors pour C et termine, avec deux coûts un puis un coût trois, total cinq pour cette histoire. Si les premiers passages donnent C puis B, elle conserve au contraire le hasard pour A, car son attente deux bat trois. Les deux histoires ont deux noms distincts après deux passages, mais la décision suivante diffère. Camille remet ces réalisations avec la politique moyenne cent onze vingtièmes ; ce nombre ne remplace pas leurs coûts individuels ni le nom qui décide de l'intervention. Le gain par rapport à soixante-treize dixièmes vient de l'action nouvellement permise lorsque le rare C reste seul à obtenir.
Les catégories consultées ne fournissent aucun tirage, coût ou intervention. Les états acquis et les permissions gardent leurs contrôles sur la feuille.
Une fin certaine sous plafond n'est pas le coût moyen minimal
Une branche séparée garde les trois chances et le prix trois des noms forcés, mais exige une collection complète avec certitude sous un plafond de coût. Nora ne demande plus la moyenne minimale. Camille ne peut lui promettre six à partir de cent onze vingtièmes : une histoire qui reprend longtemps le premier nom pouvait encore laisser deux noms absents sous cette politique. La borne doit maintenant couvrir toutes les histoires possibles, même rares, et inclure le prix des interventions effectivement décidées.
Nora choisit un premier passage aléatoire, de coût un, puis force les deux noms qui manquent pour trois chacun. Si A paraît, elle force B et C ; si B paraît, elle force A et C ; si C paraît, elle force A et B. Chaque branche termine à coût sept et possède exactement les trois noms. Commander directement A,B,C aurait coûté neuf. La première carte aléatoire permet réellement d'éviter une de ces trois commandes, quel que soit son nom ; elle n'est pas une estimation d'une économie moyenne. Nora retient sept comme plafond certain et joint les trois suites d'actes. Sous le critère précédent, cette préparation coûtait aussi sept en moyenne et perdait face à cent onze vingtièmes. La nouvelle demande accepte donc une préparation plus chère en moyenne pour supprimer toute histoire qui dépasse sa limite.
Camille vérifie qu'un plafond six ne peut fournir cette certitude. Elle considère les histoires où chaque passage aléatoire donne A. Pour obtenir B et C dans ces histoires, la politique doit les forcer toutes deux, coût six. A doit aussi avoir été acquis : au moins un passage aléatoire de coût un, ou une troisième commande de coût trois. Le total est donc au moins sept, même si les décisions dépendent des résultats déjà reçus. Avec un plafond six, il ne peut y avoir plus de six passages aléatoires ; la suite de tous A jusque-là garde une chance strictement positive, car chaque A vaut une moitié. La politique ne peut exclure cette histoire de la garantie en la qualifiant de rare. Sept est ainsi réalisé et minimal pour la fin certaine, tandis que le coût moyen cent onze vingtièmes reste attaché à l'autre commande.
Deux collections peuvent recevoir le même passage ou deux passages propres
Une préparation distincte possède deux collections à compléter. La première a déjà A, la seconde B. À chaque tour, les chances de A,B,C restent une moitié,un tiers,un sixième. Il n'y a ici aucune catégorie forcée. Camille peut tirer un seul nom et le noter dans les deux collections, ou tirer deux noms indépendants, un pour chacune. Elle veut que les deux collections soient complètes ; les tours et les tirages seront comptés séparément.
Avec un nom partagé par tour, deux tours ne peuvent terminer les deux collections. La première attend B et C, la seconde A et C : il faut donc que les nouveaux tours aient fourni A,B,C, trois noms différents. Avec les deux tirages propres, deux tours peuvent déjà suffire. La première reçoit B,C ou C,B, chance un neuvième ; la seconde reçoit A,C ou C,A, chance un sixième. Leurs tirages indépendants donnent les deux collections complètes avec un cinquante-quatrième. Nora remet par exemple B puis C à la première et C puis A à la seconde. Les deux tours ont consommé quatre tirages, tandis que la préparation partagée n'en aurait consommé que deux. Elle choisit les tirages propres lorsque sa demande conserve une possibilité de terminer les deux feuilles en deux tours, et retire cette possibilité de la fiche à nom partagé.
Au troisième tour, la comparaison des chances change de sens. Le nom partagé complète les deux collections exactement quand les trois noms ont paru ; les six ordres donnent une chance un sixième. Pour les tirages propres, la première feuille est complète avec un quart, la seconde avec un tiers, donc les deux avec un douzième. Nora choisit alors le passage partagé si elle veut maximiser la chance d'avoir fini à cette limite trois. Elle conserve pourtant son résultat nul à la limite deux : l'avantage nouveau à trois ne lui donne pas une domination à toutes les limites. A et B étaient déjà acquis sur des feuilles différentes ; les réunir dans un seul inventaire avant les passages aurait répondu à une autre demande, où seul C manquerait et où deux complétions séparées n'auraient jamais été exigées.
Camille contrôle également le coût de ces deux préparations. Avec le passage partagé, attendre les deux collections revient à attendre A,B,C depuis aucun nom nouveau : soixante-treize dixièmes de tirages et de tours en moyenne. Avec les tirages propres, arrêter les tirages d'une feuille dès qu'elle est complète donne sept plus treize demis, soit vingt-sept demis de tirages en moyenne. Les tours jusqu'à la fin commune sont une autre quantité : leur attente est celle du maximum des deux temps, et non vingt-sept demis. Pour n tours, les chances de fin des deux feuilles sont un moins deux tiers puissance n moins cinq sixièmes puissance n plus une moitié puissance n, et un moins une moitié puissance n moins cinq sixièmes puissance n plus un tiers puissance n. Leur produit donne la fin commune. La somme exacte des chances de la dépasser donne557413/60060 tours. Nora joint ce coût aux deux réponses de limite, sans compter chaque tirage propre comme un tour partagé ou prolonger inutilement une feuille déjà finie.