Vider un échiquier
dans Les-mathématiques
Bonjour à tous .
Un problème d'olympiade que je viens de découvrir ( je vous laisse deviner l'année de sa diffusion ) .
On considère un échiquier 2005 X 2005 avec un drapeau dans chaque case . On s'autorise à retirer un drapeau d'une case chaque fois que le nombre de ses voisines contenant un drapeau est pair et non nul ( les voisines d'une case sont toutes les cases ayant un sommet commun avec celle-ci ) . Trouver le nombre minimal de drapeaux que l'on peut ainsi laisser sur l'échiquier .
On peut bien sûr s'interroger sur une généralisation ( pourquoi 2005 ? ) .
Je n'ai pas beaucoup de temps libre en ce moment mais dès la fin de la semaine je serais pleinement avec vous . D'ici là si un GG , Aldo , t-mouss ou autre veut bien s'intéresser au problème ! ( pas trop quand même , laissez-moi une part du gâteau )
J'ai plein d'idées mais pas le temps de les développer .
A bientôt
Domi
Un problème d'olympiade que je viens de découvrir ( je vous laisse deviner l'année de sa diffusion ) .
On considère un échiquier 2005 X 2005 avec un drapeau dans chaque case . On s'autorise à retirer un drapeau d'une case chaque fois que le nombre de ses voisines contenant un drapeau est pair et non nul ( les voisines d'une case sont toutes les cases ayant un sommet commun avec celle-ci ) . Trouver le nombre minimal de drapeaux que l'on peut ainsi laisser sur l'échiquier .
On peut bien sûr s'interroger sur une généralisation ( pourquoi 2005 ? ) .
Je n'ai pas beaucoup de temps libre en ce moment mais dès la fin de la semaine je serais pleinement avec vous . D'ici là si un GG , Aldo , t-mouss ou autre veut bien s'intéresser au problème ! ( pas trop quand même , laissez-moi une part du gâteau )
J'ai plein d'idées mais pas le temps de les développer .
A bientôt
Domi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Domi
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.
Je crains que ton mimimum ne soit pas le meilleur candidat . Pour un échiquier à 9 cases , on peut retirer successivement les drapeaux des cases : b2;a1;a3;c1;c3;c2 laissant ainsi deux drapeaux sur le jeu alors que ta proposition en laisse quatre , on a retiré les colonnes impaires et la ligne paire . Je pense que cette stratégie doit pouvoir s'adapter au grand échiquier . Peut-on faire encore mieux ?
Domi
PS : pour un échiquier de 9 cases le minimum de drapeaux restant est certainement 2 car 1 n'est pas possible ( comment le dernier drapeau retiré aurait-il pu avoir deux drapeaux voisins ? )
oui pour n=3
il se pourrait que la classe modulo 3 pour n ait de l'importance donc..
j'ai répondu tres(trop?) vite et pendant le match lyon asroma je vais avoir le temps de ruminer!;)
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.)
Domi
[La case LaTeX AD]
Domi
Domi
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..
oui, il a l'air diabolique ton pb ! Ca me fait penser au jeu de reversi : chaque case vaut 0 ou 1 : 0 on ne peut pas enlever le drapeau qui s'y trouve, 1 on peut l'enlever. Au départ, une bordure de 0 entourant 2003x2003 1. Chaque fois qu'on enlève un drapeau d'une case 1, les huit (au max) voisins changent d'état (avec les exceptions des drapeaux isolés). Reste à trouver la bonne stratégie
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.
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.
00 04 05 00
03 13 12 06
00 01 11 07
02 10 09 08
Qui dit mieux ?
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.
Pour revenir à la variation proposée par Oumpapah, je propose de montrer que $M_{3k+2} = 4(k+1)(2k+1)$ pour tout $k \in \N$. (inspiré par le cas $k = 1$ / $n = 5$)
Soit $k \in \N$ et $n = 3k+2$.
Sur l'échiquier $E_n$ on retire successivement tous les drapeaux $(a,b)$ tq $a = b = 0$ mod $3$. Il y en a en tout $k^2$.
On constate alors au bout de ces $k^2$ étapes que l'échiquier ne comporte plus que des drapeaux ne comportant qu'un nombre impair de voisins (pour le voir, retirer la bordure de drapeaux externes et "découper" l'échiquier restant en sous-échiquier $3 \times 3$ : on a alors retiré tous les drapeaux "centraux").
Bilan : dans cette configuration, il n'y a plus de mouvement légal disponible, et ainsi $M_{3k+2} \geq (3k+2)^2 - k^2 = 4(k+1)(2k+1)$ (la séquence garantissant cette inégalité étant celle des $(a,b)$ tq $a = b = 0$ mod $3$).
Pour montrer que cette inégalité est optimale, il suffit de montrer que tout séquence comportant strictement moins de $k^2$ coups ne peut pas épuiser les mouvements légaux disponibles.
Raisonnons ainsi :
Soit $k \in \N$ et $n = 3k+2$ et $k' \in \N$ tq $k'<k^2$.
Retirons une nouvelle fois la bordure de drapeaux externes et "découpons" l'échiquier restant en sous-échiquier $3 \times 3$. Comme on l'a vu il y en a $k^2$. Le principe des tiroirs nous garantit alors qu'il existe un sous-échiquier dont le drapeau central reste non-affecté (même nombre de voisins qu'au début, c'est-à-dire 8) par une séquence de $k'$ coups. En effet si tous ces drapeaux centraux étaient affectés par la séquence, cela voudrait dire que la séquence comporte au moins un coup dans chaque sous-échiquier, c'est-à-dire $k^2$, ce qui n'est pas le cas puisque $k'<k^2$ par hypothèse.
Le drapeau central non-affecté fournit donc un mouvement légal supplémentaire, cqfd.
Bilan : $M_{3k+2} \leq (3k+2)^2 - k^2 = 4(k+1)(2k+1)$.
Conclusion : $M_{3k+2} = (3k+2)^2 - k^2 = 4(k+1)(2k+1)$
Et cette formule donne bien (heureusement) les valeurs déjà trouvées pour $M_2 = 4$ et $M_5 = 24$.
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)
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.
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]
je modifie le post précédent :
après "Ensuite au deuxième passege on arrive à "
il faut lire :
..........
....... ..
......
......
....
....
..
.
..
..
Puis
..........
..........
.......
......
....
....
...
..
..
..
Puis on peut alors finir les lignes/colonnes 3 et 4 en entier;
je crains que ce soit lourd à lire...
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 ?..
Le cas du rectangle m X n avec m et n impairs se ramène facilement au cas du carré en éliminant deux par deux les lignes ou colonnes en surnombre . Pour le cas m ou n pair , ça ne me semble pas évident du tout . Par exemple un rectangle 2 X n avec n quelconque ne peut pas se réduire . Je crois aussi comme GG ( mais sans preuve ) que pour le carré 4 X 4 on ne peut pas faire mieux que 3 drapeaux au final .
Pour 3 X 4 , je trouve encore 3 drapeaux avec :
02 05 00 07
04 01 06 00
03 00 09 08
Domi
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
???
le schmilblick a avancé ..et devancé ce que je voulais dire
..
il est vrai que pour n>=4 on peut flinguer les deux premieres lignes et les deux premieres colonnes ce qui permet de se ramener à n=3 ou 4
donc si n est impair no pb le minimum est bien 2 .
et si n est pair ce minimum est au plus 3
je pense que c'est 3 mais il faut le prouver!
et il restera le cas du maximum qui parait interessant.
Oump.
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.
oui , je n'avais pas vu le graphe de lionel pour n=6 ;bien vu!
Oump.
j'ai trouvé un petit moment pour regarder les messages en détail ( uniquement pour le minimum de drapeaux , j'ai à peine le temps de suivre un lièvre , le deuxième attendra ) .
Il est clair que pour un rectangle m X n avec m et n supérieurs à 3 , on peut supprimer 2 lignes ou deux colonnes et le problème se ramène à quelques cas simples :
Pour un rectangle m X n avec m=<n :
1 X n : reste E(n/2)+1 drapeaux .
2 X n : reste 2n drapeaux .
3 X n : le résultat doit dépendre de n , sûrement 2 ou 3 .
4 X n : et suivant doit se ramener aux cas précédents .
Les deux premiers cas ayant un faible rendemement , l'étude de carrés de type 6 X 6 ou autre n'est sûrement pas inutile .
Désolé de ne pas apporter plus d'idées pour l'instant mais je ne suis qu'à moitié avec vous .
Domi
Domi
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
Alors je propose le codage suivant : M(t) est la matrice associée à l'echiquier à l'étape t (a chaque étape on enlève un drapeau). Le coeff (i,j) vaut 0 si il y a un drapeau sur la case (i,j) et 1 si il n'y en a pas. Alors M(t) est vue comme matrice de $\F_2$ et M'(t) est la même matrice, mais considérée comme matrice à coeff dans $\Q$.
Je pose :
$U_1=(1,1,0,0)$
$U_2=(1,1,1,0)$
$U_3=(0,1,1,1)$
$U_4=(0,0,1,1)$
Desormais, si le coeff (i,j) vaut 1 (il y a donc un drapeau en (i,j)), l'opération qui consiste à enlever le drapeau en (i,j) correspond à la transformation suivante, où N représente la matrice associée au nouvel echiquier (sans le drapeau en (i,j)) et $H_{(i,j)}$ la matrice ayant des 0 partout sauf en (i,j) qui vaut 1 : $N=M+H_{(i,j)}$
On obtient désormais la propriété suivante : étant donné la matrice M associée à un echiquier, on dit que $M+H_{(i,j)}$ vérifie P si et seulement si $m_{i,j}=1$, $ ^t U_j.M.U_i=0$ et $ ^t U_j.M'.U_i \neq 0$ (M' représente la meme matrice, mais vue à coeffs dans $\Q$.
On peut aussi reformuler tout ca pour dire : Une matrice M de $\F_2$ est dite "k-cohérente" si il existe $(i_1,j_1),..,(i_k,j_k)$ indices respectivement compris entre 1 et 4, tels que : $M+H_{i_1,j_1}$, $M+H_{i_1,j_1}+H_{i_2,j_2}$,..,$M+H_{i_1,j_1}+..+H_{i_k,j_k}$, vérifient P.
On obtient ainsi les k étapes passant d'un échiquier couvert de drapeaux, à un échiquier ayant k drapeaux d'enlevés.
Il faut donc montrer que la matrice M telle que $m_{i,j}=1$ pour tout couple (i,j) n'est pas 14-cohérente.
Bon ca fait tres charrabia djeloulien X:-( mais bon faute de mieux... et puis c sympa d'introduire des formes bilinéaires sur $\F_2^4$ pour resoudre ce genre de problème (si tant est que ca puisse le resoudre)...8-)
Avis aux grippeux
t-mouss