I08 RÉCRÉATIONS MATHÉMATIQUES

en

ce qui constitue une inversion cyclique de seize termes, et, par suite, est une opération équivalente à quinze inversions simples. De la sorte, une disposition des jetons pour laquelle le problème est impossible pourra être remplacée par une autre conduisant à la possibilité, et vice versa.

Il est évident que tout ce que nous venons de dire s'applique également à une boite rectangulaire contenant m. n cases et (m. n — i) jetons numérotés. Bien entendu, on peut avoir m = n. En faisant tourner une pareille boîte de 90°, si les nombres m et n sont tous les deux pairs, l'opération est équivalente à m, n — 3 inversions simples. Une disposition pour laquelle le problème n'est pas possible peut donc ainsi être remplacée par une autre donnant une solution, et vice versa. Mais à moins que m et n ne soient des nombres pairs, la rotation est équivalente seulement à un nombre pair d'inversions.

De même, si l'un ou l'autre des nombres m et n, est pair, et s'il est impossible de résoudre le problème avec la dernière case libre, on peut le rendre possible en laissant libre la première case.

On peut augmenter la difficulté du problème en limitant les mouvements possibles : en fixant, par exemple, dans la boîte des petites réglettes que les jetons en mouvement ne seront pas autorisés à franchir.

Nous pouvons concevoir également un jeu semblable avec un cube, mais la manœuvre des jetons ne pourrait se faire pratiquement que par section.

La Tour d'Hanoï. — Le jeu ingénieux connu sous le nom de ioar (T Hanoï a été imaginé en i883 par M. Claus (Lucas).

Il consiste en trois chevilles fixées sur un plateau et en huit disques circulaires, de bois ou de carton, percés au centre d'un trou

QUESTIONS DIVERSES lOQ

permettant de les enfiler sur les chevilles. Ces disques sont de diamètres différents et, à l'origine, ils sont tous sur la même cheville, le plus grand à la base et les autres suivant leur rang de décroissance jusqu'à celui couronnant la pile qui est le plus petit. Cette disposition forme la toar. Le problème consiste à faire passer chaque disque d'une cheville sur une autre, de telle sorte qu'aucun d'eux ne soit placé sur un disque plus petit, pour former finalement sur l'une des deux autres chevilles, en utilisant tous les disques, une tour identique à celle que l'on avait primitivement.

On opère comme il suit :

1° Si nous avons à Torigine n disques sur la cheville A, la première opération consiste à faire passer graduellement les n — i disques supérieurs de la cheville A sur la cheville B, en laissant libre la troisième cheville G.

Soit X le nombre des transports qu'une pareille opération exige.

2° On déplace alors le dernier, c'est-à-dire le plus grand et on l'enfile sur G.

3'' Puis en renversant le premier procédé, on transporte graduellement les/i — I disques de B sur G, opération qui exige encore x transports.

Dès lors, si l'opération du transfert d'une tour de n — i disques exige X transports simples de disques, l'opération du déplacement d'une tour de n disques exigera 2X -f- i transports séparés de disques simples.

Or, pour deux disques, on a 3 ou 2^ — i transports, donc, pour trois disques, nous aurons 2 (2^ — i) -+- 1 ou 2^ — i transports, et d'une façon générale, pour n disques, nous aurons à effectuer 2^ — I transports simples de disques.

Ainsi, les huit disques du jeu demandent 2^ — i = 255 transports simples. Gc résultat pourrait aussi s'obtenir au moyen de la théorie des différences finies. Il faut remarquer que chaque déplacement alterné revient à transporter le plus petit disque d'une cheville sur une autre, les chevilles étant prises en ordre circulaire.

IIO RÉCRÉATIONS MATIIlîlMATIQUES

M. de Parvillc a publié une si jolie légende sur l'origine de ce jeu que nous ne pouvons résister au plaisir de la reproduire (*).

(( Dans le grand temple de Bénarès, dit-il, au-dessous du dôme qui marque le centre du monde, on voit, plantées dans une dalle d'airain, trois aiguilles de diamant, hautes d'une coudée et grosses comme le corps d'une abeille. Sur une de ces aiguilles, Dieuenfda, au commencement des siècles, 64 disques d'or pur, le plus large reposant sur l'airain et les autres, de plus en plus étroits, superposés jusqu'au sommet. C'est la tour de Brahma. Nuit et jours les prêtres se succèdent, occupés à transporter la tour de la première aiguille de diamant sur la troisième, sans s'écarter des règles fixes et immuables imposées par Brahma. Le prêtre ne peut déplacer qu'un seul disque à la fois ; il ne peut poser ce disque que sur une aiguille libre ou au-dessus d'un disque plus grand. Lorsqu'en suivant strictement ces recommandations les 64 disques auront été transportés de l'aiguille, où Dieu les a placés, sur la troisième, la tour et les Brahmes tomberont en poussière et ce sera la fin du monde. »

Le nombre des transports séparés d'un simple disque que les Brahmines doivent effectuer pour déplacer la tour est de 2^* — i ou 18446744073709551615; nombre qui, en admettant que l'opération soit exécutée sans erreur de la part des prêtres, exigerait plusieurs milliers de millions d'années

Les anneaux chinois {^). — La figure 45 représente un jeu un peu plus difficile, connu sous le nom des anneaux chinois et que l'on trouve chez presque tous les marchands de jouets.

(1) La Nature, Paris, i884. première partie, pp. 285-286.

(2) Il a été décrit par Cardan, en i55o, dans son ouvrage De subtilitate, livre XV, paragraphe 2, édition Sponius, vol. III, p. 687 ; par Wallis dans son Algèbre, seconde édition, 1698, OEiivres, vol. II, chap. nr, pp. 472-478.

OzANAM y fait également allusion dans ses Récréations, édition de 1723, vol. IV, p. 439.

QUESTIONS DIVERSES III

Il consiste en un certain nombre d'anneaux métalliques égaux enfilés sur une sorte de navette évidée dans la partie centrale et munis chacun d'une petite tringle traversant une planchette en bois. Ils sont disposés de telle sorte que l'anneau à l'une des extrémités (A par exemple) peut être, à volonté, enlevé ou monté sur la navette ; mais un autre anneau quelconque ne peut être enlevé ou monté que si l'anneau le plus voisin du côté A est enfdé sur la navette, et tou3 les autres anneaux, du même côté, enlevés.

L'ordre des anneaux ne peut être modifié.

Un seul anneau peut être enlevé ou monté à la fois sur la navette [dans le jeu tel qu'on le trouve ordinairement, cette règle présente une exception en ce qui concerne les deux premiers anneaux qui peuvent être enlevés ou montés en même temps ; mais pour simplifier notre exposition nous supposerons tout d'abord qu'un seul anneau peut être enfilé ou enlevé à la fois].

Nous allons montrer que, dans le cas de /i anneaux, il est nécessaire pour les faire sortir tous de la navette d'enlever ou d'enfiler

un anneau simple un nombre de fois représenté par 0 (2"+^ — i)

ou par ^ (2""t-i — 2) suivant que n est impair ou pair.

Appelons d'une façon générale pas, l'opération qui consiste à enlever ou à faire passer un anneau sur la navette et supposons les anneaux numérotés en partant de l'extrémité A. Admettons que les m premiers anneaux soient sortis de la navette, tous les autres étant en-

Fig. tib.

core enfilés, et que l'enlèvement de l'anneau suivant exige X — I pas ; ceci revient à dire que (x — i) pas additionnels sont nécessaires pour disposer les anneaux de telle sorte que les m 4- i premiers soient hors de la navette et tous les autres sur la navette.

112 l\ECl\EA.TIONS MATHEMATIQUES

Avant de faire celte opération nous pouvons enlever le (m -f- 2)"'" anneau, de sorte que l'enlcvement du (m -h i)'"*' et du (m -h 2)°^^ anneau exige x pas en partant de la position initiale.

Supposons ces x pas faits et les (m + 2) premiers anneaux sortis de la navette, les autres étant encore enfilés, et cherchons combien de pas additionnels sont nécessaires pour enlever les (m -1- S)*"" et (m -h 4)""® anneaux. Pour effectuer l'opération nous commençons par enlever le (/n -h 4)"'° anneau, ce qui nous donne 1 pas ; puis avant de pouvoir enlever le (m -h 3)""* nous devons arranger les anneaux de façon que le (m H- 2}^"° soitsurla navette etlcs(m -h i) premiers hors de la navette : cette opération s'effectuera comme il suit :

i» Nous devons avoir le (m 4- i)™" anneau sur la navette et les m premiers sortis (ce qui exige x — i pas) ;

2° puis nous devons enfder le (m -f- 2)"*' amieau (ce qui donne I pas) :

3' Enfin, il nous faut enlever le (m -h i)™' anneau (ce qui exige encore x — i pas).

Ainsi, cette série de manœuvres nous donne en tout

[2(x — i) + 1] pas.

Maintenant nous pouvons enlever le (m — 3)'"° anneau (i pas) et nous restons avec les (m + i) premiers anneaux sortis, le (m + 2)'"^ sur la navette, le (m -}- 3)'"® également sorti et tous les autres sur la navette. Enfin pour enlever le (m -\- 2)"*° anneau : 1° nous laissons le (m -h 1)™® sur la navette et nous enlevons les m premiers {x — \ pas ) ;

2° nous enlevons le {m -f- 2)"^^ anneau (i pas) ;

3** nous enlevons le (m + i)™^ anneau ((a: — i) pas).

Cette nouvelle série de manœuvres représente

\i{x— i) + I] pas, Par conséquent, si lorsque les m premiers anneaux sont enlevés.

QUESTIONS DIVERSES 1x3

il faut X pas, pour détacher le (m -j- i)""* et le (m -+- 2)""®, le nombre des pas additionnels nécessaires pour détacher les (m -i- 3)° et (m H- 4)'"^ anneaux sera :

1 -h [2(x — i) -h i] -h I -I- [2(0? — i) + ï]> c'est-à-dire t\x. Pour déterminer le nombre total des pas nécessaires pour enlever un nombre impair d'anneaux, nous raisonnerons maintenant comme il suit :

L'enlèvement du t" anneau exige i pas ;

Par suite, l'enlèvement des 3 premiers anneaux demande [\ pas additionnels.

L'enlèvement des 5 premiers anneaux demande 4^ pas additionnels.

Nous voyons ainsi que le nombre des pas à faire pour enlever les (2 n H- i) premiers anneaux est