une propriété du problème des tours

Publié le par jö

Rappel : le problème bien connu des 8 reines impose que leur placement sur un échiquier soit tel que qu'aucune d'elles ne soit menacée par aucune des autres (il y a 92 solutions, symétries  mises à part).

Je vais étudier une propriété d'une variante de ce problème (problème des j tours) : soit un tableau de j par j cases, j>1 sur lequel on place j tours de manière qu'aucune d'elles ne soit menacée par aucune des autres. On numérote la case en bas à gauche par 1 et les autres par la règle : le numéro d'une case à droite ou au-dessus d'une case numérotée n est (n+1)%j.

Exemple avec j=6
0 1 2 3 4 5
5 0 1 2 3 4
4 5 0 1 2 3
3 4 5 0 1 2
2 3 4 5 0 1
1 2 3 4 5 0

Je somme dans S le numéro inscrit sous chacune des tours. Je vais montrer par récurrence que S = m j où m est le nombre de tours situées strictement au dessous de la diagonale principale, celle qui est composée de 0, (ici 4+1+5+2+2+4=18 et il y a 3 tours strictement sous la diagonale principale):

0 1 2 3 4 5
5 0 1 2 3 4
4 5 0 1 2 3
3 4 5 0 1 2
2 3 4 5 0 1
1 2 3 4 5 0

Pour j=2, il y a 2 solutions : S1=0 (m=0) et S2=2 (m=1)-> Ok
Pour j=3, il y a 6 solutions : S1=0 (m=0), S2=S3=S4=S5=3 (m=1), S6=6 (m=2)-> Ok

Je l'admets pour j c'est-à-dire que S_j=m j pour toutes les dispositions convenables de j tours dans ce type T_j de tableau :

0 1 ...     j-1
j-1 0 1 ...   j-2
.   .     .
.     .   .
.       0 1
1 ...     j-1 0

Quand je cherche à savoir ce qui se passe avec j+1 tours dans ce type T_{j+1} de tableau :

0 1 ...     j-1 j
j 0 1 ...   j-2 j-1
j-1 j 0 1 ... j-3 j-2
.   . .   . .
.     . . . .
.       . 0 1
1 ...     j-1 j 0

je distingue 2 parties : la partie verte correspondant au passage de j à j+1 et la partie non-verte à mettre en correspondance avec ce qui a été vu pour T_j et dans laquelle je vais garder les j tours bien placées : je conclus au passage sur la seule position possible (case numérotée j de la partie verte [valeur : j] ) de l'unique tour à ajouter  pour passer d'une disposition convenable sur T_j à une disposition convenable sur T_{j+1} car toutes les autres colonnes/lignes sont déjà occupées.

Au niveau des numéros dans la partie non-verte de T_{j+1}, ce qui correspond à la partie triangulaire inférieure de T_j reste inchangé, tandis que les numéros de la diagonale principale de T_j passent de 0 à j [valeur : j] et enfin, dans ce qui correspond à la partie triangulaire supérieure de T_j, les numéros perdent une unité [valeur : -1].

Au niveau des positions des tours, je note d le nombre de tours sur la diagonale principale de T_j. J'ai donc partitionné l'ensemble des j tours de T_j en 3 sous-ensembles : m tours dans la partie triangulaire inférieure, d tours sur la diagonale et j - (m+d) tours dans la partie triangulaire supérieure et la somme fait bien j.

Le passage de S_j à S_{j+1} impose donc une mise à jour
  • pour les d éléments diagonaux dans T_j [rappel valeur : j],
  • pour les j - (m + d) termes de la partie triangulaire supérieure dans T_j [rappel valeur : -1] et
  • pour la dernière tour ajoutée dans T_{j+1} [rappel valeur : j] soit
S_{j+1} = S_j + d j + ( j - (m+d) ) (-1) + j = (m+d) (j+1)

car S_j = m j. Je viens déjà de prouver que S_{j+1} est divisible par j+1.
En fait, je viens également de prouver la propriété car la somme m+d est effectivement le nombre de tours strictement sous la diagonale principale de T_{j+1}.

précision complémentaire : la démonstration est valide car la propriété prouvée pour T_{j+1} est prouvée pour TOUS les tableaux construits à partir T_j (et en l'occurrence ils sont au nombre de 1).

Publié dans mathblog

Commenter cet article