CultureMath

Vous pouvez retrouver cette question au format pdf.

Question du jeudi #7 : On place des pions sur un damier de taille $n \times m$. À quelle condition sur $n$ et $m$ est-il possible de les réarranger de telle sorte que chaque pion atterrisse sur une case adjacente de celle qu'il occupait précédemment ?

La réponse est qu'un tel déplacement est possible si et seulement si le damier a un nombre pair de cases (c'est-à-dire si $n$ ou $m$ est pair).

Pour montrer que cela est alors possible, remarquons qu'échanger les deux pions répond à la question sur le damier de taille $2 \times 1$.

Si le nombre de lignes ou le nombre de colonnes est pair, on peut alors découper le damier en « dominos » $2 \times 1$. En appliquant notre technique précédente, c'est-à-dire en échangeant les deux pions de chaque domino, on obtient alors un déplacement répondant aux contraintes. (Remarquons qu'il y a beaucoup d'autres façons de faire...)

Réciproquement, montrons qu'un tel déplacement est impossible pour un nombre impair de cases. Encore une fois, il y a de multiples preuves possibles mais nous n'en exposerons qu'une : tel un vrai damier, supposons que notre damier $n \times$ soit colorié en noir et blanc, de telle sorte que deux cases de la même couleur ne soient jamais adjacentes.

On voit alors que, tel le mouvement d'un cavalier sur un vrai échiquier, chaque pion devrait changer de couleur de case en se déplaçant : passer d'une case noire à une case blanche, ou réciproquement.

Ainsi, si une permutation envoyant tout pion sur une case adjacente était possible, chaque case blanche serait associée à une case noire, et réciproquement. Mais cela est impossible, puisqu'il n'y a pas autant de cases noires que de cases blanches ! (S'il y en avait autant, le nombre total de cases est pair...)