Combien de triangles ?

gauss

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.

Dom

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 ?

gauss

Oui mais la difficulté est alors de compter les triangles aplatis ?

Dom

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...

Tonm

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

PetitLutinMalicieux

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.

Chaurien

https://oeis.org/A045996

YvesM

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à !

gauss

Ok merci à tous, le document de Chaurien montre que le problème est très très complexe.

Chaurien

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.