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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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 ?
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...
Cordialement
@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.
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à !
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.