Parmi les énigmes mathématiques ludiques que l’on retrouve régulièrement, les problèmes de pesée forment une catégorie assez classique. Typiquement, on vous demande de trouver quelle pièce d’or est fausse (car plus légère que les autres) parmi un ensemble de pièces visuellement identiques, en utilisant uniquement une balance à fléau qui vous permet de comparer le poids de deux tas de pièces, le tout en opérant le moins de pesées possibles.

Disons que vous disposez d’un tas de 32 pièces dont vous savez que l’une est fausse. Vous pouvez utiliser la méthode suivante : mettez une pièce prise au hasard dans chaque plateau de la balance. Si le fléau s’incline, la pièce qui s’élève est plus légère que l’autre et c’est elle la fausse pièce. Sinon, choisissez une des deux pièces comme étalon en mettant l’autre de côté, et comparez-la aux 30 pièces restantes. Vous trouverez la fausse pièce au plus en 31 pesées au total.

Mais on peut faire bien mieux. Divisez vos 32 pièces en deux tas de 16, que vous placez sur les plateaux de la balance. L’un des tas s’élèvera ; c’est celui qui contient la fausse pièce. Divisez-le en deux tas de 8 pièces et recommencez l’opération ; vous diviserez le tas de 8 pièces le plus léger en deux tas de 4, etc. Au bout de 5 pesées au total, vous aurez comparé deux pièces dont l’une est la fausse pièce, avec un grand gain de temps.

Il existe de nombreuses variantes plus difficiles de cette énigme. On peut par exemple spécifier que la fausse pièce est soit plus légère, soit plus lourde que les autres, ou bien qu’il y a deux fausses pièces, etc. Votre stratégie sera différente à chaque fois.

Comme il arrive plus souvent qu’on ne croit, ce jeu mathématique offre une application tout ce qu’il y a de plus sérieuse dans la vie réelle : en l’occurrence, il s’agit d’optimiser l’efficacité des tests COVID.

Chargée de la santé publique de votre pays, vous voulez tester massivement la population afin d’identifier les cas positifs. Mais les tests prennent du temps, les réactifs ne sont pas disponibles à l’infini, et vous avez besoin de résultats rapides sans embouteiller les laboratoires.

Sans connaître précisément le nombre de cas positifs – que vous cherchez justement à identifier – vous savez tout de même que ce nombre est réduit par rapport à la population générale. Pouvez-vous, de ce fait, déterminer les cas positifs sans avoir à tester individuellement chaque habitant ?

Il est possible de le faire en identifiant au hasard des groupes de personnes dont vous mélangez une partie des échantillons (sanguins par exemple) ; vous analysez ensuite le résultat du mélange pour chaque groupe. Si le résultat est positif, cela implique qu’au moins une personne du groupe est positive ; vous pouvez la ou les trouver en re-testant tour à tour l’échantillon restant de chaque personne du groupe. Si le résultat du groupe est négatif, en revanche, vous avez éliminé d’un coup toute les personnes qu’il contient. Si la prévalence du virus est assez faible et la taille des groupes bien choisie, vous économiserez des tests, car vous n’utiliserez le plus souvent qu’un test par groupe (la majorité des groupes étant négatifs), quitte à re-tester individuellement chaque personne d’un groupe positif (ce qui ne vous coûtera qu’un test de plus que la méthode exhaustive). Il faut cependant bien choisir la taille des groupes. En effet, si vous prenez des groupes trop grands, la probabilité qu’une personne de chaque groupe soit positive augmente, et vous pourriez vous retrouver à re-tester tout le monde. À l’inverse, si vos groupes sont trop petits, vous gagnez de moins en moins à cette stratégie car vous testez de nombreux groupes. Il existe des méthodes permettant de trouver la meilleure taille de groupe à utiliser en fonction de la prévalence attendue de la maladie. Il faut également prendre en compte les limites physiques de sensibilité dues à l’appareillage de tests, qui empêche de constituer des groupes trop grands – dans lesquels un unique échantillon positif serait trop dilué.

Cette méthode de test de groupe est couramment utilisée pour plusieurs maladies dont la COVID, et l’on pourrait penser qu’il n’y a pas grand-chose de neuf à découvrir à ce sujet. Mais il se trouve que récemment, une équipe israélienne a proposé une méthode encore plus efficace, évitant de devoir re-tester toutes les personnes d’un groupe testé positif.

L’idée est ici de répartir les échantillons d’une personne non pas dans un groupe unique, mais dans plusieurs, en s’arrangeant pour chaque personne soit représentée dans un ensemble unique de groupes. On teste ensuite tous les groupes. Si chacun des groupes contenant un échantillon d’une même personne est testé positif, il y a une très forte probabilité, que l’on peut déterminer, que cette personne soit positive. Si cette probabilité est assez forte, on considérera tout simplement la personne comme positive (ce qui vaut bien mieux que de négliger une personne réellement positive).

Cette stratégie implique de constituer plus de groupes puisque chaque personne doit appartenir à plusieurs groupes, mais elle évite de re-tester les membres d’un groupe positif. Dans un exemple présenté par les auteurs, l’équipe a réparti les échantillons de 384 personnes (préalablement testées individuellement) en 48 groupes de 48 ; les échantillons de chaque personnes apparaissent dans 6 groupes, et chaque personne peut être identifiée sans ambiguïté par l’ensemble de groupes où apparaissent ses échantillons. Les auteurs ont ensuite testé ces groupes, en répétant l’expérience avec plusieurs populations de personnes dont le statut était connu. Quand 4 personnes ou moins parmi les 384 étaient porteuses du virus, elles ont toutes été identifiées directement par le test des 48 groupes, sans introduire de faux positif. Dans le cas où la prévalence du virus est autour de 1%, on obtient donc une identification précise des porteurs du virus avec 8 fois moins de tests qu’une méthode de test individuelle, et deux fois moins que la meilleure méthode de test groupé connue. De plus, les limitations physiques de la taille des groupes liées à la sensibilité des appareils est en quelque sorte « gommée » du fait que chaque échantillon est testé plusieurs fois.

Voilà un beau résultat, qui arrive à point. Il est par ailleurs assez fascinant de constater que cette méthode a de nombreux points communs avec les protocoles de détection d’erreur utilisés en informatique et en télécommunications, lesquels reposent sur des techniques mathématiques très avancées.

Au mathématicien du dimanche que cela intéresse, ne reste plus qu’à s’en inspirer pour trouver de meilleures solutions aux vieux problèmes de pesée dont on pouvait penser tout savoir !

Yannick Cras
Le nombre imaginaire