Un défi par semaine

Avril 2021, 3e défi

Le 16 avril 2021  - Ecrit par  Ana Rechtman Voir les commentaires (7)
Lire l'article en  

Nous vous proposons un défi du calendrier mathématique chaque vendredi et sa solution la semaine suivante.

Le calendrier 2021 est en vente ! Il s’intitule : « Le ciel dans tous ses états ».

De janvier à décembre, à travers 12 textes superbement illustrés, découvrez l’histoire des équations cachées dans les trajectoires des planètes et des étoiles ainsi que le développement des grandes théories qui ont accompagné cette ­aventure.

Semaine 16

Combien peut-on construire de triangles (non-plats) dont les trois sommets sont placés sur des points de la même couleur ?

PNG - 16.9 ko

Solution du 2e défi d’avril :

Enoncé

La réponse est $(1,1,1)$, $(1,1,2)$ et $(1,2,3)$.

Comme $a\le b\le c$, on a $a+b\le 2c$.

De plus, $a+b$ est un multiple de $c$ donc, ou bien $a+b=c$, ou bien $a+b=2c$.

Si $a+b=2c$, comme on a $a\le c$ et $b\le c$, cela implique nécessairement que $a=c$ et $b=c$, donc $a=b=c$.

Comme ces trois nombres ne doivent pas avoir de diviseur premier en commun, on a nécessairement $a=b=c=1$.

Considérons maintenant le cas où $a+b=c$.

Les trois entiers $a$, $b$ et $c$ sont alors deux à deux premiers entre eux, car tout diviseur commun à deux de ces entiers est diviseur du troisième en utilisant la relation $a+b=c$.

Mais chacun des entiers $a$, $b$ et $c$ divise la somme $a+b+c$, donc le produit d’entiers premiers entre eux $abc$ aussi.

On obtient donc que $abc$ divise $a+b+c\le 3c$ et donc $ab\le3 $.

Si $a=b=1$, comme $c$ doit diviser $a+b=2$, $c$ peut prendre les valeurs $1$ ou $2$.

Si $a=1$ et $b=2$, alors seul $c=3$ convient.

Si $a=1$ et $b=3$, il n’y a pas de solutions possibles (car $c$ divise $4$, donc ne peut prendre que la valeur $4$, mais alors $b=3$ ne divise pas $a+c=5$).

Finalement, seuls les triplets $(1,1,1)$, $(1,1,2)$ et $(1,2,3)$ conviennent.

Post-scriptum :

Calendrier mathématique 2021 - Sous la direction d’Ana Rechtman,

Partager cet article

Pour citer cet article :

Ana Rechtman — «Avril 2021, 3e défi» — Images des Mathématiques, CNRS, 2021

Commentaire sur l'article

  • Avril 2021, 3e défi

    le 16 avril à 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 à 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 à 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 à 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 à 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 à 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 à 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

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?