La solution
Capturés par le grand méchant logicien qui veut les enrôler dans sa secte, les logiciens, en nombre impair, sont placés en cercle tournés vers le centre. En procédant à pile ou face, le méchant logicien dessine une croix, noire ou rouge, sur le front de chaque logicien qui voit les croix dessinées sur le front des autres, mais ignore celle qu’il porte. Aucune communication n’est permise entre les logiciens une fois les croix dessinées. Un vote est organisé et chacun indique s’il pense que le nombre total de croix rouges est pair ou impair, l’abstention n’est pas permise. Le grand méchant logicien comptabilise les réponses et considère la réponse majoritaire. Si celle-ci est correcte, les logiciens sont libérés. Chaque logicien se dit : « Puisque la parité du nombre total de croix rouges dépend de celle que j’ai sur le front, qui a été tirée au hasard, je ne peux rien faire de mieux que voter au hasard. Il en est de même de tous les autres logiciens et donc globalement nous ne pouvons rien espérer de mieux qu’être libéré une fois sur deux ».
En fait, il existe une méthode de vote que les logiciens peuvent deviner et appliquer et qui leur permettra d’être libérés dans bien plus de la moitié des cas. Imaginons que tous les logiciens adoptent la règle suivante.
Si je vois devant moi autant de croix noires que de croix rouges, je vote en faisant l’hypothèse que j’ai sur le front une croix rouge. Sinon, je suppose que j’ai sur le front une croix de la couleur majoritairement présente devant moi et je vote conformément à ce qu’il résulte de cette hypothèse.
Pour analyser l’effet d’une telle méthode, distinguons trois cas.
Cas 1 : Si l’écart entre le nombre de croix rouges et de croix noires est plus grand que 1, alors les logiciens, en appliquant cette règle, font en majorité une hypothèse correcte et le vote majoritaire est correct, ils sont libérés.
Cas 2 : Si l’écart entre le nombre de croix rouges et le nombre de croix noires est égal à 1 en faveur des rouges alors, d’une part, tous les porteurs de croix noires (qui voient plus de rouges que de noires) votent faussement puisqu’ils font l’hypothèse fausse qu’ils portent une croix rouge, et, d’autre part, tous les porteurs de croix rouges, qui voient autant de rouges que de noires, votent correctement (puisque, dans un tel cas, ils font l’hypothèse qu’ils portent une croix rouge). Les rouges étant majoritaires, le vote est donc majoritairement correct et les logiciens sont libérés.
Cas 3 : Si l’écart entre le nombre de croix rouges et le nombre de croix noires est de 1 en faveur des noires alors tous les porteurs de croix rouges, qui voient plus de noires que de rouges, votent faussement, ainsi que tous les porteurs de croix noires qui voient autant de rouges que de noires. Le vote est donc erroné à 100 %. C’est le seul cas où le vote est erroné. Les cas 2 et 3 se compensent et donc, dans la majorité des situations (grâce au cas 1), les votes des logiciens sont corrects.
Pour évaluer plus précisément le nombre de cas où le vote sera malheureux, considérons le nombre de logiciens \(m\) qui peut s’écrire \(m = 2n+1,\) puisque \(m\) est impair. Le nombre de cas où le vote est incorrect est le nombre de cas où il y a \(n\) croix rouges et \(n + 1\) croix noires. Ce nombre est
\[\frac {(2n+1)!}{n!(n+1)!},\]
soit le nombre de façons de choisir \(n\) éléments parmi \(2n + 1.\) Il y a deux couleurs possibles pour chacun des \(m\) logiciens, donc \(2m\) cas possibles au total. En analysant pour quelques valeurs de \(m,\) on dresse le tableau suivant.
Plus le nombre de logiciens est grand, meilleure est la méthode et on peut montrer que lorsque \(m\) tend vers l’infini, le rapport du nombre de cas défavorables sur le nombre total de cas tend vers zéro.
Les logiciens peuvent donc espérer être libérés plus d’une fois sur deux, s’ils tiennent tous ce raisonnement.
On peut critiquer cette solution, s’ils n’ont pas pu s’entendre avant l’épreuve, les logiciens n’ont pas de raison d’adopter tous cette stratégie. Il est plus raisonnable de penser que près de la moitié des logiciens va adopter la stratégie A :
Si je vois devant moi autant de croix noires que de croix rouges, je vote en faisant l’hypothèse que j’ai sur le front une croix rouge. Sinon je suppose que j’ai sur le front une croix de la couleur majoritairement présente devant moi et je vote conformément à cette hypothèse.
et que l’autre moitié va adopter la stratégie symétrique B:
Si je vois devant moi autant de croix noires que de croix rouges, je vote en faisant l’hypothèse que j’ai sur le front une croix noire. Sinon je suppose que j’ai sur le front une croix de la couleur majoritairement présente devant moi et je vote conformément à cette hypothèse.
Dans cette éventualité, il n’y a rien de changé si le cas 1 se présente. Cependant, dans le cas 2, il suffit qu’un seul porteur de croix rouge joue B plutôt que A pour que le vote majoritaire soit erroné. Sauf exception, le cas 2 sera défavorable. Le cas 3 est de même défavorable sauf hasard exceptionnel (1 fois sur \(2^n).\) Par rapport à notre calcul précédent, il faut maintenant doubler le nombre de cas défavorables. Il n’est plus aussi clair que la méthode soit intéressante. Un petit calcul montre cependant que si le nombre de logiciens est supérieur à 7, alors la stratégie décrite est favorable aux logiciens.
