Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
179 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Combien de triangles ?

Envoyé par gauss 
Combien de triangles ?
il y a sept mois
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.
Dom
Re: Question naïve ?
il y a sept mois
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.
Re: Question naïve ?
il y a sept mois
Oui mais la difficulté est alors de compter les triangles aplatis ?
Dom
Re: Question naïve ?
il y a sept mois
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...
Re: Question naïve ?
il y a sept mois
avatar
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.
Re: Combien de triangles ?
il y a sept mois
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.
Re: Combien de triangles ?
il y a sept mois
avatar
Re: Combien de triangles ?
il y a sept mois
avatar
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à !
Re: Combien de triangles ?
il y a sept mois
Ok merci à tous, le document de Chaurien montre que le problème est très très complexe.
Re: Combien de triangles ?
il y a sept mois
avatar
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 winking smiley.
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.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 744, Messages: 1 499 661, Utilisateurs: 28 309.
Notre dernier utilisateur inscrit erkl.


Ce forum
Discussions: 886, Messages: 7 507.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page