Caméléons tricolores

Le 12 septembre 2019  - Ecrit par  Patrick Popescu-Pampu Voir les commentaires

Connaissez-vous le livre suivant de Peter Winkler [1] ?

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

Une colonie de caméléons contient au départ $20$ caméléons rouges, $18$ bleus et $16$ verts. Lorsque deux caméléons de couleurs différentes se rencontrent, chacun d’entre eux acquiert la couleur restante. Est-il possible qu’après un certain temps, tous les caméléons aient la même couleur ?

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 $\pm 2, \pm 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.
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 [2] :

Des enfants sont disposés en cercle, chacun d’entre eux ayant un sac de bonbons. Le professeur donne un bonbon à chaque enfant qui en a un nombre impair, puis chaque enfant donne la moitié de ses bonbons à son voisin de gauche. Ces deux étapes sont répétées jusqu’à ce qu’elles ne produisent plus de changement dans les nombres de bonbons. Montrer qu’une telle stabilisation a effectivement lieu après un nombre fini d’étapes, et qu’alors tous les enfants auront le même nombre de bonbons.

Article édité par Laurent Bartholdi

Notes

[1Il est paru en 2007 chez Routledge. L’énigme provient de la page 22.

[2J’ai un peu modifié les termes de l’énoncé, en gardant son sens mathématique.

Partager cet article

Pour citer cet article :

Patrick Popescu-Pampu — «Caméléons tricolores» — Images des Mathématiques, CNRS, 2019

Crédits image :

Image à la une - L’image du logo est tirée de Wikimedia Commons.
img_20946 - Source : Wikimedia Commons

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Dossiers

Cet article fait partie du dossier «Recensions» voir le dossier