Bonjour j'ai une petit problème à résoudre mais je ne parviens pas a trouver
la solution je vous le soumet :
on considère un polygone P convexe à n côtés ; combien existe-t-il de
polygones convexes à p côtés dont les sommets sont les sommets de P et les
cotés des diagonales de P ?
Merci de votre aide
Posted by: fredatwork
"edf" <ab@wanadoo.fr> a écrit dans le message news:
4163f629$0$7186$8fcfb975@news.wanadoo.fr...
> Bonjour j'ai une petit problème à résoudre mais je ne parviens pas a
trouver
> la solution je vous le soumet :
>
> on considère un polygone P convexe à n côtés ; combien existe-t-il de
> polygones convexes à p côtés dont les sommets sont les sommets de P et les
> cotés des diagonales de P ?
>
> Merci de votre aide
>
>
1/ Démontrer qu'un tel polygone est convexe
2/ Combien y a-t-il de tels polygones ?
C'est le nombre de façon de choisir p sommets parmi n càd C(n,p)
Posted by: edf
c'est faux car les cotés du polygone P ne peuvent etre des cotés des
polygones inscrits il faut que cela soit seuelemtnd es diagonales de P
"fredatwork" <fredatwork@hotmail.com> a écrit dans le message de news:
ck1102$9o7$1@s5.feed.news.oleane.net...
> "edf" <ab@wanadoo.fr> a écrit dans le message news:
> 4163f629$0$7186$8fcfb975@news.wanadoo.fr...
>> Bonjour j'ai une petit problème à résoudre mais je ne parviens pas a
> trouver
>> la solution je vous le soumet :
>>
>> on considère un polygone P convexe à n côtés ; combien existe-t-il de
>> polygones convexes à p côtés dont les sommets sont les sommets de P et
>> les
>> cotés des diagonales de P ?
>>
>> Merci de votre aide
>>
>>
>
> 1/ Démontrer qu'un tel polygone est convexe
> 2/ Combien y a-t-il de tels polygones ?
> C'est le nombre de façon de choisir p sommets parmi n càd C(n,p)
>
>
>
>
Posted by: zwim
Le Wed, 6 Oct 2004 15:42:03 +0200
edf a écrit
>Bonjour j'ai une petit problème à résoudre mais je ne parviens pas a trouver
>la solution je vous le soumet :
>
>on considère un polygone P convexe à n côtés ; combien existe-t-il de
>polygones convexes à p côtés dont les sommets sont les sommets de P et les
>cotés des diagonales de P ?
>
>Merci de votre aide
>
Ca a pas l'air si simple ce truc.
Juste une idée de formalisation qui me vient comme ça.
On peut considérer les sommets par paires, un sommet utilisé dans le
polygone solution en bloque un autre (son voisin de droite par
exemple) car les côtés son obligatoirement des diagonales. On n'est
pas obligé de considérer que l'on bloque les 2 voisins car le polygone
est fermé donc le voisin de gauche d'un sommet est en fait le voisin
de droite d'un autre sommet.
Il reste alors à placer p paires de 2 sommets parmi un truc du genre
n/2p emplacements. Mais il faut tenir compte de l'effet circulaire de
la chose.
Exemple 1: nombre de triangles dans un hexagone
L'héxagone est représenté par 111111
Les 2 solutions possibles sont
(01)(01)(01)
1)(01)(01)(0
Exemple 2: nombre de triangles dans un heptagone
L'héptagone est représenté par 1111111
Les 7 solutions possibles sont en fonction de la place du 1
1(01)(01)(01)
1)1(01)(01)(0
(01)1(01)(01)
1)(01)1(01)(0
(01)(01)1(01)
1)(01)(01)1(0
(01)(01)(01)1
Voilà, c'est pas encore au point, mais c'est peut-être un piste
interessante.
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
Posted by: fredatwork
"edf" <ab@wanadoo.fr> a écrit dans le message news:
416450a3$0$16598$8fcfb975@news.wanadoo.fr...
> c'est faux car les cotés du polygone P ne peuvent etre des cotés des
> polygones inscrits il faut que cela soit seuelemtnd es diagonales de P
>
ok dans ce cas on va enlever les polygones ayant 2 sommets adjacents
dans le polygone à n côtés.
Le tout est de les dénombrer.
Choisissons au hasard 2 sommets adjacents dans le polygone à n côtés.
Une fois ces deux sommets fixés, combien y a t-il de polygones à p sommets
incluant ces deux sommets, c'est le nombre de façon de choisir p-2 sommets
parmi les n-2 restants donc C(n-2,p-2) (on prend p>2, pour p<=2 je pense que
tu y arriveras)
Maintenant combien de façon y a-t-il de choisir les
deux sommets adjacents que nous avons fixés ? n
La réponse à la question est donc :
C(n,p) - n * C(n-2, p-2)
Posted by: philippe 92
Bonjour,
fredatwork a écrit:
> "edf" <ab@wanadoo.fr> a écrit dans le message news:
> 416450a3$0$16598$8fcfb975@news.wanadoo.fr...
>
>> c'est faux car les cotés du polygone P ne peuvent etre des cotés des
>> polygones inscrits il faut que cela soit seuelemtnd es diagonales de P
>
> ok dans ce cas on va enlever les polygones ayant 2 sommets adjacents
> dans le polygone à n côtés.
>
> La réponse à la question est donc :
> C(n,p) - n * C(n-2, p-2)
>
Formule "visiblement" fausse
si n = 6 et p = 3 on dénombre facilement à la main les
deux seuls triangles formés de diagonales d'un hexagone
or C(6,3) - 6*C(4,1) = 20 - 6*4 = -4 !!!
Avec n=7 p=3 on compte un peu plus difficilement les 7 triangles
formés de diagonales d'un heptagone (voir le post de zwim)
et C(7,3) - 7*C(5,1) = 0 !!!
On a en fait ici enlevé trop de triangles car les triangles formés
de deux côtés de l'hexagone et d'une seule diagonale sont comptés
deux fois !
Il faut donc rajouter une fois les 6 triangles formés de 3 sommets
adjacents.
Dans le cas général, les p-gones comportant des côtés du n-gone sont
plus difficile à compter. Parmi les n*C(n-2, p-2) à éliminer :
Ceux qui ont un seul côté et p-1 diagonales sont bien comptés une fois
Mais ceux qui ont k côtés et p-k diagonales sont comptés plusieurs fois
Semble compliqué de compter comme ça...
L'idée de zwim semble plus fructueuse :
Un sommet interdit son voisin de droite, il s'agit alors de
choisir p "di-sommets" (un sommet + son voisin) parmi les n
positions possibles.
C'est à dire de choisir les n-2p sommets qui ne font pas partie
des di-sommets retenus. donc C(n, n-2p)
Sauf si n=2p car alors il n'y a que deux possibilités.
Et si n<2p c'est impossible : il y aura forcément deux sommets
du p-gone adjacents sur le n-gone.
philippe 92 a écrit:
....
>
> L'idée de zwim semble plus fructueuse :
> Un sommet interdit son voisin de droite, il s'agit alors de
> choisir p "di-sommets" (un sommet + son voisin) parmi les n
> positions possibles.
> C'est à dire de choisir les n-2p sommets qui ne font pas partie
> des di-sommets retenus. donc C(n, n-2p)
> Sauf si n=2p car alors il n'y a que deux possibilités.
> Et si n<2p c'est impossible : il y aura forcément deux sommets
> du p-gone adjacents sur le n-gone.
>
> si n>2p : C(n, n-2p)
> si n=2p : 2
> si n<2p : 0
>
> Sauf erreur, comme d'hab.
>
Erreur il y a, c'est tout aussi faux !
Le cas n>2p est plus tordu.
On ne peut pas choisir les n-2p trous librement parmi les n
positions : si deux trous voisins sont séparés par un nombre impair
de sommets, on ne peut évidement pas caser des paires de sommets
entre ces trous !
n = 8, p = 3 donne 16 triangles et pas C(8, 2) = 28
ma formule ne marche que pour n = 2p + 1, donne C(n,1) = n
par exemple n = 7 p = 3 (l'exemple zwim) : 7 triangles, OK.
La méthode de zwim permet bien de lister facilement les p-gones
mais ne conduit pas directement à une formule explicite.