Si on essaie de jouer plusieurs fois en faisant varier les nombres de caméléons de chaque couleur au départ, on se rend compte que 3 situations peuvent se produire :

Nous allons essayer de comprendre ce phénomène en identifiant un invariant du jeu, c'est-à-dire une caractéristique de l'état du jeu qui ne change jamais quels que soient les choix du joueur.

Vers un invariant

Pour cela, analysons ce qui se passe lors d'une évolution d'un changement de couleurs : par exemple lorsqu'un caméléon bleu et un rouge se rencontrent sur un même arbre. Ils deviennent alors tous les deux verts, donc le nombre de caméléons bleus a baissé d'une unité, le nombre de caméléons rouges a aussi baissé d'une unité, tandis que le nombre de caméléons verts a augmenté de 2.

bilan d'un changement de couleurs : bleu -1, rouge -1, vert +2.

Clairement le nombre de caméléons d'une couleur donnée n'est pas invariant, mais voyons si l'on regarde la différence entre les nombres de caméléons de 2 couleurs différentes. La différence entre le nombre de bleus et le nombre de rouges n'a pas changé. Mais la différence entre le nombre de verts et le nombre de rouges a augmenté de 3. De même la différence entre le nombre de verts et le nombre de bleus a aussi augmenté de 3.

La différence entre les nombres de caméléons de deux couleurs différentes n'est pas non plus invariante. Mais lorsqu'elle change, elle varie de 3 d'un coup. Nous pouvons exploiter cela pour trouver des propriétés invariantes. Par exemple le fait que la différence entre le nombre de caméléons rouges et le nombre de caméléons verts soit un multiple de 3 : soit cette propriété est vraie tout au long du jeu, soit elle n'est jamais vraie.

Une condition nécessaire pour rendre tous les caméléons bleus

En particulier, si à la fin du jeu on arrive à rendre tous les caméléons bleus, le nombre de verts est égal au nombre de rouges (les deux valent zéro), et donc la différence qui est aussi zéro est un multiple de 3.

Nous voilà avec un résultat important :

Pour qu'il soit possible de rendre tous les caméléons bleus, il est nécessaire que la différence entre les nombres de caméléons verts et de caméléons rouges soit un multiple de 3.

Par exemple, dans la configuration initiale 3 bleus, 4 rouges et 5 verts, la différence entre le nombre de verts et le nombre de rouges vaut 1, ce n'est pas un multiple de 3 donc il est impossible de rendre tous les caméléons bleus.

Une condition presque suffisante ?

Réciproquement, il est assez facile de voir que la condition « la différence entre le nombre de verts et le nombre de rouges est un multiple de 3 » est presque une condition suffisante pour qu'il soit possible de rendre tous les caméléons bleus. En effet, si cette condition est satisfaite on peut adopter la stratégie suivante : commencer par faire autant de rencontres rouge-vert que possible pour faire disparaître une des deux couleurs (celle qui était la moins représentée au départ). On se retrouve alors avec seulement deux couleurs : des bleus et, disons, des verts. De plus on sait que le nombre de verts est un multiple de 3 (car le nombre de rouges est zéro, et la différence entre le nombre de verts et le nombre de rouges doit toujours rester un multiple de 3). Voilà alors comment faire baisser le nombre de verts de 3 unités en 2 étapes : faire une rencontre vert-bleu, qui élimine déjà 1 vert et crée 2 rouges, puis faire 2 rencontres vert-rouge qui éliminent les 2 rouges et 2 verts supplémentaires. En répétant cette manœuvre autant de fois que nécessaire on finit par éliminer ainsi tous les verts.

Avec le raisonnement ci-dessus on a bien l'impression que la condition donnée est également suffisante pour rendre tous les caméléons bleus. Mais que dire de la condition initiale 0 caméléon bleu, 0 caméléon rouge, 12 caméléons verts ? Dans ce cas la différence entre les verts et les rouges est bien un multiple de 3, pourtant il est évidemment impossible de créer le moindre caméléon bleu. Ce qui se passe, c'est que la deuxième partie de la stratégie décrite juste avant n'est possible à appliquer que si, au moment où l'on a éliminé une des deux couleurs rouge ou vert, il reste au moins un bleu. Pour être assuré que cela pourra être le cas, on peut mettre une hypothèse supplémentaire : on suppose de plus qu'au départ il y a au moins 2 couleurs présentes.

Conclusion

Bien sûr tout ce qui a été dit ci-dessus reste valable en permutant les couleurs. Ainsi, en supposant qu'il y a au moins deux couleurs différentes au départ, il est possible de rendre tous les caméléons rouges si et seulement si la différence entre les bleus et les verts est un multiple de 3.

On peut maintenant analyser les différentes conditions initiales proposées dans le jeu.

Revenir au jeu des caméléons.