La réponse du jeudi (6) : le jeu des +1
Publié le 16/10/2014

Vous pouvez retrouver cette question au format pdf.

Question du jeudi #6 : Six nombres entiers sont inscrits dans les secteurs d'un disque. À chaque étape, vous pouvez ajouter 1 aux nombres inscrits dans deux secteurs adjacents. Si l'on part de la situation où les nombres sont 1, 0, 1, 0, 0, 0, pouvez-vous parvenir à une situation où les six nombres sont égaux ?


En jouant un peu avec le jeu, on se convainc relativemement facilement qu'il est impossible d'égaliser les nombres en partant de la configuration 1, 0, 1, 0, 0, 0. Comment démontrer une telle impossibilité ?

Une idée fertile est de trouver un invariant, c'est-à-dire un objet mathématique que l'on peut déterminer à partir d'une configuration (un nombre que l'on peut calculer, par exemple) et dont on peut démontrer qu'il ne change pas lorsqu'on passe d'une étape à la suivante.

Ici, passer d'une étape à l'autre se fait en ajoutant 1 à deux secteurs consécutifs. On peut donc trouver un invariant en considérant la somme alternée des nombres en présence, c'est-à-dire le résultat de l'opération $n_1 - n_2 + n_3 - n_4 + n_5 - n_6$, où $n_i$ est le nombre qui apparaît dans le $i$-ème secteur. À chaque étape, on remplace une paire $(n_{i}, n_{i+1})$ par la paire $(n_i+1, n_{i+1}+1)$ (ou $(n_6, n_1)$ par $(n_6+1,n_1+1)$. Cela ne change pas la valeur de la somme alternée.

Or, dans la configuration initiale, la somme alternée vaut $1-0+1-0+0-0 = 2$ alors que si tous les nombres sont égaux, la somme alternée vaut $0$ : il est donc impossible d'égaliser tous les nombres.

Réciproquement, on voit relativement aisément que si la configuration initiale a une somme alternée nulle, il est possible d'égaliser tous les nombres.

 
 
 
 
 
Dernières publications