Savez vous blanchir un rectangle ?

par **Ben314** » 18 Fév 2010, 11:40

Salut,
Une petite énigme tiré d'un jeux sur ordinateur :
Partant d'un rectangle nxm dont certaines cases sont grisées, on veut entièrement "blanchir" le rectangle en appliquant à des endroits bien choisis un "calque" en forme de croix qui a la propriété d'échanger les couleurs blancgrisé.
Le centre de la croix doit être à l'intérieur du rectangle, mais la croix peut "déborder" du rectangle.

Pour clarifier le problème, voici un exemple :

Les questions :
1) Peut on blanchir un rectangle 4x3 entièrement grisé ? Si oui, combien y-a-t-il de solutions ?
2) Peut on blanchir tout rectangle 4x3 dont certaines cases sont grisées ?
3) Quels sont les rectangles nxm que l'on peut blanchir quelque soit la disposition de départ ?
4) Quels sont les rectangles nxm entièrement grisés que l'on peut blanchir ?

P.S. Ma méthode d'approche utilise un "certain bagage mathématique" et je n'ai pas fini de trouver les réponses au 3) et au 4) mais je pense y arriver...

par **beagle** » 18 Fév 2010, 12:49

c'est très rigolo à faire comme ça déjà sans maths.
Pour les maths, je ne saurais pas le faire,
mes bagages sont plutot un sac de sports, enfin un vieux sac de sport,
mais tu transformes le problème en "matrices" avec des 0 et des 1?

par **Ben314** » 18 Fév 2010, 12:56

beagle a écrit:...mais tu transformes le problème en "matrices" avec des 0 et des 1?

Effectivement...

par **beagle** » 18 Fév 2010, 13:00

ouais, ben je sais pas faire ça moa.
Mais c'est rigolo.
J'attends les fortiches du forum,
j'espère que je pourrais suivre,...

par **beagle** » 18 Fév 2010, 13:23

J'arrive à faire la 1)
enfin le début de la 1)
faut pas pousser non plus

je me demande si je ne vais plus regarder les soluces de la semaine,
et me garder ça pour le TGv la semaine prochaine,

mais je me connais, cela va me travailler mème pendant le boulot de cet après-midi,
je encore ètre bon , tiens,
bon, je dirai que les erreurs c'est à cause de Ben,...

par **Galax** » 18 Fév 2010, 13:37

Premieres reflexions :

1) Appliquer le meme calque 2 fois ne sert à rien
2) L'ordre dans lequel on applique 2 calques n'importe pas

Pour une grille nxm, il existe n.m calques différents (repérés par la position du centre)

Si on appelle transformation l'application de p calques successifs, il y a donc 2^(n.m) transformations possibles (parties d'un ensemble de n.m elements), comme il y a aussi 2^(n.m) grilles différentes au départ, il reste à montrer que chaque transformation est unique, pour conclure que toute grille est blanchissable, mais je n'y crois pas trop ...

par **Doraki** » 18 Fév 2010, 17:24

Qui veut calculer des déterminants de matrices carrées de taille mn sur F2 ?

Ah oui sinon, je crois que déjà sur un rectangle (2m+1) par (3n+2), on a des problèmes.
Heureusement, 4*3 n'est pas de cette forme.

par **ffpower** » 18 Fév 2010, 17:57

J'avais fait cet exercice, mais avec un énoncé plus général, ce qui parait paradoxalement le rendait plus facile à appréhender :we:
Mais en tout cas oui, je confirme que ca revient à résoudre des systemes dans F2..

par **beagle** » 18 Fév 2010, 18:12

je comprends pas pourquoi faut faire ça dans un F2,
c'est pas possible dans un studio ou un pavillon?

par **nodgim** » 18 Fév 2010, 18:13

Je me régalais à l'avance avec cette nouvelle énigme, mais bon, je crois avoir trouvé (trop vite). Sans faire appel aux matrices ni autres connaissances mathématiques.
Je dirais, sans tout dévoiler, qu'on peut faire avec cette croix la même chose que si c'était une case unique, mais qu'il faut juste, en général, un peu plus de temps pour dégriser un rectangle de taille quelconque.

Je serais même tenté de dire qu'on peut faire la même chose avec n'importe quelle forme de dégriseur.....

par **Doraki** » 18 Fév 2010, 19:11

beagle a écrit:J'arrive à faire la 1)
enfin le début de la 1)
faut pas pousser non plus

C'est parceque l'énoncé de la question 2 donne la réponse au début de la question 1 ^^'

par **Ben314** » 18 Fév 2010, 21:33

Perso, je bute sévère sur la 3...

J'obtient une c.n.s. sous la forme de deux polynômes de F2[X] dépendant respectivement de n et de m et qui doivent être premier entre eux...

Je me demande si la 4 n'est pas plus simple (bien qu'à priori elle me paraissait plus compliqué que la 3...)

par **Imod** » 18 Fév 2010, 23:46

nodgim a écrit:Je me régalais à l'avance avec cette nouvelle énigme, mais bon, je crois avoir trouvé (trop vite). Sans faire appel aux matrices ni autres connaissances mathématiques.
Je dirais, sans tout dévoiler, qu'on peut faire avec cette croix la même chose que si c'était une case unique, mais qu'il faut juste, en général, un peu plus de temps pour dégriser un rectangle de taille quelconque.

Je serais même tenté de dire qu'on peut faire la même chose avec n'importe quelle forme de dégriseur.....

Il y a en effet une solution dans le cas général ( pour les questions 1 et 4 ) , quelle que soit la forme de départ ( même avec des angles , des trous ou plusieurs composantes connexes ) et quel que soit le dégriseur . Mais la solution n'est certainement pas simple même si elle est très courte et ne demande pratiquement aucune connaissance mathématique ) .

Quelques indices :

1°) Oublier les matrices et les petits appartements .
2°) Penser plutôt en termes de graphes .
3°) J'ai déjà posé le problème et sa solution sur le site , sous une forme un peu différente .

Bon courage !!!

Imod

par **ffpower** » 19 Fév 2010, 10:13

Ca a l'air fort..Peut tu préciser ce que tu entends par "quel que soit le dégriseur"? Faut quand même un minimum de condition, ne serait ce que l'on ait pas juste un dégriseur vide..

L'exo que je connaissais moi était le suivant :
On a n ampoules, numérotées de 1 à n, toutes éteintes
On a n interrupteurs, numérotées de a a n. Chaque interrupteur change l'état "allumé/éteint" de certaines ampoules
On suppose que :
-L'interrupteur i agit au moins sur l'ampoule i
-Si l'interrupteur i agit sur l'ampoule j, alors l interrupteur j agit sur l ampoule i

Alors il est possible d'allumer toutes les ampoules en même! (Plus tout a fait sur de l exactitude de l énoncé, je vérifierai tout a l heure )
Cet exercice s'il est juste répond a la question 4
Par contre, il ne permet pas de répondre à la question 3
Et les hypotheses sont un peu contraignantes pour généraliser a d autres types de dégriseur. Par exemple, dans une autre version du jeu, le dégriseur consiste à changer la couleur de toutes les cases adjacantes a la case sur laquelle on clique, mais ne change pas la couleur de la case cliquée elle-même. Cette version là ne rentre pas dans mes hypotheses. Donc l'énoncé d'Imod a l'air plus général dans ce contexte.. :)

par **Ben314** » 19 Fév 2010, 10:28

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...

par **nodgim** » 19 Fév 2010, 16:38

Oh! j'ai loupé la contrainte de la case du milieu de la croix qui doit rester dans le rectangle..
ça change tout

par **Imod** » 19 Fév 2010, 19:05

ffpower a écrit:Peux-tu préciser ce que tu entends par "quel que soit le dégriseur"? Faut quand même un minimum de condition, ne serait ce que l'on ait pas juste un dégriseur vide...

Tu as raison , j'ai un peu trop suivi le mode humoristique proposé par certains , que je ne citerai pas par courtoisie :ptdr:

Il me semble qu'on peut supposer que le dégriseur n'est pas vide , qu'il contient la case fatidique et qu'il est symétrique par rapport à celle-ci ( ou bien on autorise les rotations du dégriseur autour de la case ) . Dans ces conditions le problème est équivalent à celui des ampoules que tu évoques ( il suffit de l'interpréter en terme de graphe ) .

Imod

par **ffpower** » 19 Fév 2010, 19:57

Ok lol. On aura donc de quoi s'occuper avec l'autre dégriseur que j'ai proposé alors :)

En tout cas ta soluce graphe m'interessera. Car ma soluce ( qui semble etre aussi celle de Ben ) avec les matrices dans F2 n est pas évidente. D'ailleurs j'ai pas reussi a la retrouver quand j ai cherché tout a l heure :happy2:

par **Imod** » 19 Fév 2010, 20:22

Inutile de vous laisser poireauter plus longtemps :we:

Voici le lien vers le problème évoqué ( c'est un peu long à lire , personne n'a fait une synthèse :marteau: )
pseudo-défi

Il faut lire l'énigme comme un problème de graphe en oubliant l'habillage fantaisiste :zen:

Imod

PS : C'était à l'époque des défis :cry:

par **Ben314** » 19 Fév 2010, 20:23

Moi aussi, ta soluce m'interesse, vu que... je cherche depuis un petit moment (avec les graphes et pas avec les Z/2Z) et que je suis sec (pour le moment)
Par contre, s.t.p., met la temporairement "en blanc", j'ai pas encore abandonné...

Savez vous blanchir un rectangle ?

Savez vous blanchir un rectangle ?

Qui est en ligne