Imaginez un échiquier infini où les pièces peuvent voyager où elles le souhaitent, limitées uniquement par leurs règles de mouvement. Si un cavalier et un roi partent de la même case et font la course pour atteindre une case d’arrivée lointaine, lequel arrivera en premier ? Peut-on quantifier le rapport entre les temps qu’ils mettent à parcourir cette distance ? Ces questions mathématiques intrigantes offrent un aperçu fascinant sur la géométrie des échecs et de la théorie des nombres.
Le roi et le cavalier
Le roi se déplace d’une seule case dans n’importe quelle direction, formant une étoile à 8 branches autour de sa position actuelle. Mathématiquement, son ensemble de mouvements possibles à partir de l’origine est :
\[R = \{(1, 0), (−1, 0), (0, 1), (0,−1), (1, 1), (1,−1), (−1, 1), (−1,−1)\},\]
que l’on notera de manière succinte :
\[R = \{(\pm1, 0), (0,\pm1), (\pm1,\pm1)\}.\]
Le cavalier, en revanche, effectue ses mouvements emblématiques en forme de L : deux cases dans une direction et une perpendiculaire dans l’autre. Son ensemble de déplacements, au nombre de huit, est donc
\[C = \{(\pm1,\pm2), (\pm2,\pm1)\}.\]
Une question naturelle se pose alors : le cavalier peut-il atteindre toutes les cases de l’échiquier infini ?
Colorions l’échiquier comme d’ordinaire: une case \((x, y)\) est blanche si \(x+y\) est pair et noire si \(x + y\) est impair. Un coup de cavalier est toujours de la forme \((\pm1,\pm2)\) ou \(\pm2,\pm1).\) Dans les deux cas, la variation de la somme des coordonnées est de \(\pm(1 + 2) = \pm3\) ou de \(\pm(2 − 1) = \pm1.\) La parité de \(x + y\) change donc à chaque coup. Contrairement à certaines autres pièces, comme le fou, le cavalier n’est pas limité à une seule couleur de cases.
À partir de (0, 0), le cavalier peut se déplacer en (1, 2). À partir de là, un coup (−2,−1) l’amène en (−1, 1), puis un coup (2,−1) le conduit en (1, 0). Par symétrie des déplacements, le cavalier peut aussi atteindre (−1, 0), (0, 1) et (0,−1).
Une fois que le cavalier sait atteindre les cases \((\pm1, 0)\) et \((0,\pm1),\) il peut répéter ces déplacements élémentaires autant de fois que nécessaire. En avançant pas à pas horizontalement et verticalement, il peut ainsi rejoindre n’importe quelle case \((x, y)\) de l’échiquier infini. Ces déplacements suffisent à garantir que le cavalier peut aller partout sur l’échiquier infini.
Mais emprunter ces petits pas n’est pas toujours la stratégie la plus efficace. La vraie question devient alors : quel est le nombre minimal de coups qu’il faut au cavalier pour atteindre une case donnée ?
Vitesse sur l’échiquier
Les mouvements du roi et du cavalier possèdent des symétries : à partir d’une suite de coups qui mène à une case \((x,y),\) on peut changer le signe des déplacements ou échanger les axes horizontal et vertical pour obtenir des suites de coups menant aux cases \((\pm x,\pm y)\) et \((\pm y,\pm x).\) Autrement dit, toutes les directions sur l’échiquier se comportent de la même façon. Il suffit donc d’étudier les cases avec \(x \geq 0, y \geq 0\) et \(0 \leq y \leq x,\) puis d’en déduire les autres cas par symétrie.
Nous notons \(A(x, y)\) le nombre minimal de coups qu’une pièce \(A\) met pour atteindre la case \((x, y)\) à partir de l’origine. Pour le roi \(R,\) le calcul est simple. Pour aller de (0, 0) à \((x,y)\) avec \(x \geq 0\) et \(0\leq y \leq x,\) le roi effectue d’abord \(y\) coups diagonaux (1, 1), ce qui l’amène en \((y, y),\) puis \(x − y\) coups horizontaux pour atteindre \((x,y).\) Le nombre total de coups est donc \(R(x, y) = x.\)
En utilisant la symétrie pour les autres directions, on obtient la formule générale
\[R(x, y) = \max(|x|, |y|).\]
Pour le cavalier \(C,\) le calcul est plus délicat. En se limitant au premier quadrant et en notant \(m = y/x,\) la pente du point \((x,y),\) on distingue deux régimes selon la valeur de \(m.\) Lorsque la pente est petite \((0 \leq m \leq 1/2 ),\) le cavalier progresse essentiellement horizontalement, et le nombre minimal de coups est proportionnel à \(x.\) Lorsque la pente est plus grande \((1/2 m \leq 1),\) le cavalier avance de manière plus équilibrée horizontalement et verticalement, et le nombre de coups dépend de \(x + y.\) Plus précisément, pour des points éloignés de l’origine, on a l’approximation
\[ C(x,y) \approx \displaystyle \Biggl \{ \begin{array}{l l l} \displaystyle \frac{x}{2}, &\text { si } & 0 \leq m < \frac{1}{2}, \\ \displaystyle \frac{x+y}{3}, &\text { si } & \frac{1}{2}< m \leq 1. \end{array} \]
La Figure 3 illustre ces deux comportements. Les détails du raisonnement sont présentés dans l’encadré ci-dessous.
Détails techniques : calcul de \(C(x, y)\) pour le cavalier.
Cas \(0 \leq m \leq 1/2.\)
On pose \(x’\) égal à la partie entière de \(x/2 : x’ = x/2\) si \(x\) est pair, et \((x−1)/2\) si \(x\) est impair. En effectuant \(x’\) coups de type (2,1) ou (2,−1), le cavalier avance \(2x’\) cases vers la droite. Après ces \(2x’\) coups, il se trouve sur une case \((X, Y)\) telle que \(x−X \in \{0, 1\}.\)
Chaque coup modifie aussi la coordonnée verticale de +1 ou −1. Comme on suppose \(y \leq x/2,\) on peut commencer par effectuer y coups de type (2, 1), puis alterner les coups (2, 1) et (2,−1) de façon à compenser les variations verticales. On obtient ainsi \((X, Y)\) avec \(y−Y \in \{−1,0,1\}.\) Ainsi, le cavalier arrive dans le voisinage immédiat de \((x, y).\) Comme on peut le voir sur la Figure 2, à partir d’une telle position, il suffit d’ajouter au plus trois coups pour atteindre exactement \((x,y).\) On obtient donc
\[C (x, y) \approx \displaystyle \frac{x}{2}.\]
Cas \(1/2 < m \leq 1.\)
Lorsque la pente est plus grande, on combine deux types de coups: (2, 1) et (1, 2). Supposons que l’on effectue u coups du premier type et \(v\) du second. Le déplacement total est alors
\[(2u + v, u + 2v).\]
Pour se rapprocher de \((x, y),\) on cherche à résoudre \(2u + v = x, u + 2v = y.\) Ce système a pour solution
\[u= \displaystyle \frac{2x-y}{3}, v= \frac{-x+2y}{3}.\]
La condition \(1/2 < m \leq 1\) assure que \(u\) et \(v\) sont positifs.
En général, ces valeurs ne sont pas entières. On note alors \(U\) et \(V\) leurs parties entières, de sorte que
\[0 \leq u − U< 1, 0 \leq v − V < 1.\]
Après \(U\) coups de type (2, 1) et \(V\) coups de type (1, 2), le cavalier se trouve en une case \((X,Y)\) vérifiant \(X = 2U +V, Y = U +2V.\) En comparant avec les égalités précédentes, on obtient
\[ \begin{array}{l l l}x − X &=& 2(u − U) + (v − V) < 3, \\y − Y &=& (u − U) + 2(v − V) < 3. \end{array}\]
Le cavalier atteint ainsi une case voisine de \((x, y).\) Comme précédemment, quelques coups supplémentaires (au plus quatre) suffisent pour atteindre exactement la case voulue. Le nombre total de coups est donc de l’ordre de
\[C(x,y) \approx u +v = \displaystyle \frac{x+y}{3} = \frac{x}{3}(1+m).\]
Une question naturelle se pose : quelle est la vitesse moyenne de ces pièces sur une grande région ? En analysant les déplacements du cavalier sur un échiquier \(N \times N\) lorsque \(N\) tend vers l’infini, nous découvrons que le cavalier est, en moyenne, 24/13 (soit environ 1,85) fois plus rapide que le roi. Bien que la vitesse ne soit pas doublée, cela reste un avantage considérable.
Calcul de la vitesse
Afin de comparer quantitativement la rapidité du cavalier et du roi, nous définissons la vitesse moyenne relative du cavalier par rapport au roi comme la moyenne du rapport
\[\displaystyle \frac{C(x,y)} {R(x,y)}\]
sur toutes les cases d’un échiquier carré \(−N \leq x, y \leq N,\) puis nous faisons tendre \(N\) vers l’infini. Autrement dit, on choisit une case « au hasard » de plus en plus loin de l’origine et on compare le nombre minimal de coups nécessaires pour le cavalier et pour le roi.
Grâce aux symétries des mouvements du roi et du cavalier évoquées précédemment, ce calcul peut être ramené a la moitié du premier quadrant de l’échiquier, soit la région \(x, y \geq 0\) et \(0 \leq y \leq x.\) D’après les estimations établies plus haut, le rapport \(C(x, y)/R(x,y)\) dépend essentiellement de la pente \(m = y/x\) : pour \(0 \leq m \leq 1,\) on a l’approximation
\[\displaystyle \frac{C(x,y)} {R(x,y)} \approx \Biggl \{ \begin {array} {l r} \displaystyle \frac{1}{2}, & 0 \leq m < \displaystyle \frac{1}{2}, \\ \displaystyle \frac{1+m}{3} & \displaystyle \frac{1}{2} < m \leq 1. \end{array}\]
Détails techniques : calcul de la moyenne
Dans le premier quadrant, on pose \(m = y/x \in [0, 1].\) D’après les estimations précédentes, le rapport \(C(x, y)/R(x, y)\) est bien approché par une fonction \(f (m)\) définie sur l’intervalle [0, 1].
La vitesse moyenne cherchée correspond alors à la moyenne de \(f\) sur [0, 1], c’est-à-dire
\[\displaystyle \int_0^1 f(m) dm\]
Géométriquement, cette intégrale représente l’aire sous le graphe de \(f.\) Comme l’illustre la Figure 4, cette aire se calcule simplement en décomposant la région hachurée en deux carrés et un triangle. On obtient ainsi
\[\displaystyle \int_0^{1/2} \frac{1}{2} dm + \int_{1/2}^1 \frac{1+m}{3}dm = \frac{13}{24}.\]
Figure 4 – Graphe de la fonction f(m) (linéaire par morceaux) f(m) = 1/2 pour 0 ≤ m ≤ 1/2 et f(m) = (1 + m)/3 pour 1/2 < m ≤ 1.
Lorsque \(N\) tend vers l’infini, la moyenne discrète de \(C(x, y)/R(x, y)\) sur les cases du carré \([−N, N]^2 \) est bien modélisée par la moyenne continue de cette fonction de m sur l’intervalle [0, 1].
Le calcul donne une valeur moyenne égale à 13/24. Cela signifie qu’en moyenne, lorsqu’il faut 24 coups au roi pour atteindre une case éloignée, le cavalier n’en met qu’environ 13. Autrement dit, le cavalier est en moyenne
\[\displaystyle \frac{24}{13} \approx 1,85\]
fois plus rapide que le roi.
Généralisation : les (a, b)-cavaliers et les Fibocavaliers
Le cavalier n’est qu’un cas particulier d’une famille de pièces. On appelle (a, b)-cavalier \(C_{a,b},\) avec \(1 \leq a < b,\) une pièce qui peut se déplacer d’un coup de
\[C_{a,b} = \{(\pm a,\pm b), (\pm b,\pm a)\}.\]
Le cavalier habituel correspond donc à (a, b) = (1, 2).
Avant d’étudier leur vitesse, une question se pose : un (a, b)-cavalier peut-il atteindre toutes les cases de l’échiquier infini ? Il s’avère que cela n’est possible que si deux conditions sont satisfaites :
Supposons désormais ces conditions remplies. Comme pour le cavalier classique, on peut alors comparer la vitesse du (a, b)-cavalier à celle du roi. En reproduisant les mêmes idées que précédemment (réduction par symétrie, estimation du nombre minimal de coups, puis moyenne sur une grande région), on obtient une expression explicite :
\[v_R(C_{a,b})= \displaystyle \frac{2(a+b)b^2}{a^2 +3b^2}.\]
Nous ne détaillons pas le calcul ici, celui-ci suivant de près le raisonnement présenté pour le (1, 2)-cavalier. En faisant varier a et b, nous pouvons explorer une large gamme de pièces similaires au cavalier : la vitesse du (2, 3)-cavalier par rapport au roi est \(90/31 \approx 2,9,\) celle du (3, 4)-cavalier est \(224 /57 \approx 3,93,\) et ainsi de suite (Voir figures 5 et 6).
Un cas particulièrement intéressant apparaît lorsque a et b sont deux nombres de Fibonacci consécutifs. Rappelons que la suite de Fibonacci est définie par
\[F_1 = 1, F_2 = 1, F_{n+2} = F_{n+1} + F_n,\]
donnant la suite 1, 1, 2, 3, 5, 8, 13,…
On définit alors le n-ième Fibocavalier par
\[FC_n =C_{F_{n+1}, F_{n+2}}.\]
Le premier Fibocavalier est ainsi le cavalier classique.
Deux nombres de Fibonacci consécutifs sont toujours premiers entre eux. En revanche, leur parité suit un motif périodique : impair, impair, pair. Ainsi, lorsque l’indice n est divisible par 3, la somme \(F_{n+1} + F_{n+2} (= F_{n+3})\) est paire. Le 3n-ième Fibocavalier ne satisfait donc pas les conditions précédentes, tandis que les autres peuvent atteindre toutes les cases de l’échiquier.
Enfin, lorsqu’on compare la vitesse de deux Fibocavaliers consécutifs, on observe que
\[\displaystyle \frac{v_R(FC_{3n+2})}{v_R (FC_{3n + 1})} \to \phi = 1,618 \ldots \]
lorsque \(n \to \infty,\) où \(\phi\) désigne le nombre d’or1. Ainsi, même la vitesse de ces cavaliers particuliers porte la signature de la suite de Fibonacci.
Un voyage coloré
Les mathématiques des mouvements sur l’échiquier relient la combinatoire, la géométrie et la théorie des nombres. En analysant la répartition des cavaliers et des rois, nous découvrons des motifs liés à la symétrie, aux diviseurs et même à des suites classiques comme les nombres de Fibonacci. Que vous soyez un passionné d’échecs ou un amateur de mathématiques, ces pièces montrent qu’il y a toujours plus à explorer sur l’échiquier infini. Ainsi, la prochaine fois que vous réfléchirez aux sauts singuliers du cavalier, rappelez-vous : ce n’est pas juste un jeu, mais une porte d’entrée vers des aperçus mathématiques profonds !
- Voir les articles Nautile, nombre d’or et spirale dorée par Christiane Rousseau et Spirales végétales de Christiane Rousseau et Redouane Zazoun, vol. 3.2, été-automne 2008. Le nombre d’or par André Ross, Accromath, vol. 5, hiver-printemps 2010. ↩
