THÉORÈMES DES IMPASSES

Nous venons de traiter le cas d'une impasse simple, formée d'un seul chemin dont les extrémités aboutissent à un même carrefour. Plus généralement, nous appellerons impasse toute fraction d'un réseau qui n'a d'autres points communs avec le reste du réseau que les extrémités de deux chemins, de telle sorte que la suppression de l'extrémité de chaque chemin détermine la séparation du réseau en deux autres ; le réseau total se compose alors de deux réseaux partiels, dont le plus simple est l'impasse . Mais deux cas peuvent se présenter, suivant que les deux chemins de l'impasse aboutissent à un même carrefour du réseau partiel ou à deux carrefours dififérents. Le premier cas a été étudié par M. Tarry; nous y avons ajouté le second cas.

Premier cas. — Supposons que les deux chemins a et ^ de l'impasse aboutissent à un carrefour A du réseau partiel {/ig. gS );

Fig. 93.

Impasse aboutissant à un seul carrefour.

désignons par I et R les nombres de circuits de Timpasse et du réseau partiel, et par] 2p le nombre des chemins du réseau

Sixième récréation.

restant qui aboutissent au carrefour A, sans compter les deux chemins a et b. Dans un circuit du réseau partiel, on passe p fois au carrefour A, et à Tun quelconque des passages il faut nécessairement décrire complètement l'un des circuits de l'impasse; par suite, le nombre des circuits du réseau total est|7lR. Si le point A était un point simple du réseau restant, on ferait p=z2\si l'impasse était formée d'un seul chemin dont les extrémités viendraient aboutir au carrefour A, on ferait 1 = 2. Enfin, si q impasses indépendantes les unes des autres aboutissent au carrefour A, et si l'on distingue par des indices les nombres de leurs circuits séparés, on trouve, par la suppression successive des impasses, que le nombre des circuits du réseau total est égal au produit

Deuxième cas. — Supposons que les deux chemins ^ et ^ de

fig- 94-

Impasse aboutissant à deux carrefours.

rimpasse I aboutissent à deux carrefours A et B du réseau restant (fig. 94) ; alors ces carrefours sont impairs, ainsi que les premiers

La Géométrie des réseaux et le problème des dominos. 143

carrefours G et D de l'impasse que l'on rencontre immédiatement par les chemins a et b. Pour évaluer le nombre des circuits du réseau total, partons du point a de AC; nous avons deux sens; en partant suivant aA, nous décrivons le réseau partiel augmenté du chemin ab dans un seul sens; puis nous arrivons en b et, au lieu de décrire ba^ nous suivons le chemin éDC et nous parcourons l'impasse dans un seul sens pour revenir en a\ par conséquent, le nombre total des parcours dans les deux sens est la moitié du produit des nombres de circuits de l'impasse et du réseau partiel.

On observera, d'ailleurs, que l'application de ce théorème est illusoire, si l'impasse I se compose d'un seul chemin.

THEOREME DES CARREFOURS.

Pour évaluer le nombre des tracés d'un réseau quelconque, on ramène, ainsi que nous l'avons vu, les réseaux à carrefours impairs à des réseaux à carrefours tous pairs. Cela fait, on commence par supprimer toutes les impasses qui peuvent exister, en remplaçant le réseau total par des réseaux partiels. Considérons donc un réseau n'ayant plus aucune impasse; pour déterminer le nombre de ses circuits, on le remplace par d'autres ayant un carrefour de moins, et ainsi de suite, jusqu'à ce que tous les réseaux obtenus ne contiennent plus que deux carrefours; on revient alors aux pérégrinations de la fourmi.

Si 2n chemins a, ^, c, ^, . . ., aboutissent à un même carrefour, on décompose le réseau en N autres réseaux obtenus en sou-

144 Sixième récréation.

dant deux par deux, de toutes les manières possibles, les 2n chemins a, bj c, d, D'ailleurs, en soudant un premier chemin

avec un autre, on a le choix entre (2^ — 1) chemins; puis, en soudant un autre chemin avec un autre, on a le choix entre (2« — 3) chemins, et ainsi de suite. On a donc

c'est le nombre des manières de remplacer un produit de 2n facteurs, premiers entre eux deux à deux, par un produit de n facteurs, en groupant les facteurs deux par deux.

C'est encore le nombre que nous avons trouvé pour ramener à un réseau à carrefours tous pairs, un réseau ayant 2/1 points impairs.

Dans l'application de ce théorème, on doit faire les deux remarques suivantes : 1° Si la suppression d'un carrefour amenait la désagrégation du réseau, on recommencerait l'opération en appliquant d'abord le théorème des impasses; cette observation s'applique aussi bien aux réseaux partiels qui remplacent le réseau primitif; 2<* les N labyrinthes obtenus par la suppression d'un carrefour ne spnt pas toujours tous distincts; deux réseaux sont équivalents lorsqu'ils possèdent le même nombre de carrefours, et que deux carrefours quelconques sont réunis parle même nombre de chemins.

La Géométrie des réseaux et le problème des dominos, 146