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.



Edité 2 fois. La dernière correction date de il y a sept mois et a été effectuée par AD.

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 ?



Edité 1 fois. La dernière correction date de il y a sept mois et a été effectuée par AD.

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



Edité 1 fois. La dernière correction date de il y a sept mois et a été effectuée par Tonm.

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.

[oeis.org]

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 :
[oeis.org]
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.

Liste des forums - Statistiques du forum

Total
Discussions: 148 604, Messages: 1 497 686, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.

---

Ce forum
Discussions: 886, Messages: 7 497.