TS
Cm d.
Si nous formons le mineur de b^ et si nous y remplaçons par zéro chaque terme comptenant la lettre b ou l'indice â, iious déterminons toutes les solutions où] figure 6.^. Mais, dans ce cas, le mineur se réduisant immédiatement à e^gag^iPs, nous obtenons ainsi une solution, à savoir ^aC^B^s^t^s' ^®* solutions dans lesquelles figurent P2»^*»^6»p8»^8»<^6 ®' ^t pwi'^ent être obtenues par symétrie.
Il estàiâé de voir que parmi ces huit solutions, deui seulement sont distinctes : on peut les appeler solutions du second type.
Enfin les dernières solutions doivent être obtenues au moyen du déterminant
o Tb P,
'4 Cg O
Si nous prenons le mineur de c, et si nous y remplaçons par o chaque terme renfermant la lettre ou l'indice S, nouâ obtien-
drons toutes les solutions où figure c^. Mais, dans ce cas, le mineur s'annule. Par suite aucune solution ne renferme Cj et, comme conséquence, par symétrie, aucune solution ne renferme YsjT? ou c,.
Si la méthode que nous venons d'exposer nous avait fourni quelques solutions renfermant le S"' élément de la première ou de la dernière ligne ou colonne du déterminant, nous les aurions appelées solutions du 3"" type.
En résumé le cas considéré présente lo solutions et seulement lo, à savoir : huit du premier type, deux du second type, et aucune du troisième type.
Semhlablement, pour n = 6, nous obtenons : aucune solution du premier type, quatre solutions du second type, et aucune solution du troisième type ; soit en tout quatre solutions. Pour n = 7, nous obtenons seize solutions du premier type, vingt quatre solutions du second type, aucune solution du troisième type et aucune solution du quatrième type, soit en tout l\o solutions. Pour n = 8, nous avons seize solutions du premier type, cinquante six solutions du deuxième type et vingt solutions du troisième type, c'est-à-dire au total 93 solutions.
Il y a lieu de remarquer que toutes les solutions d'un type ne sont pas toujours distinctes. En général d'une solution quelconque, sept autres peuvent se déduire immédiatement.
De ces huit solutions quatre sont constituées par la solution initiale ou fondamentale et par les trois semblables obtenues en faisant tourner l'échiquier d'un, de deux ou de trois angles droits ; les quatre autres sont les images des quatre premières réQéchies dans un miroir. Mais dans certaine cas particuliers il peut arriver que la réflexion reproduise la figure originale, ou qu'une rotation de un ou de deux angles droits conduise à des résultats ne présentant aucune diflerence. Ainsi, sur les échiquiers de 4*» 5^, 6*, 7^, 8^, 9* et 10^ cases, il y a respectivement i, 2, 1,6, 13, 46, 92 solutions fondamentales ; tandis que le nombre total de solutions est respectivement pour chacun d'eux 2, 10, 4, 4o, 92, 862 et 724.
La collection suivante de solutions fondamentales intéressera cer-
QUESTIONS DIVERSES 121
tainement le lecteur. Les positions des reines sur Téchiquier sont indiquées par des chiEFres : le premier chiffre représente le rang de la case occupée par la reine dans la première colonne en comptant à partir d^une des extrémités de la colonne, le second chiffre indique le rang de la case dans la seconde colonne, et ainsi de suite. Ainsi, sur un casier de 4' cases, la solution représentée par 3 i4a, signifie qu'une reine est sur la troisième case de la première colonne, une autre sur la première case de la seconde colonne, une troisième sur la quatrième case de la troisième colonne, et enfin, la quatrième reine sur la seconde case de la quatrième colonne. Si une solution fondamentale ne donne naissance qu'à quatre solutions, le nombre qui la représente est placé en Ire deux parenthèses, si elle fournit seulement deux solutions, le nombre qui la symbolise est placé entre deux crochets ; les autres solutions fondamentales donnent naissance chacune à huit solutions.
Sur un échiquier de 4^ cases on trouve i solution fondamentale [3i4a];
Sur un échiquier de 5^ cases on trouve 2 solutions fondamentales, i4253, [253i4];
Sur un échiquier de 6' cases on trouve i solution fondamentale (246 i35j ;
Sur un échiquier de 7' cases on trouve 7 solutions fondamentales 1357346. 3 572461, (5724613), 4613572,3162074. (2574i36).
L'échiquier de 8* cases donne 12 solutions fondamentales, 25713864, 57138642, 71386 425, 82417536, 68241753, 36824175, 64713528, 36814752, 36 8x5 724, 72418 536, 26831475,(64718253).
L'arrangement suivant cet ordre est du à M. Oram.
Il faut remarquer que les solutions 10, 11 et 12 sont respectivement à peu près semblables aux solutions 4, 6 et 7. La 6'"* solution est la seule pour laquelle trois reines ne se trouvent pas en ligne droite.
L'échiquier de 9^ case^ fournit 46 solutions fondamentales dont l'une d'elles est représentée par le nombre 248 396 157. Sur l'échi-
quier de lo^ cases on trouve 92 solutions fondamentales ; elles ont été données par le D" A. Pein (') ; l'une d'elles s'exprime par le nombre 2 468 t i3 679, dans lequel t représente 10. Sur l'échiquier de 11^ cases, les solutions fondamentales sont au nombre de 34 1 ; elles ont été données par le D' T, B. Sprague (^) : Tune d*elles est 16926 t 37 e 48.
Nous pouvons ajouter que pour un échiquier de n^ cases, il existe toujours une solution symétrique delà forme 246... n i35... (/i — i), quand n = 6 m, ou ai = 6 m -h 4»
M. Oram a montré également que sur l'échiquier de n* cases» et
Fig. 5o
cjuand n représente un nombre premier, on obtient des solutions par des arrangements cycliques des n nombres naturels, autres que
(') Aufstellung von n koniginnen auf einem Schachbrett von n2 Feldern, Leipzig, 1889.
['^) Proceedmgs ofihe Ed'uihurgh Mathematical Society , vol. XVII, 1898-9, PPi 43-68.
QUEStlONS DIVERSES 123
celui donné par l'ordre naturel ; on peut voir, par exemple la solution citée ci-dessus.
On trouve chez les marchands de jouets un jeu identique sous la forme d'un petit carré en bois comprenant trente six cases et portant les divisions et les traits représentés sur la figure 5o. A chaque point de rencontre des lignes horizontales et verticales, la planchette est percée d'un trom et il s'agit d'y placer six petites chevilles de façon que deux quelconques d'entre elles ne soient pas sur la même ligne.
Autres problèmes avec des reines. — Le capitaine Turton a signalé à notre attention deux autres problèmes présentant beaucoup d'analogie avec le précédent ; aucun d'eux, croyons-nous, n'est encore connu et n'a été résolu autrement que d'une façon empirique.
Dans le premier il s'agit de placer huit reines sur un échiquier de manière à commander le plus petit nombre possible de cases. Ainsi, en plaçant les reines sur les cases i et 2 de la seconde colonne, sur la case 2 de la sixième colonne, sur les cases i, 3, 7 de la septième colonne et sur les cases 2 et 7 de la huitième colonne, nous aurons sur l'échiquier onze cases qui ne seront pas en échec ; on peut déterminer d'autres arrangements nous donnant ce même nombre.
Est-il possible de disposer les reines de façon à avoir plus de onze cases qui ne soient pas en échec P jusqu'à présent nous n'avons réussi, ni à faire mieux, ni à montrer que cela n'était pas possible.
Dans le second problème, il s'agit de disposer sur un échiquier m reines (m étant plus petit que 5) de façon à commander le plus grand nombre possible de cases. Par exemple, quatre reines peuvent être placées de plusieurs manières sur un échiquier pour commander cinquante-huit cases indépendamment de celles qu'elles occupent, en laissant par conséquent seulement deux cases qui ne soient pas en échec. Ce résultat peut s'obtenir en particulier en plaçant les reines sur la cinquième case de la troisième colonne, sur
la première case de la quatrième colonne, sur la sixième case de la septième colonne et sur la deuxième case de la huitième colonne ; ou encore en les disposant respectivement sur les première, septième, troisième et cinquième cases des première, troisième, cinquième et septième colonnes.
Un problème semblable consisterait à déterminer le nombre minimum de reines et les positions quUl faudrait leur donner sur un échiquier de n} cases, pour que toutes les cases soient commandées ou occupées.
11 paraîtrait que, même en introduisant la restriction qu'aucune reine ne peut en prendre une autre, on ne trouve pas moins de 91 solutions typiques permettant de disposer 5 reines sur un échiquier de façon à commander toutes les cases (').
Problèmes avec d'autres pièces du jeu. — On peut proposer des problèmes analogues en choisissant d'autres pièces du jeu d'échec. Par exemple on a proposé de déterminer le nombre maximum des cavaliers pouvant être placés sur un échiquier de n} cases de façon que deux quelconques d'entre eux ne soient pas en prise, ainsi que le nombre minimum des cavaliers qu'il faut disposer sur l'échiquier pour que toutes les cases soient commandées ou occupées. (^)
Des problèmes semblables ont été proposés pour le cas de k rois sur un échiquier de n^ cases. (') On a avancé que, si /c =■- 2, le nombre de manières de disposer a rois sur l'échiquier de façon qu'ils ne puissent occuper deux cases adjacentes a pour expression
De même, si /c = 3, le nombre de manières dont on peut dispo-
(') V Intermédiaire des Mathématiciens y Paris, 1901, vol. VIII, p. 8 S. (*) Ibid. mars 1896, vol. III, p. 58; 1897, vol. IV, pp. i5, 254; et 1898, vol. V, p. 87.
(') Ibid. juin 1901, p. i4o.
QUESTIOIVS DIVERSES
ser 3 rois sur l'cchiquier de façon que deux d'entre eux n'occupent pas des carrés adjacents est
g (n — i) (/i — 3) (n* 4- 3n» — aon* — 3on + i32.)
IjO problème des quinze éoolières. — Ce problème, qui a été énoncé pour la première fois par M. T. P. Kirkman et qui est quelquefois connu sous le nom de problème de /{'îr/fman(*), consiste, en principe, à disposer quinze objets en différentes séries de triades remplissant certaines conditions déterminées.
(*) Il a été publié pour la première fois en i85o dans Ladfs and Gentleman^s Diaryy p. 48, et a donné lieu à do nombreux mémoires. Nous citerons principalement les articles suivants :
A. G^TLET dans le PJiilosophical Magazine, juillet i85o, série 3, vol. XXXVII, pp. 5o-53 ;
T. P. KiRKMANN, dans le Cambridge and Dublin MathematicalJournal, i85o, vol. V, p. 260 ;
R. R. AïiSTicE, dans le Cambridge and Dublin Mathematîcal Journal, i852, vol. VII, pp. 279-292 ;
B, PiERCE, Gould^s Journal, Cambridge U. S. 1860, vol. VI, pp. 169-174. T. P. KiRX.MA.iv, Philosophical Magazine, mars 1862, série 4» vol- XXÏII,
pp. 198-204;
W. S. B. WooLHOusE, dans le Ladfs Diary de 1862, pp. 84-88, et de i863, pp. 79-90;
Le même dans le Educational Times Reprinls, 1867, vol. VIII, pp. 76-83 ;
J. Power, dans le Quarterly Journal of MathematicSy 1867, vol. VIII, pp. 236-25 î ;
A. H, Frost, dans le Quarterly Journal of Mathematics^ 1871, vol. XI, pp.26-37 ;
£. Garpmabl, dans les Proceedings 0/ the*London Mathematical Society y i88ï, vol. XII, pp. i48-i56;
Lucas, dans ses Récréaiions,^ voj. IJ, partie VI;
A. G. Diiow, dans le Messenger of Mathematics^ Cambridjge, octobre 18.93,. vol.' XXIII, pp. 88-89'; ®^ W. BuRNsroE, dans le même, 1894, vol. XXIII, pp. 137-143.
Il a été également discuté, par W. Ahrehs dans ses Mathematische Unterhaltungen und spiele, Leipzig, 1901, chap. XIV.
On le présente généralement sous cette forme : Une maîtresse de pension avait l'habitude de conduire tous les jours en promenade ses quinze élèves en les disposant sur cinq rangs, comptant chacun trois jeunes filles. On demande comment elle doit s'y prendre pour que chacune des élèves se trouve successivement une seule fois en compagnie de chacune de ses camarades.
Plus généralement on pourrait se proposer de disposer 3m jeunes filles en triades pour faire des promenades pendant
- (3m — i) jours, de façon que chaque enfant eût successivement
une seule fois chacune de ses camarades comme compagne de route.
La théorie de la formation de toutes les triades possibles pour le cas de quinze élèves ne présente aucune difficulté sérieuse, mais l'extension au cas de 3m personnes n*a pas encore été résolue. Nous allons présenter trois solutions, toutes les trois analytiques, mais en faisant remarquer que le problème peut également se traiter par des méthodes géométriques.
Méthode de Frost. — La première de ces solutions est due à M. Frost. Son exposition complète nous conduirait à 'des développements trop considérables et nous nous contenterons d*en présenter un aperçu qui donnera, pensons-nous, une idée suffisamment exacte du procédé.
Représentons par k lune des jeunes filles, ses compagnes de promenades étant différentes chaque jour, supposons qu'elles soient :
le dimanche «*•»•••••• ai et «a,
le lundi • • • é • . . 6i et &2»
le mardi . . . . é cj et C2,
et finalement le samedi 9i et ^2>
Nous avons ainsi les sept triades ou combinaisons trois à trois ka^ac^ \ khj)^ \ kc^c^ | kd^d^ | ke^e^ \ kfj^ \ kg,g^.
QUBSTlOIfS DIVERSES
dont chacune sert pour un jour, et il nous faut déterminer sept suites de quatre autres triades formées avec les quatorze lettres Oj, Og, 6j, 63, Cj, C2, ci,, d2, e,, «ai/iï/a, Çiy g^ de telle sorte que deux mimes lettres ne figurent pas ensemble.
Or, convenons d'écrire a pour ai ou Cg, b pour b^ oub^, c pour C| ou Cg* et ainsi de suite ; les indices i et a sont appelés complémentaires. Alors, pqisque les trois lettres qui entrent dans chacune des triades que nous cherchons à former doivent être différentes, il s'agit de composer avec ces lettres a, 6, c, d, e, /, g des arrangements de trois lettres, tels que deux quelconques d'entre elles ne se trouvent pas ensemble plus d*une fois. Aussi on peut grouper a avec 6c, de et fg, puis 6 avec df et eg^ et enfin c avec dg et ef.
Nous obtenons, par ce moyen, les sept triades fondamentales :
abc, ade, afg, bdf, beg, cdg, cef.
Parmi ces sept triades, les quatre qui ne coi^tiennent pas la lettre a seront placées dans la colonne du dimanche, les quatre qui ne renferment pas la lettre b seront inscrites dans la colonne du lundi, et ainsi de suite. Cela nous donne le canevas suivant ;
Piinao«)i(l
I^Hndi
M«rdi
Merer«<)i
Jeudi
Vtndredt
Samedi
ka^a^
kb^h
kCiC2
kdid2
/cciCg
Vi/2
f^gm
bdf
ad e
ade
abc
ab c
ab e
ab c
be g
^fg
^fg
^fg
ode
ad e
cd g
cd g
bdf
bdf
beg
cef
beg
cej
cd g
cd g
Faisons maintenant remarquer que chaque triade fondamentale donne quatre combinaisons des quatorze jeunes filles prises trois à trois, qui peuvent entrer dans le tableau des promenades de la semaine. Par ei^emple, la disposition bdf nous donne les quatre triades^
d^bif^, bidj^, K^iU Mi/i-
On pourrait disposer les indices i et 2 de plusieurs autres manières, mais nous avons donné celle qui se présente le plus naturellement.
Inscrivons donc ces combinaisons dans les colonnes respectives qui contiennent bdf^ c'est-à-dire dans les colonnes du dimanche, du mardi, du jeudi et du samedi ; puis, dans ces mêmes colonnes, donnons à l'autre lettre, 6, d ou f, Tindico complémentaire de celui déjà écrit, on obtient ainsi pour les quatre dernières lignes du tableau
bAfi
ade
abc
abc
\eg
o^fS
«/iff
ade
cd^
cdg
hAh
beg
\dj.
beg
bM
ce/
b,eg
cef
cd,g
cdg
ce/.
Cela fait, la triade suivante dans la colonne du dimanche est h^eg. La disposition beg se présente dans quatre colonnes et comprend quatre triades possibles, telles que
^a^jffi» Vifl^i» ^i«iflf2. ^«sflfi»
On les inscrit, et on donne les indices complémentaires aux autres mêmes lettres dans ces quatre colonnes.
En opérant ainsi, l'arrangement cherché s'obtient graduellement en prenant une triade à la fois, notant d'indices convenables les lettres dans les triades qui s'en déduisent, et donnant ensuite les indices complémentaires aux autres lettres semblables dans les mêmes colonnes.
Voici un arrangement final obtenu ainsi
Dimanehe
Lundi
Mardi
Mercredi
Jeadi
Vendredi
Samedi
/faia.2
UhM
kCiC^
hd,d^
/cCiCî
¥ih
bidtfi
aidiei
aîb^Ci
atbiCi
ai6jC2
heigt
aî9if2
ai/i92
adi ei
«adicj
cid^gi
cidiQi
bieig^
C2eji
Cid^i
C24igi
ClCi/,
QUESTIONS DIVERSES I2g
Nous pouvons obtenir d'autres solutions en choisissant sept autres triades ou en adoptant un autre arrangement pour les indices dans chaque triade (ou simplement en effectuant des inversions entre les lettres et les indices dans le tableau ci-dessus).
En opérant ainsi, M. Power a montré que le problème ne présentait pas moins de i5 667552000 solutions différentes, mais puisque le nombre total des manières dont la premenade peut être effectuée, dans une semaine, par les élèves disposées en triades est de (455)''» la probabilité qu'une de ses promenades, prise au hasard, se fasse suivant la condition imposée par Kirkman est très petite.
La méthode de M. Frost est applicable au cas de 2^" — i écolicres se promenant en triades pendant 2**^ ■" * — i jours. Il a donné la solution détaillée pour soixante-trois jeunes filles marchant pendant trente-et-un jours, cas qui correspond à /i = 3,
Méthode d'Anstice. — Une autre façon d'aborder le problème est due à M. Ânstice ; elle fournit l'élégante solution suivante qui permet de déduire, au moyen d'une permutation circulaire, de Tordre choisi pour le dimanche, l'ordre à adopter pour les six jours suivants.
Représentons les écolières respectivement par les lettres
fc, ai, «2» «a» ^4> ^6> «6» ^7» ^1» ^2» *8» ^4> Kf ^6» ^7
et supposons que l'ordre, pour le dimanche, soit :
ka^b^y a^a^a^, «4^6» «e^a^T» «7^A*
En faisant permuter circulairement les indices, on obient six autres arrangements qui remplissent les conditions du problème : la raison en est que dans la disposition donnée ci-dessus, la différence des indices de chaque couple de lettres semblables (telles que les lettres a ou les lettres 6), dans une triade, diffère d'une triade à l'autre, et il en est de même de la différence des indices de chaque couple de lettres dissemblables entrant dans une triade.
Récréations Mathématiques, II. g
l30 RÉCRÉATIONS MATHÉUATIQUES
On peut former, pour le dimanche, deuï autres arrangements, qui donneront par permutation circulaire^ les dispositions pous les autres jours de la semaine. Ce sont :
fcaj6j, ajajja-, 0^6.6., 05636^, a.b^b^, et
ka^b^y Oa^jasi û^ft^tg, a^b^b^, a^b^b^.
La méthode de M. Anstice s'applique au cas de 2 /) + i jeunes filles se promenant par rangs de trois pendant p jours, dételle sorte qu'aucun couple ne puisse marcher ensemble plus d'une fois, p étant un nombre premier delà forme 12 m 4- 7. Il a montré comment il était possible de former un arrangement fondamental pour un jour de promenade et comment on pouvait en déduire les arrangements pour les p — I jours restants au moyen de permutations circulaires des indices. Le nombre des arrangements fondamentaux est de
Le problème des quinze écolières correspond à m = o, et le» trois arrangements fondamentaux de M. Anstice sont donnés plus haut.
Si m = I, nous avons le problème des trente-neuf écolières. L'un des' arrangements fondamentaux est dans ce cas :
ka^b^y a^a^ai^, «s^t^'^ioj ^e^n^is» «3^10^15» ^iKh* «o^s^g» «15^8^4» «isMiT» «iAa^e» «i5^A» «le^^i» «isMia-
Si m = 2, nous avons le problème des soixante-trois écolières, dont M. Frost a donné une solution ; et ainsi de suite.
Méthode de M. GilL — M. J. H. Gill nous a donné l'idée d'une nouvelle façon de traiter la question.
En représentant les élèves par les lettres
QUESTIONS DIVERSES
i*» Il forme une triade du type a. a,n -h r, agm -H i. au moyen de laquelle il déduit, en permutant circula irement les indices i, 2, 3,...., 3m, m triades composant un arrangement pour un jour; puis
2' Il forme - (m — 1) autres triades telles que les trois différences
des indices soient différentes, et il en tire, par des permutations
circulaires des indices, les arrangements pour les - (m — i) jours
qui restent.
Ainsi, dans le cas des quinze écolières, la triade a^a^ai^ donne (par des permutations circulaires des indices) un arrangement pour le premier jour et deux triades telles que a^a^a^, ^103^8 nous permettant de former trente triades dont on peut déduire immédiatement un arrangement pour les six autres jours de la semaine. Voici une des solutions obtenues par cette méthode.
1«' jour
2* jour
3« Joar
4* jour
5' jour
fl« jour
7» jour
7, 8, ri
3, 5,ir
Il,l2,l5
5,io,i5
Mais bien que cette méthode nous donne des triades qui nous permettent de résoudre le problème, l'arrangement final est empirique.
Une solution du problème des vingt-une écolières, pour dix jours de promenades, peut s'obtenir par cette méthode.
aiagCjg donne sept triades constituant un arrangement pour un jour et a^ a^ ctg, a, a, a^^, a^ a^ a^Q nous fournissent soixante-trois triades dont on peut déduire une disposition de promenade pour les neuf autres jours. Voici la solution obtenue ainsi :
RÉGRÉATIOIfS MATHÉMATIQUES
l»r jour
2* jour
