Savez vous blanchir un rectangle ?

[Ben314]

.. Car ma soluce ( qui semble etre aussi celle de Ben )...

Tout à fait thierry, tout à fait,...
Enfin, sauf que ma soluce (avec des Z/2Z), et ben... je l'ai toujours pas trouvé (ni pour le 3) ni pour le 4))....
En fait je suis plutôt en train de chercher dans la "voie d'Imod" i.e. avec un graphe...

[nodgim]

Entre le rectangle entièrement gris et le rectangle entièrement blanc, il y a 2^12 combinaisons différentes, selon la couleur de chaque case.
Le dégriseur a lui aussi 12 positions différentes, identifiées par la position de sa case centrale. Selon l'action ou non du dégriseur de chacune de ses positions, On a 2^12 possibités d'actions.
Or, il est clair que certaines configurations sont impossibles à obtenir avec le dégriseur. Par exemple, à partir du rectangle tout gris, il est impossible d'obtenir une configuration avec une seule case blanche. Donc, à contrario, certaines configurations sont donc possibles de 2 ou plus manières possibles (principe des tiroirs).
Il est à remarquer que le scénario proposé par Ben avec l'effacement du gris en 5 étapes est obtenu quelque soit l'ordre dans lequel on réalise les étapes, et qu'en réalité, la présentation en étapes est un leurre.
C'est à peu près tout ce que je peux dire sur le sujet.
Après quelques essais, il semble que ce soit impossible de dégriser totalement le rectangle.

[Ben314]

...Or, il est clair que certaines configurations sont impossibles à obtenir avec le dégriseur. Par exemple, à partir du rectangle tout gris, il est impossible d'obtenir une configuration avec une seule case blanche...

Si tu parle du dégriseur en "croix", ce n'est pas si clair que ça...

En fait, pour un rectangle 3x4, toutes les config. sont réalisable (et, évidement, il n'y a qu'une seule solution)
Ce n'est par contre pas le cas par exemple pour un 3x5 et, plus généralement, pour un nxm où n=1 modulo 2 et m=2 modulo 3 (ou le contraire) mais ce n'est pas une C.N.S., par exemple pour le n=m=4, la grande majorité (15/16) des configs. sont non réalisable

[nodgim]

D'accord. Mon problème est que je ne sais pas quel code utiliser (quelles positions de croix) pour obtenir un résultat donné.

[Ben314]

Bon, je vient (enfin) de résoudre "le problème des ampoules" (en fait avec des matrices à coeff dans Z/2Z plutôt que des graphes, mais ça me semble quasi identique).
Cela permet effectivement de répondre par l'affirmative à la question 4) avec tout "dégriseur" dégrisant le "point de base" (celui qui doit rester dans le rectangle) et symétrique par rapport au point de base.

Par contre, je ne suis pas totalement persuadé du résultat dans le cas ou le dégriseur est non symétrique mais qu'on autorise les rotations du dégriseur autour de la case : cas présenté par Imod mais entre parenthèses...

[Imod]

Par contre, je ne suis pas totalement persuadé du résultat dans le cas ou le dégriseur est non symétrique mais qu'on autorise les rotations du dégriseur autour de la case : cas présenté par Imod mais entre parenthèses...

Après réflexion , moi non plus :marteau:

Imod

[Doraki]

Imod précise bien dans son post qu'il a une réponse uniquement à la question 4).

Pour la 3), il est par exemple clair qu'on ne peut pas blanchir un rectangle 1x2 dont une seule des deux cases est grisée.
Pour le moment, (toujours pour la 3) j'ai des conditions du type : C'est O.K. quelque soit la config. de départ lorsque :
m=1 et n-1 modulo 3
m=2 et n-1 modulo 2
m=3 et n-1 modulo 3
m=4 et n-1 modulo 5
m=5 et n=0 ou 4 modulo 6
m=6 et n-1 modulo 9
sauf que j'ai pas de formule générale (en existe t'il une ?)

Je me penche sur la 4) en essayant d'utiliser les indics. de Imod...

P.S. : Si Imod à raison (ce dont je ne doute pas), je trouve ça amusant que les réponses et les méthodes aux questions 3) et 4) soient aussi différentes...

Autant regarder l'ensemble A des couples (n+1,m+1) tels que les rectangles n*m posent problème.

Si (n,m) est dans A alors (a*n,b*m) aussi pour tout a et b.
Si (n,m) est dans A alors (m,n) aussi.
Pour tout n il existe m tel que (n,m) est dans A.

Tout ça pour dire que A est "engendré" par une famille infinie.
J'ai regardé pour n <= 23, on y trouve
(2,3) (5,5) (7,9) (11,31) (13,63) (15,17) (17,17) (19,513) (21,65) (23,2047)

Bon y'a sans doute des trucs à dire sur les puissances de 2.

[Ben314]

Je sais pas si tu procède comme moi avec des polynômes à coeff dans Z/2Z : voir ce post qui me donne :
On peut montrer que et donc que, lorsque on a .
On en déduit que
et, plus généralement, que :

Ce qui permet de ramenner le problème à la recherche des couples (n,m) formés d'entier impairs (i.e. le seul "générateur" utile contenant un nombre pair est (2,3)).
Pour les couples (m,n) qui ne sont pas de la forme (2a,3b) ou (3a,2b), j'ai aussi cette condition :
tels que où désigne la cloture algébrique de
Qui est sans doute liée aux polynômes cyclotomiques sur mais je ne domine pas super bien le sujet...

Si tu veut faire des "essais" avec mapple ou autre, les deux algo. trés rapides de calcul des polynômes que j'ai sont :
1) et
2) avec la "convention"

[Doraki]

Si je comprends bien, pour chaque paire (x,x+1) dans la clôture algébrique de F2, on obtient une paire (n,m) supplémentaire ?

P(n-1) a X (resp. X+1) en facteur si n = 2k (resp. n = 3k),
ce qui donne le couple (2,3)

P(n-1) a X²+X+1 en facteur si n = 5k,
ce qui donne le couple (5,5)

P(n-1) a X^3+X+1 (resp. X^3+X²+1) en facteur si n = 9k (resp. n = 7k),
ce qui donne le couple (7,9)

Et ainsi de suite...

en fait il suffit de mesurer la période des suites Ux définies par
Ux(0) = 0 Ux(1) = 1 Ux(n+1) = x*Ux(n)+Ux(n-1) ?

Et est-ce qu'en prime le degré du polynôme minimal donne les dimensions du noyau des morphismes dont on parlait au début ?

[Ben314]

Oui, c'est exactement ça (modulo le fait que quand tu parle de "la période des suites Ux définies par..." je pense que tu parle évidement de la suite modulo un polynôme irréductible fixé)

Si tu veut les "étapes manquante" pour en arriver à ces conditions, ce n'est pas super compliqué :

On part d'un rectangle dont certaines cases sont grisées et on note les vecteurs colonnes correspondant aux cases grisées (1=grisé, 0=non grisé).
Dans l'exemple de départ :
On note aussi les vecteurs colonnes correspondant aux centres des croix que l'on va "appliquer" à la grille.
Dans la soluce de départ : (5 étapes -> 5 '')
On constate que l'application des croix transforme la colonne qui au départ vaut en où est la matrice entièrement nulle sauf sauf sa diagonale et les cases au dessus et en dessous de la diagonale qui contiennent des (en convenant que ).
On veut rendre tout les nuls et sela impose de prendre




où la suite de polynômes est définie par et
Le problème se ramène alors à trouver tel que c'est à dire tel que :

On en déduit qu'il y a une solution quelque soit la disposition de départ si et seulement si est inversible, c'est à dire si et seulement si est premier avec le polynôme caractéristique de qui s'avère (aprés un mini calcul) être

Par rapport à ta dernière question :

Et est-ce qu'en prime le degré du polynôme minimal donne les dimensions du noyau des morphismes dont on parlait au début ?

Je pense que tu parle du morphisme qui à une matrice nxm (correspondant au centre des croix) associe la matrice nxm des modifications que l'application de ces croix produit. Dans ce cas, il me semble que son noyeau est trés fortement lié à celui de la matrice et je pense que ce dernier est lié à la nature du .
Je regarderais bien, dans un cadre trés général, le lien entre le noyeau de P(A) et le pgcd(P,Q) où Q est le polynôme caractéristique de A [peut-être faut il prendre pour Q le polynôme minimal ? dans le cas ou le pgcd=1, cela ne change rien]

P.S. Concernant la suite de polynômes, il semble assez clair (comme tu le suggérais dans ton post concernant l'ensemble A) qu'il vaudrait mieux travailler avec la suite régie par la même récurence mais d'amorce .
En plus, dans se cas, si on "inverse" la récurence on a , qui donne pour les négatifs

P.S.2 : En fait, pour reprendre ce que tu dit, si est un couple de (cloture algébrique de ) et si on prend tels que et alors les ordres n et m de et fournissent un des couples de A.
Le problème est de savoir si on peut dire quelque chose de ces ordres ?
Je me demandais s'il ne fallait pas regarder où "vivent" x,y et z (i.e. dans quel avec ) et voir si on en déduit quelque chose...

[Doraki]

pour toute paire (y,z) de la clôture algébrique de F2 vérifiant y+z+yz+y²z+yz² = 0, on a des valuations périodiques du plan (y^a*z^b) qui donnent des coloriages qui ne font rien.

C'est marrant de voir comment à chaque point de la courbe y+z+yz+y²z+yz² dans la clôture algébrique de F2 il correspond une taille de rectangles où le morphisme de coloriage n'est pas inversible.

J'imagine que ça devrait se généraliser à toutes les formes et dans un truc à un nombre quelconque de dimensions.