Caméléons tricolores

Connaissez-vous le livre suivant de Peter Winkler ?¹Il est paru en 2007 chez Routledge. L’énigme provient de la page 22.

Il est rempli d’énigmes, parfois très subtiles, pour amoureux des mathématiques. Voici l’une d’entre elles :

Convenablement guidé par des questions, même un collégien peut arriver à résoudre l’énigme. On peut lui faire découvrir en même temps la notion d’« invariant », qui est l’une des plus importantes des mathématiques modernes :

— Partons de nos 20,18 et 16 caméléons des trois couleurs. Il y a deux cas : soit il est possible d’organiser leurs rencontres pour arriver à une situation où tous les caméléons ont la même couleur, soit cela n’est pas possible. Es-tu d’accord ?

— Oui.

— Je prétends que si à un moment donné il y a le même nombre de caméléons rouges et verts, alors ils peuvent tous devenir bleus. Par exemple, s’il y a trois rouges et trois verts.

— C’est vrai, on fait se rencontrer trois fois de suite un rouge et un vert, ensuite ils seront tous bleus … Pour qu’à la fin ils aient tous la même couleur, il suffit donc qu’à un moment donné il y ait le même nombre de caméléons de deux couleurs différentes.

— Très bien. Cela peut laisser penser qu’il est bon de regarder les différences des nombres de caméléons de couleurs différentes : le nombre de rouges moins le nombre de bleus, celui de verts moins celui de rouges, et ainsi de suite. Ce qu’on veut, c’est amener l’une de ces différences à valoir zéro, d’accord ?

— C’est bien ça.

— Alors on va regarder ce qui se passe avec une telle différence à chaque rencontre de caméléons de couleurs différentes. Peux-tu le dire ?

— … À chaque rencontre, deux des nombres de caméléons diminuent de 1 et le troisième augmente de 2. Donc une différence donnée, soit reste inchangée, soit elle augmente ou diminue de 3.

— Excellent ! Et qu’est-ce qui ne change pas dans un nombre lorsqu’on le modifie de cette manière, en lui rajoutant ou en lui soustrayant 3 ?

— … Je ne sais pas …

— Eh bien, c’est le reste de sa division par 3 ! Tu le vois ?

— … C’est vrai.

— Donc, si on regarde les différences des nombres de caméléons de couleurs différentes, leurs restes de la division par 3 ne changent pas au gré des rencontres, d’accord ?

— C’est bien ça.

— Et que valent ces différences au début ?

— Comme on avait les nombres 20,18,16, les différences sont ±2,±4. Donc les restes valent 1 ou 2.

— Je prétends alors qu’il n’est pas possible d’arriver à une situation où tous les caméléons ont la même couleur. Pourquoi ?

— … ah oui, je vois. Si c’était le cas, il y aurait une différence nulle, donc le reste de sa division par 3 vaudrait 0. Mais au départ il n’y a pas de reste nul, et comme les restes demeurent inchangés pendant les rencontres, on ne peut pas non plus en avoir à la fin …

— Excellent ! Eh bien, un nombre qui ne change pas lors d’une suite de transformations d’un type donné (par exemple, les changements des nombres de caméléons dus à leurs rencontres) est appelé un « invariant ». Dans les mathématiques du XXe siècle sont apparues d’innombrables situations où il a été nécessaire de construire des invariants. Ils permettent par exemple de montrer de la même manière que certains buts sont inaccessibles à partir de certaines situations de départ.

Ce dialogue pourrait continuer, afin d’aider notre jeune interlocuteur à comprendre dans quels cas on peut passer d’une configuration donnée de caméléons à une autre par une suite de rencontres. Retour ligne automatique
Par exemple, peut-on passer de la configuration précédente (20,18,16) à une autre où il y a 24 caméléons rouges, 13 bleus et 17 verts ?

Si vous avez aimé cette énigme, en voici une autre d’un esprit différent, mais portant toujours sur des transformations de configurations, provenant de la même page du livre de Winkler ² J’ai un peu modifié les termes de l’énoncé, en gardant son sens mathématique. :