Connaissez-vous le livre suivant de Peter Winkler ?3Il 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 :
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 ±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 4 J’ai un peu modifié les termes de l’énoncé, en gardant son sens mathématique. :
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.
ÉCRIT PAR
Patrick Popescu-Pampu
Professeur - Université de Lille
