16 avril 2021

7 messages - Retourner à l'article
  • Avril 2021, 3e défi

    le 16 avril 2021 à 09:42, par Al_louarn

    Il y a $6$ points violets et $10$ points oranges, donc ça nous donne $\binom{6}{3} + \binom{10}{3} = 20 + 120 = 140$ triplets monochromes, dont il faut retrancher les triplets de points alignés.
    J’en compte $2$ violets ($1$ vertical et $1$ en diagonale) et $9$ oranges ($2$ horizontaux, $5$ verticaux et $2$ en diagonale). Donc sauf erreur il y a $140 - 2 - 9 = 129$ triangles monochromes non plats.

    Répondre à ce message
  • Avril 2021, 3e défi

    le 16 avril 2021 à 11:09, par Christophe Boilley

    La question qui vient juste après, bien sûr, c’est le nombre de triangles non plats avec des sommets sur les points colorés qui ne sont pas monochromes.

    Répondre à ce message
    • Avril 2021, 3e défi

      le 17 avril 2021 à 12:38, par Blaxapate

      Il suffit de compter tous les triangles, de retirer les triangles plats, puis de retirer les triangles monochromes :

      $\binom{16}{3}-44-129=387$

      Répondre à ce message
      • Avril 2021, 3e défi

        le 17 avril 2021 à 12:43, par Christophe Boilley

        D’où la question à laquelle je n’ai pas encore de réponse : comment colorier les 16 sommets pour maximiser ce nombre de triangles bicolores ?

        Répondre à ce message
        • Avril 2021, 3e défi

          le 21 avril 2021 à 21:23, par drai.david

          Bonsoir,
          si je n’ai pas fait d’erreur, voici la réponse à votre problème :
          $ $
          • Il doit y avoir 8 points de chaque couleur.
          $ $
          • Il existe alors 16 dispositions possibles :
          type 1 :
          – 6 telles que chaque ligne est monochrome ;
          – 6 telles que chaque colonne est monochrome ;
          $ $
          type 2 : 4 de la forme :
          $ $
          $ $ 1000
          $ $ 1101
          $ $ 1011
          $ $ 0001
          $ $
          À partir de celle-ci, on en obtient une autre par symétrie d’axe horizontal (ou vertical) ;
          On obtient les deux dernières en échangeant les 0 et les 1 des deux précédentes.
          $ $
          • Dans ces 16 configurations, on peut tracer 420 triangles bicolores.

          Répondre à ce message
          • Avril 2021, 3e défi

            le 23 avril 2021 à 11:48, par Christophe Boilley

            Bravo ! La répartition 8-8 minimise effectivement le nombre de triplets monochromes, et pour faire au moins aussi bien avec une répartition déséquilibrée, il faudrait augmenter le nombre d’alignements monochromes.

            Avec la répartition 5-11 ou un déséquilibre supérieur, le nombre de triades monochromes devient trop grand (≥ 175) pour qu’on puisse espérer descendre en dessous de 100 triangles monochromes.

            Et même avec une répartition 6-10, pour réduire suffisamment les 140 triades monochromes, il faudrait arriver à garder 40 alignements monochromes, ce qui est impossible avec une répartition polychromatique. En effet, étant donnés deux sommets de couleur différente sur des lignes et colonnes différentes, au moins deux lignes ou colonnes ne sont plus monochromes ce qui supprime au moins 6 alignements.

            Pour éliminer les répartitions 7-9, il suffit montrer qu’on ne peut conserver 20 alignements monochromes dans ce cadre.

            Je ne vois pas pour l’instant de raisonnement simple pour terminer cette démonstration justifiant l’optimum annoncé. On peut bien sûr écrire un algorithme en force brute pour tester tous les cas (après tout, il n’y a que 12870 répartitions 8-8 sans même chercher à réduire par symétrie), mais je cherche ci-dessous une piste plus élégante. Avez-vous mieux ?

            Chaque sommet appartient à au moins 7 alignements. Deux sommets ont au maximum deux alignements en commun, donc la perte de 2 sommets fait perdre au minimum 12 alignements. Trois sommets de côté ne peuvent appartenir deux à deux à des alignements sans qu’il y en ait un dans un coin, donc la perte de 3 sommets fait perdre au minimum 17 alignements. En retirant un quatrième sommet il peut avoir jusque quatre alignements communs avec deux des précédents, ce qui ne fait perdre au total que 20 alignements. Je pense qu’avec 5 sommets perdus on perd au moins 26 alignements, mais les sous-cas commencent à se multiplier.

            De l’autre côté, je suis convaincu qu’avec 7 sommets on ne peut pas faire plus de 8 alignements, mais l’étude de cas est fastidieuse.

            Répondre à ce message
            • Avril 2021, 3e défi

              le 23 avril 2021 à 15:22, par drai.david

              Non, honnêtement, je n’ai pas mieux : j’ai écrit un algorithme de force brute qui teste les 65 536 coloriages possibles... Enfin non, j’ai quand même eu la présence d’esprit d’exclure les deux carrés monochromes !!! 😄

              Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.