Combien de triangles ? — Les-mathematiques.net The most powerful custom community solution in the world

Combien de triangles ?

Bonjour
Sur un quadrillage à mailles carrées de taille n*n (n entier supérieur à 2), combien de triangles non aplatis ont leurs sommets formés de trois points de ce quadrillage ?

Y a-t-il un moyen simple de dénombrer ces triangles ?
Bonne journée.

Réponses

  • Hum...
    Les compter tous (tous les triplets), même les aplatis et les dégénérés (réduits à un point), puis soustraire ces derniers ?
  • Oui mais la difficulté est alors de compter les triangles aplatis ?
  • Ha oui je vois.
    Il y a les lignes, les colonnes, les diagonales, les parallèles aux diagonales mais aussi des points alignés sur d’autres pentes...
    Ces derniers peuvent dépendre péniblement de $n$ me dis-je...
  • Bonjour, c'est une généralisation du calcul (classique) nombre de rectangles distincts pour un quadrillage donné (un rectangle $4$ triangles rectangles). Tu dois par exemple trouver le nombres de parallélogrammes distinctes à sommets $\in$ les noeuds du quadrillage. Ça doit être faisable (un joli truc)
    Cordialement
  • Bonjour

    @Gauss: Ta question est très intéressante. Pour compter les triangles aplatis, il faut dompter les nombres premiers et la factorisation des nombres entiers inférieurs ou égaux à n. Je doute, a priori, que l'on puisse trouver une formule simple.
  • Bonjour,

    Il n’y a pas de formule explicite.

    Algorithme.

    Avec des boucles tu comptes tous les triangles.

    Tu élimines les triangles égaux.

    Tu élimines les triangles aplatis avec $x_1=x_2=x_3.$

    Tu élimines les triangles aplatis avec $y_1=y_2=y_3.$

    Tu élimines les triangles aplatis en pente : tu calcules la pente $(y_2-y_1)/(x_2-x_1)$ et celle en l’indice 3 et 2.

    Voilà !
  • Ok merci à tous, le document de Chaurien montre que le problème est très très complexe.
  • Il faut ajouter le complémentaire, le nombre de triplets colinéaires, où il y a plus de références :
    https://oeis.org/A000938
    J'ai réussi à trouver le texte : M. A. Adena, D. A. Holton and P. A. Kelly, Some thoughts on the no-three-in-line problem, pp. 6-17 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974
    que je ne peux sans doute communiquer publiquement, mais si quelqu'un en a besoin, on peut s'arranger, je pense ;-).
    On y apprend que le problème vient des mathématiques récréatives, pour $n=8$, Dudeney (1917) et Rouse Ball (1939).
    Bonne soirée.
    Fr. Ch.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!