§ Posté le 30/04/2015 à 19h 29m 22
Je participe actuellement à une activité de « maths à modeler », destinée à présenter quelques problèmes mathématiques à des élèves de différents niveaux(1). Je vais développer ici l'un de ces problèmes, utilisé pour faire saisir les notions de bornes (inférieure et supérieure) et de preuve mathématique.
Notez qu'il s'agit, comme les autres problèmes que nous proposons, d'un véritable sujet de recherche : bien sûr, la partie présentée ici, et que nous développons principalement en classe, est assez bien connue, mais ce n'est qu'une petite partie d'un problème plus vaste sur lesquels des chercheurs travaillent réellement : le but est d'initier à la recherche par un exemple réel.
En conséquence, je compte sur vous pour jouer le jeu, dans tous les sens du terme : je vous donnerai bien sûr quelques indices que j'espère utiles, puis les solutions aux questions précises que je poserai, mais il vous revient de chercher par vous-mêmes avant de les consulter, faute de quoi cet article n'aurait pas grand intérêt.
Avancez par étapes, réfléchissez, et quand vous pensez avoir trouvé, continuez.
Bien sûr, ce genre d'ateliers ne se met pas au point les mains dans les poches : les élèves, particulièrement les plus jeunes, ont besoin de manipuler, et nous utilisons pour cela des plateaux avec des pièces à disposer dessus. Un tableau (blanc ou à craie), voire un papier et un crayon, peuvent également servir de support de réflexion adapté.
Au cas où le matériel de note ferait défaut, reconstituer le quadrillage du plateau avec les moyens du bord (des couverts, par exemple(2)) peut également fonctionner. Mais puisque ce blog ne permet pas encore de vous fournir des objets physiques, j'ai mis au point une petite interface adaptée à ce problème-ci, qui devrait vous permettre de travailler correctement.
À l'origine, il s'agit d'un problème mathématique assez connu, qui consiste à tenter de placer le plus de reines possibles sur un échiquier sans qu'aucune n'en mette une autre en échec (en faisant, bien sûr, abstraction des couleurs). Les joueurs de l'excellente série Professeur Layton ont peut-être eu l'occasion de s'y essayer.
Mais, comme les reines peuvent être assez complexes à manipuler du fait de leur importante marge de manœuvre, nous allons commencer en essayant également avec d'autres sortes de pièces : les tours, les fous, les rois et les cavaliers(3).
Normalement, je vous en ai dit suffisamment, et vous pouvez cesser la lecture ici. Mais nous allons quand même essayer de donner davantage de détails, pas à pas.
Comment savoir si une combinaison est bonne ou pas ?
Le but du jeu est de placer le plus de pièces possibles sur l'échiquier. Si vous arrivez à placer un certain nombre de pièces, vous avez montré que la solution optimale en comptera au moins ce nombre-là. Mais peut-être est-il possible d'en mettre davantage ?
En raisonnant, nous pouvons déterminer un nombre maximal de pièces possibles, compte tenu de leur façon de se déplacer. À titre d'exemple, un échiquier comptant 8 × 8 = 64 cases, on peut d'ores et déjà poser que le nombre maximal de pièces que l'on pourra poser ne sera pas plus grand que soixante-quatre.
Le but du jeu est donc d'approcher de la solution par un encadrement de plus en plus serré. Si vous avez réussi à placer (au hasard) six reines sur l'échiquier, et que vous avez trouvé un raisonnement solide vous indiquant qu'il n'est pas possible d'en mettre plus de douze, alors la solution optimale est quelque part entre six et douze.
Il s'agit alors de continuer à progresser, en cherchant une solution valide avec sept reines ou plus, ou bien un raisonnement prouvant qu'il n'est pas possible d'en mettre plus de onze, ou moins. En affinant ainsi, vous finirez par faire coïncider les deux : si vous avez une solution utilisant 𝓃 reines, et que vous montrez par le raisonnement que vous ne pouvez pas en mettre plus que ce même 𝓃, bingo !, vous avez une solution optimale 
Bien sûr, vous pouvez procéder de n'importe quelle manière. Néanmoins, je vous conseille ici – et c'est dans cet ordre que je donnerai les indices – de commencer par chercher combien de pièces vous allez essayer de placer, avant de tenter de les placer, histoire de gagner en efficacité.
Le problème des tours est le plus simple. La tour, en effet, se déplace aux échecs d'autant de cases qu'elle le souhaite, mais en restant toujours sur la même ligne ou sur la même colonne. Une tour située dans un coin, par exemple, pourra atteindre en un seul déplacement n'importe quelle case de l'un des deux bords rejoignant ce coin, mais aucun autre.
Indice concernant le nombre maximum de tours possible
Combien peut-on mettre de tours sur une seule ligne ?
Indice concernant la façon de placer ces tours
Vous n'avez pas le droit de les placer sur une même ligne, ni sur une même colonne. Commencez dans un coin, et avancez simplement.
Solution du problème des tours
Un plateau d'échec comporte huit lignes. Il est impossible de placer deux tours sur la même ligne, faute de quoi chacune pourrait prendre l'autre. En conséquence, il n'est donc pas possible de placer plus de huit tours sur le plateau.
Il y a cependant de multiples manières de parvenir à en placer huit, mais la plus simple reste d'occuper la diagonale principale. Placez la première tour dans un coin, puis chacune des suivantes sur la ligne et la colonne suivante, de cette manière.
Mais, comme je l'ai dit, il ne s'agit ici que d'une petite partie du problème. Même en conservant les tours comme unique pièce disponible, nous pouvons envisager de changer de plateau. Pourquoi rester sur un échiquier, en effet ? Le jeu de Go, par exemple, admet des plateaux de diverses tailles, qui pourraient tout à fait être réutilisés ici (j'avais déjà évoqué ça). On pourrait d'ailleurs aussi bien envisager des plateaux, non pas carrés, mais rectangulaires, avec un nombre de lignes différent du nombre de colonnes. Pour les tours, ça ne devrait pas être particulièrement plus compliqué.
Généralisation aux échiquiers rectangulaires pour les tours
Tout fonctionnera de la même manière quelle que soit la taille de l'échiquier : le nombre maximal de tours sera égal au côté du carré (ou à la plus petite des deux dimensions pour un échiquier rectangulaire), et les placer en diagonal depuis un coin sera toujours une bonne manière de les placer, en « empilant » les lignes et colonnes occupées.
Si l'on pose ℓ comme étant le nombre de cases d'une ligne et 𝒸 celui d'une colonne, le nombre maximal de tours que l'on peut placer sur un plateau rectangulaire sera donc min(ℓ, 𝒸).
Mais l'ont pourrait également attaquer des formes plus exotiques et biscornues. Sur un plateau en « forme de U », par exemple, ce que nous venons de voir ne tient plus. Et si le plateau est de forme quelconque, j'aurais plus de mal à vous donner une réponse : comme mentionné plus haut, il ne s'agit plus seulement d'un jeu, mais d'un véritable problème de recherche (et je n'ai pas encore eu l'occasion de consulter l'état de l'art à ce sujet).
L'étape suivante, c'est le fou. Il se déplace lui aussi en ligne droite, d'autant de cases qu'il le veut, mais n'utilise pour sa part que les diagonales(4) : partant d'une case noire, il restera toujours sur une case noire, et partant d'une case blanche, toujours sur une case blanche, sans jamais pouvoir changer.
Premier indice concernant le nombre maximum de fous possible
Au premier abord, on pourrait penser que le problème des fous ressemble comme deux gouttes d'eau à celui des tours, mais ce n'est pas tout à fait le cas. D'abord, ce sont des diagonales et pas des lignes. Combien un plateau compte-t-il de diagonales ?
Deuxième indice concernant le nombre maximum de fous possible
Attention : le plateau a deux dimensions, et il y a deux façons de compter les diagonales. Peut-être que ce qui se passe de l'une des deux façons peut gêner ce qui se passe sur l'autre ?
Indice concernant la façon de placer les fous
Contrairement aux tours, nous pouvons aligner les fous sur une même ligne ou sur une même colonne. Ou les deux.
Solution du problème des fous
Partant d'un coin et en avançant droit vers le coin opposé, on peut compter quinze « diagonales », successivement noires et blanches (ou blanches et noires, selon le coin choisi). Comme on ne peut mettre qu'un seul fou par diagonale, une première estimation indique que le nombre maximal est de quinze fous ou moins.
On peut cependant remarquer que deux de ces diagonales (les deux coins) ne sont constituées que d'une case. Or, si l'on prend le plateau dans l'autre sens (en partant de l'un des deux coins de couleur opposée), ces deux cases sont situées sur la même diagonale (la plus grande, celle du milieu). On ne peut donc pas les utiliser simultanément : occuper l'un des coins interdit d'occuper l'autre, et comme il n'y a qu'une seule case, il n'y a pas de possibilité d'aller ailleurs sur cette même diagonale. Il n'est donc pas possible de placer quinze fous, et le nombre maximal sera au mieux de quatorze.
Une bonne solution pour réussir à placer autant de fous est d'occuper l'un des bords du plateau en entier : cela fait huit fous facilement disposés. Pour en placer six de plus, nous pouvons utiliser le bord opposé, dont seules les deux cases extrêmes sont interdites, comme ceci. Alternativement, on pourra aussi ramener l'un des fous d'un coin vers le coin opposé, pour en avoir sept de chaque côté, comme cela.
Là encore, nous pouvons tenter de changer la taille du plateau, et cela marche relativement bien… dans certains cas.
Généralisation aux échiquiers rectangulaires pour les fous
Tant que le plateau est carré, cette solution peut se reproduire à l'indentique : on peut placer 𝓃-1 fou sur chacun des bords d'un plateau de taille 𝓃×𝓃, ce qui fait donc un nombre maximal de 2×(𝓃-1) fous, correspondant au nombre de diagonales moins un.
En revanche, les choses peuvent se compliquer assez fortement dès que le plateau devient rectangulaire : aligner les fous sur l'un des grands côtés vous empêchera d'exploiter totalement l'autre, plusieurs diagonales pouvant se toucher mutuellement. Il est beaucoup plus intéressant, au contraire, d'utiliser les petit côtés : vous pourrez alors les remplir tous deux entièrement, passant la meilleure solution à au moins 2×𝓃. Selon l'écart entre le nombre de lignes et le nombre de colonnes, des solutions avec encore plus de fous peuvent cependant apparaître, certaines diagonales centrales restant partiellement inoccupées.
Même sur un plateau de forme presque conventionnelle, cela peut donc se corser…
Et, bien sûr, changer de forme de plateau rend de nouveau le problème bien plus complexe.
Passons maintenant au roi ? Plus modeste que les pièces précédentes, il ne se déplace que d'une seule case à la fois ; ce déplacement pouvant se faire dans toutes les directions. En d'autres termes, chaque roi peut atteindre n'importe laquelle des huit autres cases d'un carré de neuf par neuf dont il serait le centre.
Premier indice concernant le nombre maximum de rois possible
Chaque roi se déplace avec son carré d'interdiction autour de lui. Mais peut-être que neuf cases sont un peu trop ? Après tout, rien n'empêche qu'une case interdite le soit à cause de plusieurs rois…
Deuxième indice concernant le nombre maximum de rois possible
Réduisez la taille, on a dit Combien de rois peut-on placer dans un carré de deux par deux ?
Indice concernant la façon de placer les rois
C'est assez simple, en fait : vous avez dû découper le plateau en cases plus petites que le carré d'interdiction autour d'un roi ? Il vous suffit de faire en sorte que les rois soient placés de façon assez régulière pour ne pas se menacer entre eux.
Solution du problème des rois
Il ne peut pas y avoir plus d'un roi par carré de quatre cases. Comme le plateau peut être découpé en seize carrés de cette taille, nous aurons donc, au maximum, seize rois.
Il suffit alors de les placer de manière régulière, toujours sur la même case du carré, pour qu'ils ne se menacent pas entre eux, comme ceci.
Généralisation aux plateaux quelconques pour les rois
Découper le plateau en carrés de deux par deux n'est toujours ce qu'il y a de plus pratique, selon la taille et la forme du plateau, mais placer les rois régulièrement, en commençant par un bord et en laissant une case vide dans chaque direction avant de placer le roi suivant, donne toujours de bons résultats (optimaux, ça, c'est à voir).
En pratique, un plateau carré présente deux possibilités : soit le nombre de cases par ligne est pair, soit il est impair. S'il est pair, comme sur un plateau de 8×8, le placement régulier décrit ci-dessus laissera toujours une ligne et une colonne vides. Par conséquent, il sera possible de retirer ces zones vides sans retirer de roi : le plateau ayant exactement une ligne et une colonne de moins présentera donc exactement la même solution optimale.
Sur un plateau carré de taille 𝓃, on peut donc placer 𝓃²∕4 rois (𝓃² correspondant au nombre de cases, ce que l'on divise ensuite par la taille de notre quadrillage) si 𝓃 est pair, et (𝓃+1)²/4 si 𝓃 est impair.
Le cavalier, pour sa part, est un peu différent des autres, dans la mesure où son mode de déplacement est assez particulier : il se déplace « en L », avançant de deux cases dans une direction (verticale ou horizontale), puis d'une case dans l'autre (ou l'inverse, ce qui revient au même). Il s'agit d'une pièce « sauteuse », c'est-à-dire que seule la case d'arrivée compte : les pièces étant éventuellement situées sur le trajet sont ignorées et ne seront pas touchées.
Premier indice concernant le nombre maximum de cavaliers possible
Le nombre maximal possible de cavaliers sur un échiquier est en fait assez élevé. Beaucoup plus que pour les autres pièces.
Deuxième indice concernant le nombre maximum de cavaliers possible
Observez attentivement les couleurs des cases que le cavalier emprunte. Ne pourrait-on pas en tirer une conclusion intéressante ?
Le fait qu'il n'y ait pas d'indice sur la façon de placer le plus de cavaliers possible est peut-être en fait un indice également : une fois que vous connaissez le nombre maximal avec certitude, la façon d'y arriver est évidente
Solution du problème des cavaliers
Un cavalier partant d'une case noire arrive toujours sur une case blanche, et réciproquement. Comme les cases vont par paire (il y a autant de cases noires que de cases blanches, on peut donc les associer deux à deux), il suffit d'occuper toutes les cases d'une même couleur, comme ceci, pour placer un maximum de trente-deux cavaliers sur le plateau.
Généralisation aux plateaux quelconques pour les cavaliers
Quelle que soit la taille du plateau, occuper toutes les cases d'une même couleur fonctionnera. Cependant, notez que certains plateaux carrés ont un nombre de cases impair : dans ce cas, les cases ne se correspondent plus deux à deux, et il faudra bien évidemment choisir la couleur ayant le plus grand nombre de cases, histoire de profiter de la case esseulée pour placer un cavalier de plus.
Cela doit pouvoir également s'appliquer plutôt bien aux plateaux de forme quelconque (où la différence de nombre de cases entre les deux couleurs peut cette fois être bien plus importante), mais ce n'est qu'une conjecture de ma part. On peut par ailleurs noter que, lorsque la forme du plateau brise les associations deux à deux, ça risque de beaucoup se compliquer…
Toutes les autres pièces ayant été examinées, reste maintenant à s'occuper de cette redoutable reine(5)… elle combine, pour sa part, les déplacements de la tour et du fou, pouvant bouger d'autant de cases qu'elle le désire aussi bien en ligne ou en colonne qu'en diagonale.
Indice concernant le nombre maximum de reines possible
La reine se déplace comme une tour et comme un fou. Nous avons déterminé le nombre maximal de tours et le nombre maximal de fous possible. Peut-on réutiliser ces informations ?
Indice concernant la façon de placer les reines
C'est assez délicat ici, dans la mesure où ce n'est pas régulier. Une tactique possiblement efficace peut être de placer une reine de moins que le maximum, puis de chercher les positions, pour la dernières, dans lesquelles une seule autre reine sera en échec. On peut alors essayer de déplacer celle-ci, et ainsi de suite.
Solution du problème des reines
Ce problème mathématique est assez connu : le but du jeu est de placer huit reines sur le plateau. Non seulement c'est possible, mais il existe un certain nombre de possibilités. Je suis parvenu à retrouver ces trois-ci en utilisant mon outil, mais Wikipédia nous indique qu'il y en a douze, aux rotations et symétries près.
Généralisation aux plateaux quelconques pour les reines
Placer, sur un plateau carré donné, autant de reines que l'on y plaçait de tours est a priori toujours possible à partir du moment où le plus petit côté du plateau fait plus de trois cases. En revanche, la façon de les placer est souvent assez délicate…
Même pour le plateau carré, la résolution de ce problème est déjà assez complexe quand le nombre de cases n'est pas fixé à l'avance. Alors, bien sûr, passer aux plateaux de forme quelconque rend les choses encore moins pratiques. Là encore, il faudrait consulter l'état de l'art, mais le problème général est loin d'être résolu. Il y a de quoi occuper les chercheurs
Si vous avez réussi toutes ces épreuves (y compris la partie « preuve » pour chacune d'elle, bien sûr) sans regarder la solution, mes félicitations Mais ce n'était qu'un début. De nombreux autres problèmes de ce genre, déjà résolus ou non, attendent votre sagacité. N'hésitez pas à consulter le site de Maths à modeler, où quelques autres vous seront proposés.
En particulier, celui appelé « chasse à la bête » m'est assez sympathique. Je ne l'ai pas détaillé ici afin d'assurer le plaisir de la découverte à celles et ceux de mon lectorat qui auront l'occasion de participer à l'un de nos prochains ateliers, mais les personnes souhaitant s'y intéresser de plus près peuvent évidemment me contacter à ce sujet.
Et, bien sûr, si vous voulez vous-mêmes présenter ce problème à d'autres gens, libre à vous : la recherche, c'est aussi le fait de communiquer et de fournir à réfléchir aux autres