Camille reçoit une suite d’étiquettes pour une activité de table. Elle souhaite repérer une identité qui revient sur plus de la moitié des fiches, mais ne veut pas garder un compteur séparé pour chaque identité rencontrée. Nora lui propose une petite mémoire de candidats. Le projet doit distinguer ce que cette mémoire peut préserver, ce qu’elle peut certifier immédiatement et ce qui demande encore une consultation de la suite exacte. Une identité restant sur la feuille ne reçoit donc pas d’avance le titre de majorité.
Les lettres, les occurrences et les opérations sont stipulées. Il s’agit de fiches sur papier, sans vote observé, jugement sur des personnes ou logiciel installé. Les méthodes de cancellation sont classiques ; nous ne revendiquons pas leur invention.
BENU présente des stylos-plume.
Montegrappa présente des stylos-plume.
Scrikss présente des stylos-plume.
Ces catégories situent seulement les stylos de la fiche ; elles ne donnent aucune fréquence ni règle de cancellation. Les images ne sont pas examinées.
Un nom restant n’est pas encore une majorité
Nora fixe d’abord une règle avec une identité et un entier r, initialement zéro. Si r vaut zéro, l’étiquette reçue devient le candidat et r devient un. Sinon, une étiquette identique au candidat augmente r d’un ; une autre le diminue d’un. Quand r atteint zéro, l’ancienne identité n’a plus de statut actif. La majorité recherchée signifie strictement plus de la moitié du nombre total n d’étiquettes, pas simplement la plus grande fréquence parmi plusieurs fréquences égales.
Camille traite A, A, A, B, B. Après les trois A, la feuille porte A avec trois ; les deux B font descendre ce nombre à deux puis un. La suite exacte contient trois A et deux B : A possède bien une majorité stricte. Camille prépare la mention « A, trois occurrences sur cinq », mais ne la tire pas du chiffre un conservé. Nora effectue le compte exact de cette suite avant de remettre cette mention. Un était le résidu de la règle, et non le nombre d’étiquettes A réellement reçues.
Elle traite ensuite une autre suite, B, B, C, C, A. B commence avec deux, les deux C ramènent le compteur à zéro, puis A ouvre une nouvelle candidature avec un. La feuille finale porte encore A et un, sur cinq étiquettes traitées. Cette fois, A n’apparaît qu’une fois ; B et C apparaissent deux fois chacun. Nora retire la proposition qui annoncerait A majoritaire depuis cet état seul. Les deux suites gardent le même candidat, le même résidu et la même longueur, mais l’une autorise la majorité d’A et l’autre la refuse.
Nora explique ce que la mémoire a effectivement fait : chaque diminution a retiré, pour le contrôle, une occurrence du candidat actif et l’étiquette différente qui arrivait. Les occurrences restantes sont toutes de l’identité active. Il n’est pas nécessaire de retrouver matériellement quelle occurrence antérieure a été retirée pour établir cette décomposition ; on peut en choisir une parmi les r occurrences encore représentées. Dans la suite B, B, C, C, A, les deux groupes retirés sont B avec C, puis B avec C. Dans la suite A, A, A, B, B, ils sont deux fois A avec B. Le même résidu ne révèle pas les identités des groupes disparus.
Supposons maintenant qu’une identité X possède une majorité stricte dans la suite complète. Retirer deux étiquettes différentes enlève au plus une occurrence de X. Si X participait au groupe, elle perd un et la longueur totale deux ; sa fréquence reste strictement au-dessus de la moitié de la nouvelle longueur. Si elle n’y participait pas, sa fréquence reste entière tandis que la longueur diminue. Une majorité stricte ne peut donc disparaître pendant ces retraits. À la fin, si elle existait, elle doit être l’unique identité restante. Nora garde cette garantie de candidature, mais n’en inverse pas le sens pour transformer chaque candidat en majorité.
Camille choisit de consulter de nouveau la suite exacte lorsque le résidu ne suffit pas à conclure. Elle compte seulement les occurrences de l’identité candidate, puis compare le résultat à la moitié de n. Sur A, A, A, B, B, elle retrouve trois et remet la majorité ; sur B, B, C, C, A, elle retrouve un et remet l’absence de majorité stricte. Dans ce second cas, elle n’a pas besoin de compter toutes les autres identités : si une majorité existait, la garantie précédente l’aurait gardée comme candidat. Le refus concernant A ferme donc la question pour la suite entière, pas seulement pour cette lettre.
Le résidu donne des bornes, pas le compte perdu
Nora conserve également la longueur n. Chaque groupe retiré contient deux identités différentes ; il peut donc contenir au plus une occurrence du candidat final. Le résidu r lui en donne déjà r, et les groupes retirés peuvent en ajouter au plus la moitié de n moins r. Sa fréquence réelle se trouve donc entre r et la moitié de n plus r. Pour n cinq et r un, cela donne de un à trois. Les deux suites déjà remises atteignent exactement les deux extrémités ; la borne n’est pas seulement un intervalle généreux qui n’aurait aucune réalisation.
Camille remplit une troisième suite, A, B, B, C, A. Le premier B ramène A à zéro ; le second ouvre B, C le ramène à zéro, puis A ouvre le dernier résidu un. A apparaît cette fois deux fois. Elle conserve donc trois réalisations du même état final : une, deux ou trois occurrences réelles d’A. Nora refuse une correction consistant à remplacer systématiquement r par la borne haute trois. Ce remplacement annoncerait une majorité dans la suite présente où A n’a que deux occurrences. La petite mémoire a gardé une possibilité de fréquence, sans choisir laquelle de ces trois réalisations lui appartient.
L’ordre peut aussi changer r quand les fréquences sont conservées. A, A, A, B, C finit sur A avec un ; B, C, A, A, A finit sur A avec trois. Chacune contient trois A, un B et un C. La première retire deux groupes contenant A ; la seconde retire d’abord B avec C et garde ensuite les trois A. Camille transmet la même majorité exacte pour les deux, après vérification, mais garde leurs deux résidus. Les groupes retirés dépendent des rencontres dans l’ordre, tandis que le caractère majoritaire d’A ne dépend pas de cet ordre.
Dans la seconde suite, r trois dépasse déjà la moitié de n cinq. La borne basse suffit alors : la suite contient au moins trois A, donc une majorité stricte. Nora peut la certifier sans deuxième passage pour ce cas. Dans la première, r un ne suffit pas et elle consulte la suite exacte. Elle retire ainsi une consigne trop forte, « tout candidat doit toujours être recompté », en lui substituant deux actions précises : certificat depuis une borne basse déjà supérieure à la moitié, ou vérification lorsque cette borne laisse encore deux réponses possibles. Elle ne fait pas passer le cas de résidu trois pour une preuve que résidu un aurait le même pouvoir.
Si r vaut zéro, tous les groupes restants ont été retirés par deux identités différentes. Chaque identité peut apparaître au plus une fois par groupe, donc au plus n sur deux fois. Une majorité stricte est impossible. Camille traite A, A, B, B : la feuille finit vide, et le compte exact possède deux A et deux B. Elle remet l’absence de majorité, mais ne remet pas l’absence d’étiquettes reçues. La suite de quatre existe toujours ; la mémoire vide certifie ici une limite de fréquence, et non une disparition du dossier.
Deux noms peuvent être fréquents sans atteindre la moitié
Camille reçoit une autre commande : retrouver toutes les identités apparaissant strictement plus d’un tiers des n étiquettes. Une seule place de candidat ne suffit plus. La suite A, A, A, A, B, B, C, C, C contient neuf étiquettes. A apparaît quatre fois et dépasse trois, mais n’atteint pas une majorité stricte. La première règle finit sur C avec un. Camille ne peut pas consulter seulement C puis annoncer que la commande au tiers est fermée : A, qu’elle n’a pas conservé, est précisément l’identité à remettre sous cette nouvelle demande.
Nora ouvre deux places, chacune portant une identité et un compteur positif. Une étiquette déjà présente augmente son compteur ; une étiquette nouvelle prend une place libre avec un. Si les deux places sont occupées par d’autres identités, l’étiquette entrante diminue les deux compteurs d’un. Les compteurs qui atteignent zéro sont retirés avec leur identité. L’étiquette entrante n’est pas ensuite ajoutée à une place libérée par cette même diminution : elle a déjà servi dans le groupe de trois retiré. Une autre occurrence future de son identité pourra ouvrir une place, mais cette occurrence présente ne sert pas deux fois.
La suite précédente remplit d’abord A avec quatre et B avec deux. Le premier C fait passer les compteurs à trois et un ; le deuxième C les fait passer à deux et zéro, retirant B. Le troisième C prend la place libre avec un. Nora conserve donc A deux et C un, avec deux groupes de trois retirés. Elle consulte les fréquences exactes : quatre pour A, trois pour C. A répond strictement à la commande au tiers ; C atteint seulement la frontière et est retiré de la remise des identités recherchées. Sa présence parmi les candidats n’avait pas changé le sens du mot « strictement ».
Chaque diminution retire trois identités distinctes : celles des deux places et celle qui arrivait. Appelons D le nombre de ces groupes. La longueur n vaut la somme des compteurs finaux plus trois fois D. Une identité X perd au plus une occurrence dans chaque groupe, donc sa fréquence exacte est au moins son compteur final c, pris comme zéro si elle n’est pas gardée, et au plus c plus D. Une identité absente de la mémoire a ainsi au plus D occurrences. Comme D ne dépasse pas n sur trois, toute identité dont la fréquence dépasse strictement n sur trois doit occuper une des deux places.
Dans la réalisation de neuf étiquettes, D vaut deux. Le compteur de C vaut un ; sa fréquence ne peut dépasser trois. Nora peut donc déjà exclure C de la commande stricte au tiers, sans lire sa fréquence exacte. Pour A, le compteur deux et D deux donnent une fréquence entre deux et quatre. La frontière trois reste à l’intérieur de ces possibilités. Camille vérifie donc A, retrouve quatre et le remet. Elle ne traite pas tous les candidats comme s’ils demandaient la même action : la borne de C ferme le refus, tandis que la borne d’A impose encore la consultation qui certifie son acceptation.
Une suite A, B, C, A, B, C, A, B, C finit avec deux places vides et D trois. Chacune des trois identités apparaît exactement trois fois. Aucune ne dépasse le tiers de neuf, et la mémoire vide peut certifier ce résultat sans relecture. Si la demande avait été « au moins un tiers », elle manquerait les trois identités. Nora maintient donc le seuil strict auprès de la garantie, puis refuse de transférer cette feuille à la commande inclusive. Ce n’est pas une perte accidentelle causée par la dernière étiquette : retirer des groupes de trois autorise précisément l’effacement d’une identité présente à la frontière.
Camille avait proposé, sur la première arrivée A, B, C, de diminuer les deux compteurs, puis d’inscrire immédiatement C avec un dans la place libérée. Nora retire cette opération de sa feuille. Elle aurait annoncé trois étiquettes traitées, un résidu et un groupe retiré de trois, dont la somme vaut quatre. C apparaîtrait dans le groupe retiré et dans le résidu alors que cette occurrence n’a été reçue qu’une fois. Camille garde la mémoire vide après ces trois arrivées et attend une nouvelle étiquette avant d’utiliser une place libre. La réparation porte sur l’action réellement exécutée, sans ajouter une occurrence au relevé.
Des blocs résumés doivent garder le poids de leur résidu
Dans une branche sur la majorité stricte, Nora reçoit trois blocs traités séparément : dix A, puis trois B, puis trois B. Chaque bloc porte son candidat et son résidu, respectivement A dix, B trois et B trois. Camille souhaite donner une voix à chaque bloc. Deux blocs désignent B contre un A ; ce nouveau vote choisit B. Nora refuse de le remettre comme majorité des seize étiquettes : elles contiennent dix A et six B. La multiplication des blocs B n’a pas multiplié les occurrences qu’ils contiennent. Le résultat d’un vote entre trois résumés répond à une autre question que celle posée sur leurs seize entrées.
Elle réunit plutôt les résidus avec leurs poids : A dix rencontre B trois, retire trois de chaque côté et laisse A sept. Le second B trois fait de même et laisse A quatre. À l’intérieur de chacun des blocs, les groupes éventuellement retirés seraient déjà formés de deux identités différentes ; les retraits de la réunion possèdent la même propriété. Une majorité stricte de toutes les entrées doit donc survivre à l’ensemble de ces retraits. Camille garde A comme candidat global, puis le compte exact dix pour confirmer sa majorité. Le résidu quatre ne devient pas dix sous prétexte que la réunion a retrouvé la bonne identité.
La réunion ne peut pourtant pas être annoncée comme une opération donnant toujours le même résumé, quel que soit son regroupement. Nora prend trois blocs réduits à une étiquette A, B et C, dans cet ordre. Réunir d’abord A et B laisse zéro, puis C laisse C avec un. Réunir d’abord B et C laisse zéro, puis A laisse A avec un. Les trois occurrences complètes n’ont aucune majorité stricte. Les deux résumés sont donc des candidats différents, compatibles avec la garantie conditionnelle, mais pas deux copies d’une même identité conservée. Camille retire la propriété de regroupement indifférent de son contrat de résumé.
Si Camille exige exactement le résumé que la règle aurait donné en lisant la suite d’origine, Nora maintient cet ordre de traitement : A puis B puis C conduit à C. Elle ne présente pas le résumé A issu de l’autre regroupement comme cette exécution. Si la demande consiste seulement à garder toute majorité éventuelle pour une vérification, les deux regroupements restent admissibles, car chacun retire seulement des paires différentes. Nora remet donc deux contrats distincts : reproduire une sortie déterminée par l’ordre, ou conserver une garantie sur une identité majoritaire si elle existe. La faiblesse du second ne doit pas être cachée sous une promesse de reproduction du premier.
Camille complète enfin la branche pondérée avec une vérification de la longueur. Les seize entrées, après la réunion des trois blocs, laissent quatre A et six groupes de deux retirés. Quatre plus douze retrouve seize. La fréquence exacte d’A se trouve entre quatre et dix ; la lecture conservée fournit dix. Une seconde réalisation conservant seulement ce même état et cette même longueur pourrait placer moins d’A dans les groupes disparus, sans modifier le résidu quatre. Nora joint donc les seize entrées exactes à la remise majoritaire, plutôt qu’utiliser la formule de longueur comme si elle retrouvait les identités qu’elle avait précisément permis de retirer.
Les feuilles conservent leurs commandes : majorité stricte, fréquence strictement au-dessus du tiers, ou reproduction d’un résumé dans un ordre donné. Les places de mémoire, les groupes retirés et les vérifications portent sur ces demandes explicites. Camille remet des identités effectivement confirmées ou des refus certifiés par les bornes, sans transformer chaque résidu en fréquence exacte ni chaque disparition de candidat en absence d’étiquette reçue.
Une majorité peut survivre à deux regroupements sans donner la même vérification
Nora remplit enfin trois blocs dans un ordre fixé : trois A, un B, un C. Réunir les deux premiers laisse A deux, puis ajouter le troisième laisse A un. Réunir d’abord les deux derniers laisse zéro, puis joindre le premier laisse A trois. Les cinq entrées n’ont pas changé d’ordre à l’intérieur de leurs blocs, et les deux chemins gardent A, véritable majorité. Leur résidu change pourtant la remise disponible sans consultation : A trois dépasse la moitié de cinq et certifie directement la majorité ; A un laisse seulement une fréquence comprise entre un et trois, qui ne la certifie pas. Camille retient le regroupement qui annule B avec C avant la réunion d’A, puis remet le certificat depuis la borne basse trois. Elle n’ajoute pas deux au résumé un de l’autre chemin pour le faire ressembler au sien : les groupes de cancellation choisis sont différents. Cette possibilité n’accorde aucun certificat automatique à tous les regroupements donnant la même identité.