Colorier un quadrillage avec deux couleurs

[Juzo]

Bonjour à tous,

Dans le double numéro de La Recherche n°537-538, un défi est proposé en lien avec le théorème de Hillel Furstenberg et Benjamin Weiss*.

Considérons un carré régulièrement quadrillé de taille NxN. Il s'agit de placer des points colorés dans les cases en utilisant seulement deux couleurs différentes, et sans former de carré dont les quatre sommets sont de la même couleur et dont les côtés sont parallèles aux bords du quadrillage. On appelle un tel carré un "carré aux coins monochromes".

Voici 4 "jeux" que je vous propose à partir de ce sujet :

Jeu 1 : dans l'image en fin de message, trouver la ou les erreurs (carrés aux coins monochromes) et proposer des corrections simples.

Jeu 2 : proposer un algorithme le plus léger possible qui permet de vérifier si un quadrillage colorié contient des carrés aux coins monochrome

Jeu 3 : proposer la méthode la plus efficace pour chercher "à la main" un grand quadrillage ainsi colorié.

Jeu 4 : proposer le plus grand quadrillage ainsi colorié. C'est le défi donné dans le magazine, qui offre au passage un an d'abonnement au gagnant.

Je suggère de répondre en spoiler et de mettre le numéro du jeu en en-tête


* Le théorème de Hillel Furstenberg et Benjamin Weiss montre qu'il existe une taille N telle que pour tout coloriage du quadrillage NxN (en utilisant toujours deux couleurs), on trouve un carré aux coins monochromes. L'auteur de l'article indique qu'il ne connaît pas ce nombre N... Ce théorème est une extension du théorème à une dimension de Leendert Van der Waerden (qui montre un nombre limite mais ne contient pas sa valeur).

Pavage.jpg

Bonne journée !
-----

[roro222]

Bonjour

 Cliquez pour afficher

Pavage.jpg
A partir de cette configuration de base, solution impossible
Rien que dans le grand carré, quel que soit le coin que j'inverse, je reforme un autre carré

[invite51d17075]

Jeu 1 : dans l'image en fin de message, trouver la ou les erreurs (carrés aux coins monochromes) et proposer des corrections simples

qu'entends tu par "corrections simples" , je suppose qu'il s'git d'inverser deux éléments, mais toutes les inversions sont elles admises ?

[roro222]

Toutes inversions est admise du moment que tu reformes pas un autres carré

[A voir en vidéo sur Futura]

[invite51d17075]

je suppose qu'on a droit à plusieurs inversions à la fois. ?

[roro222]

oui

 Cliquez pour afficher

la configuration proposé par Juzo est insolvable
il faut en proposer une autre
C'est du même genre que les sudokus des grilles possibles et d'autres non

[Juzo]

Bonjour,

Je ne suis pas sûr d'avoir vu toutes les erreurs, par conséquent la grille pourrait bien être insolvable. Je ne l'ai pas revérifiée après avoir posté le message (j'aurais plutôt dû partir d'une grille juste et la modifier).

Une correction simple consiste à changer une couleur ou à inverser les positions de deux couleurs.

Pouvez-vous indiquer en spoiler le nombre de carrés aux coins monochromes que vous avez trouvé et les coordonnées de leurs sommets ?

 Cliquez pour afficher

J'ai repéré deux carrés possibles à corriger avec des corrections simples à priori

[invite51d17075]

Une correction simple consiste à changer une couleur ou à inverser les positions de deux couleurs.

je pensais qu'on ne pouvais faire que des inversions, pas de chgt de couleur d'une seule case.
j'y retourne, fidèle à ma signature.

[invite51d17075]

comme on a deux carrés, il faut à minima autoriser deux chgt , non ?
quelle est la règle exacte ?

[Juzo]

comme on a deux carrés, il faut à minima autoriser deux chgt , non ?

Oui, un changement autorisé par carré carré (inversion de deux couleurs ou changement de la couleur d'une seule case).

[invite51d17075]

suggestion

 Cliquez pour afficher

inversions A2A7 et F9G9

[roro222]

suggestion

 Cliquez pour afficher

inversions A2A7 et F9G9

Non pas bon

 Cliquez pour afficher

Tu va reformer un carré avec les 4 coins marrons A2 F2 F7 A7

[Juzo]

Réponse à la proposition de ansset et à la remarque de roro222 :

 Cliquez pour afficher

La première inversion A2A7 n'est pas correcte. Le carré A2F2F7A7 est ok contrairement à la remarque de roro222 (les sommets A2 et A7 n'ont pas la même couleur), mais le carré A1G1G7A7 est monochrome (4 sommets blancs).

La deuxième inversion F9G9 me semble correcte, c'est l'une des deux corrections que j'avais imaginées.

[roro222]

Oui tu as raison, j'ai fais une erreur de coordonnées dans la précipitation

 Cliquez pour afficher

Pavage1.jpg

Dans cette image, j'ai pas tenu compte de l'autre carré puisque déja la première proposition est fausse

[invite6c250b59]

Jeu 2 : proposer un algorithme le plus léger possible qui permet de vérifier si un quadrillage colorié contient des carrés aux coins monochrome

Sympa

 Cliquez pour afficher

tirer au hasard l'ordre des colonnes et des lignes   # optionnel, rend le comportement moyen plus facile à déterminer
pour chaque case X                                                                          # coût en N*N
    lister les DX cases à droite de X qui sont de même couleur que X                      # coût en N/2 
    lister les BX cases en bas de X qui sont de même couleur que X                        # coût en N/2 
    lister les SX cases d'indices DX BX et de même couleur que X                           # coût en N*N/4
    conclure que les X-DX-BX-SX résultants sont des carrés aux coins monochromes

Sauf erreur le temps d'exécution est en N⁵/4, ce qui est probablement améliorable. Je soupçonne toutefois que que ce serait au prix d'une grande complexification du code.

[invite23cdddab]

@Jiav : un algorithme naïf a déjà une complexité en O(N^3) vu qu'il n'y a que carrés, et qu'on peut tester un carré en temps constant

[invite9dc7b526]

joli problème.

le fait qu'il y ait une taille de damier minimale au-delà de laquelle un carré monochrome est inévitable est intuitivement évident, puisque les contraintes s'accumulent avec la taille du damier et que les solution périodiques sont interdites. Mais je ne vois pas comment le démontrer.

sinon, on peut généraliser le problème de plusieurs façons: considérer les dimensions supérieures à 2, ou bien considérer plus de 2 couleurs, ou bien prendre en compte les rectangles au lieu des seuls carrés...

autre problème: a priori le pense que c'est plus facile de n'avoir aucun carré si le nombre de pièces noires est égal au nombre de pièces blanches. Quelle est la proportion maximale de blanches qui permette de ne faire apparaître aucun carré (pour une taille de damier donnée)? puisque si toutes les pièces sont blanches il y a forcément un carré, il y a un maximum strictement compris entre 0 et 1.

[invite6c250b59]

@Jiav : un algorithme naïf a déjà une complexité en O(N^3) vu qu'il n'y a que carrés, et qu'on peut tester un carré en temps constant

Les "carrés" rectangulaires ne sont pas à considérer?

[invite51d17075]

ben déjà avec les simples carrés , ça m'a l'air un peu coton quand même !
je veux dire de manière analytique, c-a-d sans programme.

[Juzo]

autre problème: a priori le pense que c'est plus facile de n'avoir aucun carré si le nombre de pièces noires est égal au nombre de pièces blanches. Quelle est la proportion maximale de blanches qui permette de ne faire apparaître aucun carré (pour une taille de damier donnée)?

En effet, j'avais remarqué qu'il y a avait 40 cases blanches et 41 noires dans la solution 9x9.

@ansset @roro222 : j'indique ci-dessous les deux modifications à apporter pour obtenir la solution 9x9

 Cliquez pour afficher

Permutations E6E9 et F9G9

On remarque aussi dans la solution 9x9 qu'il n'y a jamais plus de 5 blanches ou moins de 4 blanches dans une ligne (idem donc pour les noires). Dans les colonnes aussi, excepté une colonne avec 3 blanches... Peut-être un début de piste de démonstration ?

[invite23cdddab]

Les "carrés" rectangulaires ne sont pas à considérer?

Un rectangle n'est pas un carré. D'ailleurs, le problème est beaucoup plus simple avec des rectangles.

Théorème : Il n'existe pas de quadrillage de taille supérieure à 8 sans rectangle monochrome.

Démonstration :
Il y a 8 façon de placer 2 couleurs sur une sous-ligne de 3 : OOO, OOX, OXO, OXX, XOO, XOX, XXO, XXX

Si il y a plus de 8 lignes, on trouvera deux fois le même groupe de 3 dans les 3 première colonnes

Or cela permet de construire un rectangle monochrome (puisqu'on a toujours au moins 2 fois une des couleurs dans chacun des groupes).


(on peut améliorer facilement ce résultat, en remarquant qu'il y a déjà des rectangles monochromes avec ces 8 groupes, et donc que le maximum est inférieur)

[invite23cdddab]

Je continue :

Si il y a XXX (ou, par symétrie, OOO), alors la taille maximale du quadrillage est 4 : les seuls groupes compatibles sont OOX, OXO, XOO, OOO (compatible = qui ne permet pas de former un rectangle monochrome)

Mais {XXX, OOO} est incompatible avec tout autre groupe : soit on va pouvoir former un rectangle monochrome avec XXX, soit avec OOO, puisque tout groupe à au moins deux fois la même couleur

Du coup, peut avoir au mieux 4 lignes. Et il existe une solution à 4 lignes :

XXXO
XOOX
OXOX
OOXO

Si il n'y a pas XXX (ou, par symétrie, OOO), alors le nombre de lignes ne peut dépasser 6.

Mais si on essaye de construire une solution de taille 6, on se rend compte que c'est impossible !

En effet, on peut permuter librement les colonnes. Donc si la taille est de 5 ou plus, on a forcément une ligne dans laquelle se trouve 3 fois la même couleur. On peut donc permuter les colonnes pour faire apparaitre XXX ou OOO : or la taille maximum d'un quadrillage contenant XXX (ou OOO) est de 4.

D'où le résultat suivant :

Théorème : La taille maximum d'un quadrillage sans rectangle monochrome est de 4



Maintenant, ceci ne sert à rien pour le problème des quadrillages sans carrés monochromes, puisque la permutation des lignes et des colonnes ne conserve pas le caractère "sans carré monochrome", or c'est ce qui fait marcher les démo ci-dessus

[invite6c250b59]

Intéressant, merci.