![](/img/vague-bas-gauche.png) |
#1 - 25-11-2016 12:08:13
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Tringulation
Bonjour à tous.
Un géomètre mesure l'aire d'un terrain en découpant celle ci en triangles.
Pour un polygone convexe irrégulier à 9 sommets, de combien de façons peut il découper en triangles si les sommets du polygone sont les seuls sommets autorisés pour les triangles ? Pour quels types de polygones convexes le nombre de façons de découper sera t'il impair (avec la même contrainte) ?
Pour ce nuage de 9 points autorisés comme sommet de triangle, de combien de façons peut on trianguler l'aire du polygone qui enferme ce nuage ? Points : (0,0) (18,0) (8,5) (12,5) (3,9) (15,9) (10,15) (0,18) (18,18).
Bon amusement
La première partie est assez théorique mais pas très difficile. La seconde n'est pas théorique mais exige une méthode bien carrée.
#2 - 25-11-2016 17:34:40
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
triangulatoon
Bonsoir ,
La première question est en effet très classique ( et pas évidente ) , la solution est donnée par les nombres de Catalan .
Je n'ai pas regardé la deuxième question , je suppose que certains points sont strictement à l'intérieur de l'enveloppe convexe de l'ensemble .
Vasimolo
#3 - 25-11-2016 17:55:44
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
trizngulation
Bonjour, doit on compter toutes les symétries, ou seulement compter les triangulations non superposables?
#4 - 25-11-2016 18:21:19
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Trianulation
@Caduk: j'ai apporté une précision: polygones non symétriques.
#5 - 25-11-2016 18:26:26
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Trianguation
@ Vasimolo: je ne connaissais pas, et après vérification, il s'avère que tu as raison. Déja une bonne réponse pour la 1ère partie, bravo à toi. Sans doute pourras tu préciser pour la parité ? Ce n'est pas méchant quand on a compris comment se décortique l'algorithme.
#6 - 26-11-2016 13:42:38
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Triangultaion
Si j'ai bien compris la question, il s'agit des nombres de Catalan. C'est un problème très classique : https://en.wikipedia.org/wiki/Catalan_n … binatorics Ici, pour un ennéagone, la réponse attendue est 429.
Pour la question de la parité des nombres de Catalan, je vous livre une démo qui n'est pas de moi mais que j'aime beaucoup.
Tout d'abord, le nombre de Catalan Cn = (2n)! / n!.(n+1)! permet de dénombrer les chemins de longueur 2n, comme dans la figure 1, qui commencent et terminent sur la droite, et limités au demi-plan supérieur. Par exemple, il y a C5=42 chemins de longueur 10 du type de celui de la figure 1.
![http://www.prise2tete.fr/upload/Ebichu-catalan.png](http://www.prise2tete.fr/upload/Ebichu-catalan.png)
Ces chemins peuvent être assemblés par paires, comme ceux de la figure 2, sauf ceux qui sont symétriques. Donc en notant Sn le nombre de chemins symétriques de longueur 2, Cn et Sn ont la même parité.
Maintenant, les chemins symétriques peuvent également être assemblés par paires, comme sur la figure 3, en inversant la portion constituée des deux segments médians. Mais là encore, il reste des chemins : ce sont ceux pour lesquels la portion médiane est tout en bas, comme dans la figure 4. Or, on peut dénombrer ces exceptions : il y en a C((n-1)/2) si n est impair (car les n-1 segments de gauche déterminent entièrement la figure 4), et 0 si n est pair. Donc, là encore, Sn a la même parité que C((n-1)/2) si n est impair, et Sn est pair si n est pair.
En résumé, Cn a la même parité que C((n-1)/2) si n est impair, et Cn est pair si n est pair. Par récurrence, Cn est impair si et seulement si n est de la forme 2^k-1.
Pour ton nuage de points, je ne suis pas sûr de la définition du "polygone qui enferme ce nuage" : est-ce que un carré, ou une étoile à 4 branches aplatie en bas, ou autre chose ? Car on peut imaginer des manières plus pathologiques d'enfermer le nuage...
#7 - 26-11-2016 16:22:37
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Triangultaion
@Ebichu: il s'agit bien de ces nombres référencés comme tels. Je n'ai pas tout à fait employé le même raisonnement, mais l'idée est là. Le résultat est presque correct, sauf qu'à mon avis il faut que tu l'adaptes au cas des polynômes à n sommets.
Pour le nuage de points, considérer son aire comme étant le polygone qui passe par les points extérieurs. Autrement le fil tendu qui entoure tous les points. Pour ne pas le cacher, c'est bien un carré 18*18.
#8 - 26-11-2016 16:34:36
- Sydre
- Professionnel de Prise2Tete
- Enigmes résolues : 15
- Messages : 245
Triangulationn
Salut,
Sauf erreur pour un [latex]9[/latex]-gone convexe il existe [latex]429[/latex] découpes possibles.
Plus généralement la suite définie par : [TeX]U_2=1[/TeX] [TeX]U_n=\sum_{k=2}^{n-1}U_kU_{n+1-k}[/TeX] Donne au rang [latex]n[/latex] le nombre de découpes possibles pour un [latex]n[/latex]-gone convexe.
On remarque que la somme, qui contient [latex]n-2[/latex] termes, est symétrique donc paire si [latex]n-2[/latex] est pair donc [latex]n[/latex] pair.
A l'inverse lorsque [latex]n[/latex] est impair donc [latex]n+1[/latex] pair la somme n'est pas symétrique à cause du terme [latex]U_{\frac{n+1}{2}}^2[/latex] et sa parité dépends donc de la nature de ce celui-ci.
Par récurrence il vient :
Si [latex]\frac{n+1}{2}[/latex] est pair alors [latex]U_{\frac{n+1}{2}}[/latex] est pair sinon il est de même nature que [latex]U_{\frac{n+3}{4}}[/latex]
...
Au final on conclus que le nombre découpes possibles pour un [latex]n[/latex]-gone convexe est impair si et seulement si [latex]n-1[/latex] est une puissance de [latex]2[/latex].
#9 - 26-11-2016 16:35:21
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
triangulatipn
Oui, bien sûr, j'avais omis de préciser que le nombre de Catalan Cn donne le nombre de découpages d'un polygone à n+2 côtés. Les polygones avec un nombre impair de découpages sont donc ceux à 2^k+1 côtés (k>0). Il faut toujours répondre à la question posée ![smile](img/smilies/smile.png)
Je vais regarder pour le découpage du carré.
#10 - 26-11-2016 17:39:08
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
triangukation
Pour le découpage du nuage de points, est-on obligé d'utiliser les 9 points ? Par exemple, le découpage du carré en 2 triangles en traçant juste une diagonale est-il valide ?
#11 - 26-11-2016 18:04:20
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Tirangulation
@Ebichu (et @ tous): il faut obligatoirement utiliser les 9 points comme sommets des triangles. Le but est quelque part de comparer le découpage d'un 9 points - polynôme et d'un 9 points - nuage.
#12 - 26-11-2016 18:10:14
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Triangulaiton
@ Sydre : c'est parfait pour la 1ère partie de la question, bravo à toi. @ Ebichu : Idem, après la retouche, c'est OK pour la 1ère partie. Bravo.
#13 - 26-11-2016 19:34:22
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
Triangultaion
Pour le nombre de façons de découper un ennéagone en triangles, je pense qu’il s’agit d’un nombre de Catalan, soit 429 dans notre cas. Le nombre de façons de découper sera impair pour les polygones à 1+2^n côtés, n étant un entier naturel (soit pour les polygones à 3; 5; 9; 17; 33; 65, etc côtés). Pour le nuage de neuf points, le nombre de façons de découper semble être de: 1 (carré extérieur) x 5 (pentagone du milieu) x 2 (partie inférieure) = 10.
#14 - 26-11-2016 20:37:10
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Tringulation
Pour le nuage, je tente 92, sans certitude.
#15 - 27-11-2016 08:06:07
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Triangultaion
@Francky: c'est tout bon pour la 1ère partie, bravo à toi ! Pour le nuage de 9 points, n'oublie pas que chaque point participe à la triangulation, et seulement ces points là.
@Ebichu: j'en ai 4 de plus. Attendons d'autres résultats.
#16 - 27-11-2016 16:38:50
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
triangularion
Cela correspond à la suite des nombres de Catalan pour k=n-2
Autrement dit, pour 9 sommets le septième nombre de Catalan est 429.
Les seuls nombres de Catalan impair sont pour n = 2x+1. Pour conserver cette imparité, le terme suivant doit être (2 fois +1) le précédent...
On tombe donc plutôt sur les 2^n-1.
Pour le nuage de points, je trouve 31 possibilités.
#17 - 28-11-2016 12:15:22
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Trianuglation
OK Gwen pour le polygone 9 cotés. Le critère de parité est à revoir (effectivement, il faut un polygone avec un nombre impair de cotés, mais ça ne suffit pas)
#18 - 28-11-2016 17:39:49
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
Triangulatino
C'est revu et corrigé.![smile](img/smilies/smile.png)
#19 - 28-11-2016 18:26:01
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Trianuglation
C'est presque ça, Gwen, pour la parité, tu dois juste adapter la formule au cas spécifique des polynômes. Pour le nombre de configurations possibles dans le nuage des 9 points, tu es assez loin du résultat. Sans doute y a t'il une mauvaise interprétation. Pour l'instant, seul Ebichu a approché le résultat (il lui en manque tout de même 14 et non 4). L'important dans cette histoire là est de trouver une méthode qui permette ni d'oublier des cas, ni d'en compter 2 fois. Par ailleurs, c'est un problème qui ne se met pas facilement sous forme de lignes de programme.
#20 - 29-11-2016 18:57:42
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
trianhulation
Je relance de 14 : pris par le doute suite à ton message, j'ai vérifié ma preuve en refaisant les calculs d'une autre façon, ce qui m'a permis de corriger une erreur.
Mes deux calculs trouvent maintenant le même résultat, et c'est 120 ![smile](img/smilies/smile.png)
J'espère que je n'aurai pas à tous les tracer pour me justifier. En attendant, je peux déjà dire que 12 segments appartiennent à toutes les triangulations.
#21 - 30-11-2016 07:30:28
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
triangukation
Bonjour, pour la première, il est facile de remarquer la relation de récurrence: f(n) = n[f(3)f(n-1) + f(4)f(n-2) + ... + f(n-1)f(3)] / 2(n-3) Cela vient que l'on peut séparer le polygone en deux, et on obtient deux nouveaux polygones avec p et n-p+2 côtés. On somme sur tous les découpages possibles en partant d'un sommet, fois n pour pour parcourir tous les sommets, divisé par 2( n-2) pour enlever les doublons (2 car la même coupe sera comptée deux fois (on pourrait sommer seulement sur la moitié des termes, mais il faudrait alors distinguer le cas pair et impair...) , n-3 car il y a toujours n-3 coupes non sécantes avant de triangulariser le polygone (somme des sommets dechaque face - 3(nombres de faces) = n-3, diminue de 1 à chaque étape, atteint 0 en n-3 étapes, on a alors que des triangles) On conjecture rapidement grâce à l'OEIS que l'on obtient les nombres de Catalan, et de là, on en déduit une méthode directe, en relation avec les parenthèses (jamais j'aurais pensé que ça puisse avoir un rapport avec le parenthésage... ) On trouve donc 42 manières pour un polygone a 9 côtés.
En prenant la formule de récurrence, f(n) = somme f(i) f(n-i+1), on trouve que f(n) est ipair si et seulement si le terme du milieu est pair. (car la plupart des termes sont sommés deux fois). Il faut donc que n soit impair (nombre impair de termes sommés, donc un central). Quand on a un terme impair, il faut doubler le nombre de termes pour en trouver un nouveau impair. par récurrence,on trouve qu'un nombre de Catalan est pair si il est égal à 2^n-1, donc 2^n+1 côtés au polygone.
#22 - 30-11-2016 08:34:41
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Triangulationn
@ Caduk: c'est bon pour la première partie, j'imagine que pour le nombre de combis, tu as oublié un chiffre dans ta réponse.
@ Ebichu: Tu en as 14 de plus que moi. Perso, je suis sûr de n'avoir pas de redondant, et, pour autant que j'ai vérifié, il ne m'en manque pas, mais c'est tellement facile d'en oublier.... Ce qui m'intéresse, c'est la méthode, bien sûr.
#23 - 30-11-2016 08:37:48
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Triangulatino
Pour s'y retrouver mieux dans le nuage, j'ai numéroté les points : 1: 0 18 2: 18 18 3: 10 15 4: 3 9 5: 15 9 6: 12 5 7: 8 5 8: 0 0 9: 18 0
#24 - 30-11-2016 09:43:40
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
triangulatiob
J'ai commencé par remarquer que les arêtes 12, 13, 14, 18, 23, 25, 29, 48, 59, 69, 78, 89 sont obligatoires.
Ensuite, j'ai réalisé un arbre pour répertorier toutes les possibilités. Chaque noeud de l'arbre correspond à une disjonction de cas. Par exemple, il part trois branches de la racine de l'arbre, qui indiquent qu'une triangulation contient soit l'arête 49, soit l'arête 58, soit l'arête 67 (il y en a forcément une et une seule).
Si 49 est tracée, alors 47 et 79 le sont également, ce que je n'ai pas indiqué dans l'arbre. Puis, il y a encore 3 cas : ou bien 24 est tracée, ou bien 26 est tracée mais pas 24, ou bien 35 est tracée. On voit à droite de la première feuille de l'arbre que si on trace 49 puis 24, il y a deux triangulations possibles (le nombre entouré).
Enfin, 67 (en bas de l'arbre) est un sommet un peu particulier, car si on trace l'arête 67, alors en bas de la figure, on a le choix entre tracer 68 ou 79 : il faut donc multiplier par 2 le nombre de triangulations qui commencent par 67.
On a donc au total : (2+2+2+2+5) + (2+2+2+2+5) + 2*(4+1+5+4+5+5+4+5+14) = 120 triangulations possibles.
![http://www.prise2tete.fr/upload/Ebichu-triangulation.jpg](http://www.prise2tete.fr/upload/Ebichu-triangulation.jpg)
#25 - 30-11-2016 11:26:19
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Triangulaion
@ Ebichu: je n'ai pas pratiqué autrement. C'est peut être dans la réalisation qu'il y a une différence. Je regarde ton arbre en détail. Sinon, pour les 12 arêtes obligatoires, je suis d'accord.
|
![](/img/vague-haut-droite.png) |