Amusette "classique"

[Ben314]

Une petite amusette sans grande dificulté pour ceux qui savent par quel bout s'y prendre (tirée d'un exo. de la section "lycée")
Sur un quadrillage 8x8, on a disposé des pions du type "Othello Reversi", c'est à dire avec une face noire et une face blanche. Au départ, les couleurs des faces sont disposées comme les case d'un échiquier (alternance horizontale et verticale de noir et de blanc)
Sur ce quadrillage, on s’autorise à retourner :
- Soit tout les pions d'une même ligne.
- Soit tout les pions d'une même colonne.
- Soit tout les pions d'un même carré 2x2 contenu dans le quadrillage 8x8.

Question : quelle sont les dispositions que l'on peut obtenir suite à une série de retournement et lesquelles est-il impossible d'obtenir (par exemple, peut on mettre tout les pions coté noir ? tous sauf un ? avoir un carré 3x3 noir et le reste blanc...)

Même question si au départ le quadrillage fait 8x9 ou bien 9x9.

[beagle]

J'aperçois ce défi il y a quelques minutes.

Mettre tout en noir = oui fastoche.

sauf un , je dirais à priori non pour le 8x8, enfin j'ai juste mis un 4x4, car tout marche de paire, donc se retrouver à former du 1 je ne vois pas comment.Mais j'ai pas réfléchi non plus.

[beagle]

a priori en changeant une colonne sur deux on crée des rangées identiques, reste à les changer une sur deux pour avoir la couleur que l'on veut.
Ceci en pair x pair comme en pair x impair comme en impair x impair.

Pour avoir un reste de 1, impossible avec le pair x pair, donc 8x8 non pas possible.
Donc si Ben propose du 8x9 et du 9x9 c'est que une seule des 2 grilles permet le reste à 1,
alors disons que 9x9 étant impair et 8x9 étant pair, c'est le 9x9 qui restera avec du 1.

[beagle]

le 9x9 pourra faire du 1, mais peut-ètre aussi le 8x9 finalement.
ah zut alors,
en 5x5 on termine en quelques essais en 0 ou 3 qui est 2 aussi (car 5-3).

[beagle]

ou alors on ne peut pas faire 1 si ça se trouve.
en 5x5 on fait des 0 ou 2 ou 3 modulo 5 peut-ètre

ben non car si 3 dans un carré de 4 cela fera ton 1 beagle, va plutot te coucher.

[beagle]

bon alors j'arrive à faire du 1 avec le 3x3.
That's mon niveau , le 3x3!

[LeJeu]

Salut Ben,

Pour une fois que les réponses ne fusent pas en 5 minutes, j'ai le temps de penser et de rédiger !

Une petite amusette sans grande dificulté pour ceux qui savent par quel bout s'y prendre (tirée d'un exo. de la section "lycée")

Pour sûr, ça sent la parité , la parité du nombre de faces noires est un invariant par les 3 transformations ligne, colonne ou carré .

Question : quelle sont les dispositions que l'on peut obtenir suite à une série de retournement et lesquelles est-il impossible d'obtenir (par exemple, peut on mettre tout les pions coté noir ? tous sauf un ? avoir un carré 3x3 noir et le reste blanc...)

Donc on a déjà des réponses faciles : au départ on a autant de noir que de blancs, en quantité paire, donc "tous les pions coté noirs" PEUT être possible," sauf un" est impossible, un carré de trois sur trois est aussi impossible!

Mais comment montrer le chemin quand c'est 'possible' et que ce passe t'il vraiment quand c'est impossible ?

Commencons par la fin :

Même question si au départ le quadrillage fait 8x9 ou bien 9x9.

Regardons pour un quadrillage de taille impair: pas de problléme de parité, il faut juste montrer que le possible sest faisable

J'illustre mon propos par un cinq sur cinq : en fait on peut changer la couleur de toutes les cases de façon indépendante
Voila une façon de faire : en rose la zone que l'on veut traiter, en bleu les cases que l'on retournent , en jaune la case cible ; on balade le carré bleu de droite à gauche et de haut en bas et on inverse suivant ce que l'on veut dans le carré jaune en haut à gauche :


pour traiter la colonne qui reste à droite, on superpose les deux figures suivantes, pour au final se retrouver avec juste les deux cases jaunes inversées , en déplaçant ces deux deux case de haut en bas dans la colonne , on positionne toutes les cellules, sauf la dernière qui dépend alors des opérations précédentes


pour traiter la ligne du bas idem

pour la dernière case en bas à droite,ca se fait ainsi en superposantles trois figures:


Revenons à notre carré de coté pair, tout n'est pas possible, regardons de plus près :

J'illustre avec un carré 4 sur quatre , on reprend la technique ci dessus et on essaie d'effacer les croix :


Ca roule du feu de dieu ! on a notre soluce ( tout effacé) mais visiblement il ne nous reste pas beaucoup de degré de libertés n peut juste inverser la dernière ligne et la dernière colonne



C'est donc qu'il existe une contrainte plus forte que la constance de parité pour la figure totale : la contrainte se trouve en fait sur deux lignes ou deux colonnes adjacentes : les huit cases aussi conservent leur parité !

Et si on regarde la figure ci dessus, pour la dernière ligne , de gauche à droite, on a un degré de liberté pour la première case et toutes celles sur la droite s'en déduisent en considérant des paquets de deux
La dernière case elle se calcule en respectant la règle de parité globale

Donc, par exemple, si on essaie de garder la case en haut à gauche de cochée, en remplissant avec la méthode ci dessus, ( ou par n'importe que méthode qui efface le grand carré de taille 4) on aura sur la ligne du bas la nécessité d'une croix dans les deux premières cases, idem pour les 2 premières cases de la dernière colonne, et aussi pour la case en bas à droite

Ca commence par :



et ca se termine par la figure ci dessous et ses variantes en inversant dernière ligne et colonne


On peut aussi donc voir ce qui va se passer avec le carré de trois sur trois, si on essaie d'effacer toutes les croix du carré supérieur alors on va provoquer un changement de parité sur chaque colonne et sur chaque ligne qu'il faudra équilibrer ( ca se fait tout seul ) par 3 croix sur une horizontale, trois en vertical et un une dans le coin en bas à droite


Ou ses variantes.

Le cas 8 lignes sur 9 colonnes est un mixte de ce qui précède, on peut choisir le couleurs sur les 7 lignes de 9 cases cases, la 8 ieme ligne ne présente que la première case comme degré de liberté, les 8 cases qui suivent sont alors déterminées

Pas si fastoche le lycée et puis moi je jouais au morpion...

[Ben314]

C'est effectivement "tout bon".
Pour le truc niveau lycée (ici) il demandait uniquement si on pouvait obtenir comme résultat "une seule case noire" (donc l'argument "global" de parité était suffisant).
Perso, je l'avais fait avec des outils plus compliqués (e.v. sur Z/2Z et notion de dualité d'un s.e.v.) ce qui permet d'avoir le résultat légèrement plus rapidement, mais je pensait que c'était faisable en restant plus pragmatique et... effectivement...

[beagle]

Pas vu que LeJeu avait répondu cette nuit,
Ce matin entre deux trucs j'ai repris, en faisant ceci:

mettre tout de la mème couleur, c'est possible sans contrainte de parité,
on change une colonne sur 2 ce qui synchronise les rangées,
on change une rangée sur deux , tout est de mème couleur.

Pour le 1 tout seul, si on a du impair fois impair, c'est possible facilement ainsi:
on met tout couleur 0 par exemple.
on allume un colonne impaire, puis une rangée impaire,
cela donne donne du 1 sur cette colonne et cette rangée sauf la case intersection repassée à 0.
On a délimité quatre rectangles à zéro qui sont des pairxpair, par paquets de 4 on les allume de 0 à 1,
tout est à 1 maintenant sauf la case intersection qui est restée à 0.

Pour pas impairximpair, pas de possibilité de changer l'ensemble des rectangles délimités par la rangée et la colonne où figurerait le tout seul .Cela ne prouve pas tout bien sur.

[beagle]

c'est encore faux beagle,
les rectangles c'est pas avec pairxpair que tu feras des paquets de 4,
ah là là, c'est pas possible ces réponses balancées rapidement ...
Bon t'as du bol avec le 9x9 , tu vas y arriver.
mais fais un peu attention quand mème!