Répondre à la discussion
Affichage des résultats 1 à 23 sur 23

Colorier un quadrillage avec deux couleurs




  1. #1
    Juzo

    Colorier un quadrillage avec deux couleurs

    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 !

    -----

    Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne verront jamais

  2. Publicité
  3. #2
    roro222

    Re : Colorier un quadrillage avec deux couleurs

    Bonjour
     Cliquez pour afficher
    Le nombre d'imbéciles est incalculable,il y a de fortes probabilités que j'en suis

  4. #3
    ansset

    Re : Colorier un quadrillage avec deux couleurs

    Citation Envoyé par Juzo Voir le message
    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 ?
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !


  5. #4
    roro222

    Re : Colorier un quadrillage avec deux couleurs

    Toutes inversions est admise du moment que tu reformes pas un autres carré
    Le nombre d'imbéciles est incalculable,il y a de fortes probabilités que j'en suis

  6. #5
    ansset

    Re : Colorier un quadrillage avec deux couleurs

    je suppose qu'on a droit à plusieurs inversions à la fois. ?
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  7. A voir en vidéo sur Futura
  8. #6
    roro222

    Re : Colorier un quadrillage avec deux couleurs

    oui
     Cliquez pour afficher
    Le nombre d'imbéciles est incalculable,il y a de fortes probabilités que j'en suis

  9. #7
    Juzo

    Re : Colorier un quadrillage avec deux couleurs

    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
    Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne verront jamais

  10. Publicité
  11. #8
    ansset

    Re : Colorier un quadrillage avec deux couleurs

    Citation Envoyé par Juzo Voir le message
    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.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  12. #9
    ansset

    Re : Colorier un quadrillage avec deux couleurs

    comme on a deux carrés, il faut à minima autoriser deux chgt , non ?
    quelle est la règle exacte ?
    Dernière modification par ansset ; 09/08/2018 à 15h47.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  13. #10
    Juzo

    Re : Colorier un quadrillage avec deux couleurs

    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).
    Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne verront jamais

  14. #11
    ansset

    Re : Colorier un quadrillage avec deux couleurs

    suggestion
     Cliquez pour afficher
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  15. #12
    roro222

    Re : Colorier un quadrillage avec deux couleurs

    Citation Envoyé par ansset Voir le message
    suggestion
     Cliquez pour afficher
    Non pas bon
     Cliquez pour afficher
    Le nombre d'imbéciles est incalculable,il y a de fortes probabilités que j'en suis

  16. #13
    Juzo

    Re : Colorier un quadrillage avec deux couleurs

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

     Cliquez pour afficher
    Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne verront jamais

  17. #14
    roro222

    Re : Colorier un quadrillage avec deux couleurs

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

    Dans cette image, j'ai pas tenu compte de l'autre carré puisque déja la première proposition est fausse
    Le nombre d'imbéciles est incalculable,il y a de fortes probabilités que j'en suis

  18. #15
    Jiav

    Re : Colorier un quadrillage avec deux couleurs

    Citation Envoyé par Juzo Voir le message
    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
    Dernière modification par Jiav ; 15/08/2018 à 17h07.
    The opposite of a deep truth may well be another deep truth. Information is physical.

  19. #16
    Tryss2

    Re : Colorier un quadrillage avec deux couleurs

    @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

  20. #17
    minushabens

    Re : Colorier un quadrillage avec deux couleurs

    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.

  21. #18
    Jiav

    Re : Colorier un quadrillage avec deux couleurs

    Citation Envoyé par Tryss2 Voir le message
    @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?
    The opposite of a deep truth may well be another deep truth. Information is physical.

  22. #19
    ansset

    Re : Colorier un quadrillage avec deux couleurs

    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.
    Dernière modification par ansset ; 19/08/2018 à 23h20.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  23. #20
    Juzo

    Re : Colorier un quadrillage avec deux couleurs

    Citation Envoyé par minushabens
    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


    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 ?
    Dernière modification par Juzo ; 19/08/2018 à 23h36.
    Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne verront jamais

  24. #21
    Tryss2

    Re : Colorier un quadrillage avec deux couleurs

    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)
    Dernière modification par Tryss2 ; 22/08/2018 à 13h19.

  25. #22
    Tryss2

    Re : Colorier un quadrillage avec deux couleurs

    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
    Dernière modification par Tryss2 ; 22/08/2018 à 13h48.

  26. #23
    Jiav

    Re : Colorier un quadrillage avec deux couleurs

    Intéressant, merci.
    The opposite of a deep truth may well be another deep truth. Information is physical.

Discussions similaires

  1. Créer un quadrillage incliné word
    Par payschaud dans le forum Logiciel - Software - Open Source
    Réponses: 11
    Dernier message: 17/05/2015, 18h33
  2. Logiciel R : comment colorier des aires entre deux courbes ?
    Par julien_4230 dans le forum Programmation et langages, Algorithmique
    Réponses: 1
    Dernier message: 30/05/2013, 11h48
  3. [Blanc] Quadrillage rose sur TV LCD Lg 37LC45
    Par joss083 dans le forum Dépannage
    Réponses: 0
    Dernier message: 21/03/2011, 17h06
  4. deux couleurs
    Par jacquydu34 dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 08/10/2009, 15h24
  5. Enigme : le quadrillage infernal
    Par Argyre dans le forum Science ludique : la science en s'amusant
    Réponses: 14
    Dernier message: 21/12/2005, 21h13