La ronde des cavaliers : Deuxième prise !

Dans le précédent article, nous avions vu qu’il était impossible de faire un tour – ou parcours fermé – du cavalier sur des échiquiers de taille particulière. Si vous ne l’avez pas consulté, je vous le recommande vivement, car je reprends dans les lignes qui suivent certains éléments abordés dans l’article en question.

Voilà ? C’est fait ? Parfait ! Continuons.

Parmi les situations impossibles, il en subsistait une sur la quelle je n’avais touché mot. Soyez rassurés, car le temps est venu de remédier à cet oubli. Dans cet article, nous démontrerons pourquoi, sur un échiquier de taille 3 x 8, il est impossible de faire un tour du cavalier. Accrochez-vous à vos ceintures, c’est parti.

Des réductions

Non, pas question de soldes ni de promotions, mais de graphes. Comme nous l’avons déjà vu, nous pouvons modéliser les mouvements de notre cavalier par un graphe.

Les cases de notre échiquiers sont matérialisées par des sommets. Ces sommets sont eux-mêmes reliés entre eux lorsqu’il est possible de joindre l’une et l’autre en un seul tour pour notre cavalier – lequel, rappelons-le, se déplace selon une trajectoire « en L ».

Si nous prenons un plateau de 3 lignes et 8 colonnes, voici à quoi pourrait ressembler notre graphe.

Graphe du cavalier

Graphe du cavalier sur un échiquier 3 x 8

Le but est donc de trouver un chemin qui passe une et une seule fois par tous les sommets, et qui en plus, revient à son point de départ.

Une solution consisterait à tous les essayer. Et là, je ne dis pas qu’une telle solution ne fonctionnerait pas, j’affirme simplement qu’elle ne serait pas élégante, car elle ne mettrait pas en avant toute l’astuce dont les mathématiques peuvent se vanter. Ce serait fort dommage.

Plutôt que de partir tête baissée, nous allons plutôt nous intéresser à certains sommets particuliers. Regardez par exemple le sommet de la deuxième ligne, première colonne. De ce sommet, seules deux arêtes partent (ou y arrivent, c’est selon).

Or, nous cherchons un chemin qui passe pas tous les sommets du graphe : un tel chemin, s’il veut arriver à notre sommet (2,1) – notation pour dire 2ème ligne, 1ère colonne – devra forcément passer par ces deux arêtes.

Un chemin qui décrit un tour du cavalier devra forcément passer par toutes les arêtes rouges de ce graphe.

Et c’est là qu’intervient la réduction. Le sommet (2,1) est relié aux sommets (1,3) et (3,3). Un tour du cavalier devra forcément passer successivement par la chaîne (1,3) – (2,1) – (3,3), ou dans l’autre sens, (3,3) – (2,1) – (1,3). Du coup, plutôt que de s’embêter à garder ces trois sommets, nous allons les regrouper en un seul super-sommet. A ce sommet, nous allons relier tous les sommets qui arrive à l’une ou l’autre des extrémités. Nous réduisons ainsi le nombre de sommets à étudier.

On se ramène à un graphe plus simple en réduisant le nombre de sommets.

De cette manière, si j’ai un tour du cavalier dans mon graphe de départ, alors j’aurai forcément un « tour du cavalier » – ou cycle hamiltonien, rappelons ce mot – dans mon graphe réduit. Un chemin qui passe par mes trois sommets dans mon graphe d’origine passera par mon super-sommet dans mon graphe réduit. Attention, l’inverse n’est pas forcément vrai, puisque mon super-sommet a créé de nouvelles connexions !

Par ailleurs, vous aurez peut-être aussi remarqué que les coins également n’avaient que deux arêtes, alors pourquoi ne pas les réduire eux aussi ? Voyons les deux coins de droite.

Ce que l’on peut voir, c’est que ces deux sommets sont reliés à un même troisième sommet, celui situé à la position (2,3). Cela limite mes mouvements : pour ne passer qu’une et une seule fois par chaque sommet, je dois parvenir au sommet (2,3) depuis l’un des coins, puis repartir vers le deuxième coin. En fait, je peux supprimer les arêtes qui relient (2,3) à (1,5) et (3,5), je sais déjà que je ne les utiliserai pas.

Graphe des coins

Aux quatre coins n’arrivent que deux arêtes. Avec un peu de logique, je m’aperçois que je dois forcément passer par les arêtes vertes et oublier les noires.

De la même manière que précédemment, je peux donc réduire mon graphe, en ramenant à un seul super-sommet tous les sommets qui sont reliés par une arête verte.

Chemin obligatoire

Le chemin obligatoire lorsque j’approche des coins

Couper le graphe

Allez, résumons ! Voici notre graphe tel que nous l’avons étudié : nous devons passer par les arêtes rouges et vertes, mais nous ne pouvons passer par les arêtes noires qui ont été barrées

Total

Au total…

Il ne nous reste plus qu’à réduire la bête pour nous ramener à un graphe plus simple à étudier.

Réduction totale

On réunit tous les sommets reliés par une arête coloré ensemble, et on efface les arêtes interdites

Plus sympathique non ? Nous passons de 24 sommets à seulement 8 avec un peu d’astuce. Encore un peu de réflexion et nous aurons notre résultat tant espéré !

Nous voyons ici deux sommets qui sont reliés chacun à trois autres sommets. Que se passe-t-il si l’on supprime ces deux polissons ?

On supprime les deux sommets reliés à 3 autres sommets

Vous voyez apparaître trois segments : notre graphe est divisé en trois morceaux, alors que nous n’avons retiré que deux sommets. Si nous avions un tour du cavalier, ce serait impossible !

Dans un graphe qui comporte un cycle hamiltonien, si on retire deux sommets, on ne peut pas créer plus de deux morceaux ! Pensez encore au collier ou au bracelet fermé : si vous le coupez à deux endroits différents, dans le pire des cas, vous n’aurez que deux morceaux. C’est la même chose ici.

Donc il n’y a pas de cycle hamiltonien ou de tour du cavalier dans notre graphe réduit. Or, s’il y en avait eu un dans le graphe d’origine, on en aurait trouvé un dans ce graphe réduit… C’est donc que notre graphe d’origine, notre échiquier 3 x 8, ne comporte aucun tour du cavalier.

Voici notre preuve bouclée. Avouez que c’est plus élégant que de tout essayer !

 

Cet article a été publié dans Curiosités et récréation. Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s