Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 25-11-2016 12:08:13

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

triangilation

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.

  • |
  • Répondre

#0 Pub

 #2 - 25-11-2016 17:34:40

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

Triangultaion

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

Trianglation

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

ttiangulation

@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

triangukation

@ 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

ttiangulation

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

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

Triangulatioon

@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 : 236

Triangulatoin

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

triabgulation

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

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

Triangullation

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

Triangulatiion

@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

Triangulationn

@ 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 : 3208
Lieu: Luxembourg

Triaangulation

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

Triangultion

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

TTriangulation

@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,896E+3

triangulatoon

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

Triaangulation

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,896E+3

trizngulation

C'est revu et corrigé.smile

 #19 - 28-11-2016 18:26:01

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Trinagulation

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

Trinagulation

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

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

triangulatoon

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

ttiangulation

@ 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

Triangultaion

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

triangulatoon

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

 #25 - 30-11-2016 11:26:19

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

triabgulation

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

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 51 pommes et que vous en prenez 24, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
P2T
02-06-2022 Enigmes Mathématiques
P2T
Effet de serre par Sydre
19-06-2019 Enigmes Mathématiques
P2T
Les deux échelles . par unecoudée
19-03-2021 Enigmes Mathématiques
P2T
Gâteau 53 par Vasimolo
13-06-2012 Enigmes Mathématiques
13-06-2008 Enigmes Mathématiques
P2T
Carré magique par Antober
27-01-2010 Enigmes Mathématiques
P2T
Gâteau 25 par LeSingeMalicieux
09-08-2010 Enigmes Mathématiques
13-09-2013 Enigmes Mathématiques
P2T
Supercherie radine par Griimm
14-03-2016 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete