Vider un échiquier

ça me fait penser au problème du solitaire, qu'on peut résoudre je crois en utilisant certains corps finis. Mais ton problème est un peu plus complexe, et à l'heure qu'il est je ne peux malheureusement pas y réfléchir sérieusement, bien que je n'ai pas du tout la prétention de dire que je pourrais apporter un élément de réponse, cela va de soi.

Bonjour,

On peut aussi se demander "quel est le nombre maximal de drapeaux qu'on peut laisser"

On a 2005 = 3x668+1
On peut laisser 668x2x2005 + (2005-668) drapeaux : candidat pour le nb maximal

(en enlevant les drapeux des colonnes d'indice 3,6,9,...,2004 (c'est possible)
et ceux de la dernière colonne de rang 3,6,9...,2004)

Candidat pour le nombre minimal : on enlève les colonnes d'indice 2,4,6,...,2004
et les lignes de rang 2,4,6,...,2004
(il reste alors les cases (i,j) avec i et j impairs

Premier jet sans garantie !

Oump.

pourquoi ne pas laisser un seul drapeau au milieu ?

ahh! désolé, j'avais mal lu le probleme.

Bonsoir, il est rigolo ce problème.

Notons $m_n$ le minimum de drapeaux laissables sur un échiquier $E_n$ de taille $n \times n$ et $M_n$ le maximum de drapeaux laissbles sur le même échiquier $E_n$ (sans mouvement légal).

On trouve :
$m_1 = M_1 = 1$
$m_2 = M_2 = 4$
$m_3 = 2$ ; $m_3 \geq 4$

Petite curiosité : sauf erreur, $M_5 = 24$ (enlever $(3,3)$).

Et comme indiqué par Domi, on montre que $m_n \geq 2$ pour tout $n \geq 2$.

Je vais suivre ce fil avec intérêt.

(Edité : ne pas confondre \leq et \geq, grrrr.)

J'ai l'impression qu'il reste au moins $n$ drapeaux sur un échiquier $n \times n$. Et on peut s'arranger pour qu'il ne reste plus que la grande diagonale.

[La case LaTeX AD]

Peut-être bien... Quelqu'un aurait-il mieux pour des petites valeurs de $n$ ? Moi je n'arrive pas à faire moins !

Je n'ai pas compris comment tu arrives à 2. Après b2;a1;a3;c1;c3 on est bloqué avec 4 drapeaux isolés.

Re

si n=6k+1 alors m(n)<= (3k+1)(2k+1)

( en effet dans ce cas on peut supprimer les colonnes d'indices: 2,3,5,6,..
..(6k-1),6k et dans chacune des 2k+1 colonnes restantes il reste 3k+1 drapeaux)

pour n=2005=6x334 +1 le minimum est donc inferieur ou egal à 1003x669.

candidat moins ridicule que celui que j'avais avancé..

a suivre et bonne nuit les petits..

Bonjour,

peut être une idée :
je pense que l'on peut enlever les lignes 1 et 2 et les colonnes a et b de la manière suivante :
b2,a1,a3,a2,b2,c2,c1,b3 puis d2,d1, puis e2,e1 puis f2,f1 etc... et idem par symétrie b4,a4 puis b5,a5...etc

lorsque tous les drapeaux des lignes 1 et 2 et des colonnes a et b sont enlevés on recommence avec les lignes 3 et 4 et les colonnes c et d.

Cependant, au bout des deux lignes 1 et 2 on ne peut pas directement enlever en entier tous les drapeaux il faut en laisser un. Mais je crois qu'on peut l'enlever au cours du passage des lignes 3 et 4.

Bref on peut enlever en entier les lignes 1 2 3 4 et les colonnes a b c et d.
De proche on proche on retombe sur le problème 5x5.

Merci de me lire. J'espère avoir été compréhensible.

bien vu lionel40, ton idée est la bonne :
on peut enlever une bande de deux colonnes (ou de deux lignes) : b2,a1,a3,a2,b1,a4,b3,a5,b4, ... an,bn-1,bn.
Donc on enlève lignes et colonnes alternativement jusqu'à ce qu'il reste 3 drapeaux, dont on enlève le central. Donc la réponse est : il reste deux drapeaux pour n impair, et on ne peut faire mieux. Pour n pair >2, il reste un rectangle de 2x4=8 drapeaux. Mais peut-on faire mieux ? Il faut donc voir avec n=4.

Bonjour,

j'appelle r le nombre de drapeaux restants à l'issue d'une sequence épuisant les retraits possibles et n le nombre de colonnes et de lignes
les colonnes sont indicées de 1 à n et les lignes de 1 à n (avec n>=3)
une sequence est decrite par une liste de termes (ij) associes aux drapeaux enlevés
il s'agit de determiner m(n) le minimum de r et M(n) le maximum

on a m(3)=2
ex de sequence: (22),11),(33),(13),(31),(23),(21)

et M(3)=4
ex de sequence: (22),12),(32),(23),(21)

rem:au lieu d'enlever des drapeaux,on dessine une grille carrée de n² cases
et on marque d'une croix une case entourée d'un nb pair de cases vides, le jeu s'arrete quand on ne peut plus cocher de case; cela peut donner lieu à un jeu à deux "papier crayon " on coche à tour de role et le dernier qui peut cocher a gagné
d'ou le pb : existe t il une strategie de jeu? et pour corser le jeu on peut partir d'une grille pas forcement carrée!(ne serait ce que rectangulaire, cas interessant)

pour n=4 i me semble que m(4)=3 et M(4)=8

on a r=3 pour la sequence: (22)(11)(13)(12)(21)(32)(31)(43)(34)(42)(14)(23)(33)
on a r=8 pour la sequence:(22)(11)(13)(12)(21)(14)(23)(24)

c'est un petit debut,je persiste à croire qu'il intervient les restes modulo 3
(ou 6) pour n;( quand on flingue les deux premieres colonnes , il se passe des choses quand on arrive en haut!)

Domi, que ce pb ne t'empeche pas de corriger tes copies;)

Oump.

Mais pour pair il n'est pas certain que shunter les colonnes/lignes deux par deux constitue la meilleure stratégie...


Avec cette stratégie, et en terminant le dernier carré 4x4 comme je l'ai indiqué, on arrive à 3 drapeaux restants pour tout n pair>4. J'essaie de démontrer qu'aucune stratégie ne peut laisser 2 drapeaux. (j'en suis presque convaincu pour n=4)

Bonjour,

Je ne crois pas qu'on puisse vider complètement les deux premières lignes/colonnes, il se passe des choses au bout... Mais je pense qu'on peut les vider au "deuxième passage" en entier.

Donc on vide proprement les lignes/colonnes 4 par 4 et non 2 par 2 en partant d'un coin...

exemple: on vide les lignes 1 2 3 4 et en même temps les colonnes 1 2 3 4
        puis on vide les lignes 5 6 7 8 et en même temps les colonnes 5 6 7 8 etc...

Pourquoi ? Que se passe-t en fin de lignes/colonnes ?

exemple : cas 10x10

On commence par vider par le coin en haut à gauche. On vide les deux premières colonnes/lignes comme indiqué dans des posts plus haut.

Je note par un point ce qui est vide et par rien un drapeau.

Au bout des deux colonnes/lignes on obtient:
\fbox {\begin{tabular}{cccccccccc}
.&.&.&.&.&.&.&.&.&. \\
.&.&.&.&.&.&.& &.&. \\
.&.& & & & & & & & \\
.&.& & & & & & & & \\
.&.& & & & & & & & \\
.&.& & & & & & & & \\
.&.& & & & & & & & \\
.& & & & & & & & & \\
.&.& & & & & & & & \\
.&.& & & & & & & &
\end{tabular} }
Je pense qu'on ne peut pas faire mieux. Mais ça c'est faisable.

Ensuite au deuxième passage on arrive à :
\fbox {\begin{tabular}{cccccccccc}
.&.&.&.&.&.&.&.&.&. \\
.&.&.&.&.&.&.& &.&. \\
.&.&.&.&.&.& & & & \\
.&.&.&.&.&.& & & & \\
.&.&.&.& & & & & & \\
.&.&.&.& & & & & & \\
.&.& & & & & & & & \\
.& & & & & & & & & \\
.&.& & & & & & & & \\
.&.& & & & & & & &
\end{tabular} } et là on peut faire en 4 coups : \fbox {\begin{tabular}{cccccccccc}
.&.&.&.&.&.&.&.&.&. \\
.&.&.&.&.&.&.&.&.&. \\
.&.&.&.&.&.&.& & & \\
.&.&.&.&.&.& & & & \\
.&.&.&.& & & & & & \\
.&.&.&.& & & & & & \\
.&.&.& & & & & & & \\
.&.& & & & & & & & \\
.&.& & & & & & & & \\
.&.& & & & & & & &
\end{tabular} } puis 2 coups : \fbox {\begin{tabular}{cccccccccc}
.&.&.&.&.&.&.&.&.&. \\
.&.&.&.&.&.&.&.&.&. \\
.&.&.&.&.&.&.&.& \\
.&.&.&.&.&.& \\
.&.&.&.& \\
.&.&.&.& \\
.&.&.& \\
.&.&.& \\
.&.& \\
.&.&
\end{tabular} }
Puis en continuant on finit les quatres lignes/colonnes et on obtient :
\fbox {\begin{tabular}{cccccccccc}
.&.&.&.&.&.&.&.&.&. \\
.&.&.&.&.&.&.&.&.&. \\
.&.&.&.&.&.&.&.&.&. \\
.&.&.&.&.&.&.&.&.&. \\
.&.&.&.& \\
.&.&.&.& \\
.&.&.&.& \\
.&.&.&.& \\
.&.&.&.& \\
.&.&.&.&
\end{tabular} }
Voilà , sauf erreurs...

[Il serait judicieux de choisir autre chose que '.' qui n'est pas très visible
Je te laisse reprendre ton message suivant. AD]

bonjour,

pardon pour les deux derniers posts qui sont brouillons et inutiles.


GG a bien sûr résolu le problème et tous les cas où n est impair (j'aurais dû mieux lire).

Pour n pair, peut être que la métohde permettant de laisser un ou deux drapeaux autour du dernier carré 4x4 peut permettre de ne laisser que deux drapeaux au total ?..

bonjour,
je n'arrive pas à réduire le cas 4x4 par contre avec le coup de laisser des trous je crois avoir le cas 6x6 :

02 05 07 11 12 10
04 01 06 26 09 13
03 08 27 30 25 24
16 28 29 00 31 21
17 14 34 32 19 22
15 18 00 33 23 20

S'agissant des carrés nxn, on s'oriente vers une réponse du style :

1 si n=1
4 si n=2
3 si n=4
2 sinon

???

bonsoir,
ce que lionel40 a montré avec son carré 6x6, c'est que le min est 2 pour n>4, que n soit pair ou impair. Ce qui reste à montrer c'est qu'il vaut bien 3 pour n=4.

Bonjour

J'arrive un peu après la bataille... Pour l'instant j'essaie d'associer à chaque disposition sur un $4\times 4$ une matrice à coeffs dans $\mathbb F_2$. On pose $a_{i,j} = 1$ si il y a un drapeau, 0 si il n'y en a pas. Pour chaque case $a_{i,j}$ on définit les vecteurs $v_{i,j}$ et $u_{i,j}$ tels que $v_{i,j}(k)=1, \mathrm{\ pour\ } k\in\{j-1,j,j+1\} \mathrm{\ et\ } 0$ sinon et $u_{i,j}(k)=1, \mathrm{\ pour\ } k\in\{i-1,i,i+1\}\mathrm{\ et\ }0$ sinon.

Bon normalement ça nous permet d'avoir, en notant $M$ la matrice correspondante à l'échiquier, que la quantité $ {}^tU_{i,j}.M.V_{i,j}$ nous donne la parité du nombre de drapeaux entourant la case de coordonnées $(i,j)$. On peut donc voir $M$ comme une forme bilinéaire sur $\mathbb F_2^4$.

Maintenant je vais essayer de définir une transformation $F$ qui à une matrice correspondant à une configuration de drapeaux associe une nouvelle configuration en enlevant un drapeau, sous la condition que la case ou on enlève le drapeau vérifie bien la condition de parité. Le plus dur je pense va être de gérer le cas ou le nombre de drapeaux autour est nul...

Avis aux amateurs, je dois y aller

t-mouss