Le premier problème est beaucoup plus complexe que le second et je ne connais pas de formule générale (i.e. le nombre de Dames f(n) en fonction de la taille n de l'échiquier) ...

f(n)≤f(n+1)≤f(n)+1 :
f(n)≤f(n+1) (i.e. f est croissante), car si on ne peut contrôler l'échiquier de taille n avec k Dames, on ne pourra pas non plus contrôler celui de taille n+1 avec ces k Dames.
f(n+1)≤f(n)+1, car si on peut contrôler avec k Dames l'échiquier de taille n, on pourra considérer que l'échiquier de taille n+1 est constitué du précédent échiquier de taille n muni de ses k Dames complété par une colonne et une rangée qui se coupent en la case X et que si on ajoute alors une Dame sur la case X, l'échiquier de taille n+1 est contrôlé totalement.

n/4<f(n)<n
1. Une Dame sur un échiquier de taille n contrôle au maximum de 4n-3 cases (au centre) si n est impair et un maximum de 4n-4 cases (au centre) si n est pair (voir Séance 1). On peut donc minorer strictement le nombre f(n) par n/4 (ceci montre en outre que la suite (f(n))_n diverge en l'infini).
2. On a f(n+1)≤f(n)+1, et comme f(3)=1, on a f(n)≤n-2. On peut donc majorer strictement le nombre f(n) par n.

Pour n=3, le nombre f(3) est 1. Il est donc faux de dire que f(n) est strictement supérieur à n/3 (si n>2).
Pour n=4, le nombre f(4) est 2. Il est donc faux de dire que f(n) est strictement inférieur à n/2 (si n>2).
Un autre exemple, ...
Pour n=9, le nombre f(9) est inférieur ou égal à 5, comme le montre le tableau suivant
O	O	O	O	O	O	O	O	O
O	O	O	O	O	O	O	O	O
O	O	O	O	O	X	O	O	O
O	O	X	O	O	O	O	O	O
O	O	O	O	X	O	O	O	O
O	O	O	O	O	O	X	O	O
O	O	O	X	O	O	O	O	O
O	O	O	O	O	O	O	O	O
O	O	O	O	O	O	O	O	O
Les "X" désignent les positions des Dames, les "O" désignent les cases vides contrôlées, les "I" désignent les cases vides non contrôlées.
Retour à la page précédente
Retour à l'index