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 : 2953

Trinagulation

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.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

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

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Triangulatioon

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
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 68

triangulatiob

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 : 2953

Triangulatioon

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

Triangulatoin

@ 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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

trianhulation

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 : 2953

Triangulatino

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

Trianguation

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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Triangulattion

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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

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 : 2953

Triangualtion

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

triangulatipn

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

Trriangulation

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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Triangulaiton

Pour le nuage, je tente 92, sans certitude.

 #15 - 27-11-2016 08:06:07

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

rTiangulation

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

Triangulaiton

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 : 2953

Tringulation

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

Trianulation

C'est revu et corrigé.smile

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

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

Trianguulation

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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

triabgulation

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
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 68

triangylation

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 : 2953

triangulatipn

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

Triangulaton

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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Triangulatio

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 : 2953

Triangulatin

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

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

Sujets similaires

Sujet Date Forum
08-01-2008 Enigmes Mathématiques
P2T
25-02-2015 Enigmes Mathématiques
P2T
N feuilles de papier... par MeugiWara
15-03-2013 Enigmes Mathématiques
P2T
Optimisation level 5 par golgot59
04-12-2014 Enigmes Mathématiques
P2T
Echecs 4 par Vasimolo
19-08-2010 Enigmes Mathématiques
P2T
27-08-2010 Enigmes Mathématiques
P2T
Gâteau 104 par Vasimolo
12-09-2015 Enigmes Mathématiques
P2T
06-11-2010 Enigmes Mathématiques
P2T
La sphère trouée par looozer
27-02-2010 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