Peindre à la souris

[Imod]

Un petit jeu qu'un programmateur moyen réalisera aisément .

On considère le dessin d'un échiquier rectangulaire de taille quelconque sur un écran d'ordinateur . Avec la souris on sélectionne un rectangle constitué de cases de cet échiquier et avec un simple clic on inverse les couleurs des cases ainsi choisies .



Comment donner une couleur uniforme à cet échiquier en un minimum de "clics" ?

Imod

[Patastronch]

Je propose E(n/2)*2 transformations rectangulaire pour un échiquier de n x n cases. Soit n transformations si n est pair, sinon n-1 (pour le peindre dans sa couleur majoritaire).

Donc pour l'exemple 3x3, 2 rectangles suffisent pour le repeindre entièrement en noir.

[Patastronch]

Edit : Non en fait rien, je croyais avoir une piste pour prouver la minimalité mais c'était que du vent :)

[Imod]

Je propose E(n/2)*2 transformations rectangulaire pour un échiquier de n x n cases. Soit n transformations si n est pair, sinon n-1 (pour le peindre dans sa couleur majoritaire).
Donc pour l'exemple 3x3, 2 rectangles suffisent pour le repeindre entièrement en noir.

Plus généralement E(n/2)+E(m/2) pour un rectangle nXm avec la stratégie ci-dessous :


Peut-on faire mieux ???

Imod

[Patastronch]

Pour la preuve de minimalité y a une astuce ou c'est bourrin ?

[Imod]

J'ai trouvé une astuce qui tient en deux lignes mais c'est à la sauce Imod donc ça demande confirmation :zen:

Imod

[Imod]

Un indice :id:

Pour uniformiser la couleur d'un côté n du rectangle , pourquoi faut-il au moins E(n/2) clics de souris ?

Imod

[Doraki]

Parcequ'il y a (n-1) changements de couleurs, donc (n-1) bouts de lignes différents à utiliser au moins 1 fois.
Sachant qu'un rectangle peut en contenir au plus 2, il faut donc au moins E(n/2) clics pour rendre un bord uniforme.

Si on veut faire les 2 bords, on a (n+m-2) bouts de lignes, y'en a toujours au plus 2 pris dans un rectangle, et ça nous fait une belle preuve pour montrer qu'il faut au moins E((n+m-1)/2) clics.
Pour E(n/2) + E(m/2) je vois pas tellement de truc pas moche =(.

[Imod]

Parcequ'il y a (n-1) changements de couleurs, donc (n-1) bouts de lignes différents à utiliser au moins 1 fois . Sachant qu'un rectangle peut en contenir au plus 2, il faut donc au moins E(n/2) clics pour rendre un bord uniforme.

C'est sûrement de ma faute mais je ne vois pas ce que tu veux dire :doh:

Imod

[Doraki]

Surement de la mienne aussi.

Si on regarde seulement un bord du rectangle, on voit une bande de n carrés dont la couleur alterne noir/blanc/noir etc... on a n zones de couleurs alternées.

Pour uniformiser une bande, on sélectionne donc des bouts de la bande.
Quand on regarde la frontière entre la sélection et l'extérieur au moment où on inverse les couleurs,
ou bien la frontière départageait 2 zones de couleurs différentes et alors après l'inversion on a uniformisé 2 zones en 1 seule zone;
ou bien la frontière était au milieu d'une zone et alors on sépare une zone en deux nouvelles zones de couleurs différentes (bien sur on va éviter de faire ça)

Le nombre de zones diminue d'au plus 2 à chaque inversion (1 à chacune des 2 extrémités du morceau de bande sélectionnée)
Comme on avait n zones au départ, et qu'on en veut 1 à la fin, il faut bien E(((n-1)+1)/2) clics minimum pour uniformiser la bande initiale.

Ensuite il faut faire le même raisonnement en parallèle sur l'autre bord du rectangle.
En considérant les 2 bandes (initialement en forme de L) comme 1 seule, on arrive à montrer qu'il faut au moins E((n+m-1)/2) clics.

[Imod]

J'ai compris :id:

En fait on a eu la même idée , la bande est constituée de composantes noires ou blanche et chaque "clic" fait disparaître au plus deux composantes et c'est gagné .

Pour la suite on raisonne par l'absurde et en supposant que n est le plus grand côté ( au sens large ) on doit pouvoir montrer que l'un des rectangles "cliqué" traverse l'ensemble de la grille .

Imod

PS: ça fait quand même un peu plus de deux lignes ( mais l'idée est simple ) .

[Doraki]

L'idée de montrer qu'une stratégie minimale comprend un rectangle qui traverse l'ensemble de la grille permettrait de faire un raisonnement par récurrence simple.

[Imod]

C'est bien là l'idée et n'oublions pas qu'un rectangle a deux longueurs :doh:

Imod

[nodgim]

Un modèle du problème:
La grille est présentée sans la couleur des cases. Chaque segment reçoit un pois quand de chaque coté de ce segment il y a une différence de couleur.
Donc au départ tous les segments ont un pois.
Quand on sélectionne un rectangle, tous les segments situés sur le pourtour voient disparaitre leurs pois. Si, en revanche, on sélectionne un rectangle dont le contour comporte des segments sans pois, ces segments voient réapparaitre leurs pois.

[nodgim]

Un modèle du problème:
La grille est présentée sans la couleur des cases. Chaque segment reçoit un pois quand de chaque coté de ce segment il y a une différence de couleur.
Donc au départ tous les segments ont un pois.
Quand on sélectionne un rectangle, tous les segments situés sur le pourtour voient disparaitre leurs pois. Si, en revanche, on sélectionne un rectangle dont le contour comporte des segments sans pois, ces segments voient réapparaitre leurs pois.

On peut aussi dire qu'il suffit de passer une fois et une seule sur chaque segment de la grille pour avoir une couleur unique.
Pour cela, le rectangle qui passe par les bords est le plus efficace.
Imod, tu peux essayer de sélectionner non pas des rectangles , mais n'importe quel polygone, tu n'obtiendras pas de meilleurs résultats.

[Imod]

On peut aussi dire qu'il suffit de passer une fois et une seule sur chaque segment de la grille pour avoir une couleur unique.

Tout à fait d'accord .

Pour cela, le rectangle qui passe par les bords est le plus efficace.Imod, tu peux essayer de sélectionner non pas des rectangles , mais n'importe quel polygone, tu n'obtiendras pas de meilleurs résultats.

C'est sûrement vrai mais je ne comprends pas quel argument tu utilises :marteau:

Imod

[Imod]

On peut aussi dire qu'il suffit de passer une fois et une seule sur chaque segment de la grille pour avoir une couleur unique.

D'accord , ou un nombre impair de fois .

Pour cela, le rectangle qui passe par les bords est le plus efficace.Imod, tu peux essayer de sélectionner non pas des rectangles , mais n'importe quel polygone, tu n'obtiendras pas de meilleurs résultats.

Là , c'est sûrement ma faute mais je ne comprends pas l'argument utilisé :marteau:

Imod

[nodgim]

D'accord , ou un nombre impair de fois .

oui, mais alors il faut multiplier les passages et on n'optimise plus.

Là , c'est sûrement ma faute mais je ne comprends pas l'argument utilisé :marteau:

Imod

Avec le rectangle max qui ne passe pas par la bordure, si a*b est la taille de l'échiquier, le nombre de segments traités est de 2a-2+2b-2. Mais il faudra encore traiter les 4 angles, en 4 fois. Donc au total, 2a+2b en 5 fois.
En 2 fois, on en fait autant avec des rectangles qui prennent toute la longueur ou toute la largeur.
En fait, si on choisit des sélections qui ne prennent pas des lignes entières, il faut s'y prendre en 2 fois au lieu d'une.

[jeancam]

peut etre peut on multiplier à gauche et a droite par des matrices avec que des 1 et des -1
j ai pas encore reflechi

[Imod]

Avec le rectangle max qui ne passe pas par la bordure, si a*b est la taille de l'échiquier, le nombre de segments traités est de 2a-2+2b-2. Mais il faudra encore traiter les 4 angles, en 4 fois. Donc au total, 2a+2b en 5 fois. En 2 fois, on en fait autant avec des rectangles qui prennent toute la longueur ou toute la largeur. En fait, si on choisit des sélections qui ne prennent pas des lignes entières, il faut s'y prendre en 2 fois au lieu d'une.

Désolé je ne suis vraiment pas convaincu par l'argument :triste: Tu te bases sur le fait qu'il faut prendre chaque segment une seule fois alors qu'un nombre impair de fois donne le même résultat avec , pourquoi pas , moins de dépense .

Imod