20 mai 2016

5 messages - Retourner à l'article
  • Mai 2016, 3e défi

    le 20 mai 2016 à 09:14, par Al_louarn

    Disons qu’un triangle est d’ordre $n$ s’il a $n$ sommets sur le cercle.
    Pour faire un triangle d’ordre $n$ il faut $3$ cordes issues de $6-n$ sommets.
    Il y a $C_8^k$ ensembles de $k$ sommets.
    Un ensemble de $6$ sommets forme $1$ triangle d’ordre $0$.
    Un ensemble de $5$ sommets forme $5$ triangles d’ordre $1$.
    Un ensemble de $4$ sommets forme $4$ triangles d’ordre $2$.
    Un ensemble de $3$ sommets forme $1$ triangle d’ordre $3$.
    Le nombre de total de triangles est donc $1 \times C_8^6 + 5 \times C_8^5 + 4 \times C_8^4 + 1 \times C_8^3 = 644$.

    Répondre à ce message
  • Mai 2016, 3e défi

    le 20 mai 2016 à 15:37, par mesmaker

    Bien que je trouve ce défi plus corsé que d’habitude, je me pose une question qui me semble encore plus dure.

    Si j’ai bien compris la question et la solution donné par Al_louarn, on cherche tous les triangles possibles même ceux qui sont traversées par des cordes. Dans mon cas, je me pose la question de colorier les triangles et de manière plus générales les quadrilatères, pentagones, ...Donc je me restreint au figures géométriques dont l’intérieur est vide. Est il possible de savoir combien il y en a ?

    Par exemple pour 3 points, il y a seulement 1 triangles, pour 4 points, il y a quatre triangles, pour cinq points il y a 10 triangles et au milieu un pentagones, pour six points, cela se corse, et il me semble qu’il y a 18 triangles sur les ’’bords’’ 1 au centre, 3 quadrilatères et 3 pentagones.

    Que se passe t’il pour 7 en enfin 8 ? et plus si c’est possible ?

    Répondre à ce message
    • Mai 2016, 3e défi

      le 23 mai 2016 à 15:03, par Al_louarn

      Donc si je résume le problème, on a un polygone convexe a $n$ côtés, tel que $3$ de ses diagonales ne sont jamais concourantes à l’intérieur du polygone. Les diagonales divisent le grand polygone en petites régions polygonales, qu’on veut dénombrer.

      Imaginons qu’on trace les diagonales une à une.

      Au départ il n’y a qu’une seule région.

      Ensuite, à chaque étape, la $i$ème diagonale ajoutée va croiser ${d_i}$ autres diagonales parmi les $i-1$ qui ont déjà tracées.
      Elle va donc traverser ${d_i}+1$ régions existantes. Chaque région traversée est divisée en $2$, ce qui augmente d’un point le nombre de régions.
      Le nombre de régions ajoutées par la nouvelle diagonale est donc ${d_i}+1$.

      S’il y a $D$ diagonales, le nombre total de régions est donc $R(n) = 1 + ({d_1}+1) + ... + ({d_D}+1) = 1 + D + ({d_1} + ... + {d_D})$.

      Comme ${d_i}$ est aussi le nombre de croisements (intérieurs) ajoutés par la $i$ème diagonale, la somme des ${d_i}$ est égale au nombre total de croisements intérieurs.
      Tout croisement intérieur s’obtient à partir de $4$ sommets du polygone, et inversement tout ensemble de $4$ sommets définit un et un seul croisement intérieur de diagonales.
      Le nombre total de croisements intérieurs est donc ${C_n^4}$.

      Pour calculer le nombre $D$ de diagonales, on considère tous les couples de sommets : il y en a ${C_n^2}$. Mais il ne faut pas compter les $n$ côtés du polygone, donc $D={C_n^2} - n$.

      Finalement on obtient $R(n) = 1 + {C_n^2} - n + {C_n^4}$, qui se simplifie en $R(n) = {C_{n-2}^2} + {C_n^4}$ pour $n \geq 4$.

      En faisant le calcul on retrouve bien :
      $R(4) = 4$
      $R(5) = 11$
      $R(6) = 25$
      Ensuite :
      $R(7) = 50$
      $R(8) = 91$
      etc.

      Répondre à ce message
      • Mai 2016, 3e défi

        le 24 mai 2016 à 10:04, par mesmaker

        Je n’ai rien a dire sinon merci et bravo.

        Ensuite si vous arrivez à donner le nombre de triangles, quadrilatères, pentagones, ... dans chaque cas, je créerai une page Wikipédia en appellant cette suite la suite Al_louarn :)
        Trêve de plaisanteries, ces questions pourraient presque rentrer dans le cadre des graphes complets convexe si cette catégorie existe.
        https://fr.wikipedia.org/wiki/Graphe_complet

        Répondre à ce message
        • Mai 2016, 3e défi

          le 25 mai 2016 à 23:37, par Al_louarn

          Pour l’instant ce n’est pas brillant, tout ce que j’ai trouvé c’est une petite erreur dans l’écriture de ma formule... En fait $R(n) = {C_{n-1}^2} + {C_n^4}$.

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