Combinatoire

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: lapras

Bonsoir,
exercice marran des OIM :
"On considère un polygones de n côtés non convexes. On note d la somme des longueurs de ses diagonales, p son périmetre.
Montrer que
(n-3)/2 < d/p < 0.5*( [n/2]*[(n+1)/2] - 2)"
[N] : partie entiere de N

Good luck


Posted by: _-Gaara-_

Salut,

Comment noter la somme des longueurs des diagonales ? C'est à dire avec des n et des nombres oO car un polygone à n cotés (non convexe) a n(n-3)/2 diagonales (pour n sup à 3).

Et pour le périmètre, il faut prendre n à partir de 4 si je ne me trompe pas ? xD
( p = (4+n)(n-3)/2 )

Arf ^^


a+


Posted by: lapras

salut,
je ne connais pas tes formules, mais on te demande de prouver des Inégalités strictes, et non des égalités.


Posted by: _-Gaara-_

Citation:
Posté par lapras
salut,
je ne connais pas tes formules, mais on te demande de prouver des Inégalités strictes, et non des égalités.


Salut,

et tu n'aurais pas un point de départ pour résoudre ce truc ?? oO je ne vois vraiment pas ^^ xD


Posted by: nodgim

La partie gauche de l'inégalité est fausse: il est facile de trouver un polygone non convexe de 4 cotés dont la longueur des diagonales est inférieure à la moitié du périmètre du polygone.

La partie droite de l'inégalité se retrouve facilement:
Les diagonales qui relient 2 sommets séparés par un sommet intermédiaire ont une longueur totale inférieure au double du périmètre.
Les diagonales qui relient 2 sommets séparés par 2 sommets intermédiaires ont une longueur totale inférieure au triple du périmètre.
etc...jusqu'à n/2
La sommation donne au final p(2+3+...n/2), qui conduit bien à l'inégalité recherchée.


Posted by: lapras

Ok donc en gros c'est inégalités triangulaire pour la partie de droite (grosse inégalité triangulaire)
Trouve moi donc un contre exemple pour la partie de gauche :)


Posted by: nodgim

Dans un repère orthonormé, (0,0) relié à (-1, 5) relié à (0,1) relié à (1,5) retour à (0,0).
Pour construire un polynome non convexe, donner les sommets ne suffit pas, il faut aussi indiquer les cotés.
En outre, le terme diagonale est curieux, faut il compter les diagonales extérieures au polynome, ce qui ne manque pas lorsque celui ci est non convexe


Posted by: lapras

Qu'on soit bien d'accord :
on compte les diagonales qui ne sont pas des côtés.


Posted by: nodgim

Si tu veux, mais c'est encore mieux pour l'exemple que j'ai donné


Posted by: Patastronch

En effet la partie gauche est forcément fausse puisque dans un polygone non convexe on peut augmenter le périmetre comme on veut sans modifier la somme des longueurs des diagonales. Du coup la valeur d/p peut etre aussi petite que désiré.


Posted by: lapras

Citation:
on peut augmenter le périmetre comme on veut sans modifier la somme des longueurs des diagonales

Ok, mais peux tu le prouver s'il te plait ?
Il doi surement y avoir une erreur d'énoncé, pourtant je croyais pouvoir le démontrer avec un enchainement d'inégalités triangulaires.










-