Combinatoire
Olympiades mathématiques, énigmes et défis
-
lapras
- Membre Transcendant
- Messages: 3664
- Enregistré le: 01 Jan 2007, 12:00
-
par lapras » 26 Jan 2008, 18:46
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
-
_-Gaara-_
- Membre Complexe
- Messages: 2813
- Enregistré le: 03 Nov 2007, 14:34
-
par _-Gaara-_ » 28 Jan 2008, 01:02
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+
-
lapras
- Membre Transcendant
- Messages: 3664
- Enregistré le: 01 Jan 2007, 12:00
-
par lapras » 28 Jan 2008, 07:11
salut,
je ne connais pas tes formules, mais on te demande de prouver des Inégalités strictes, et non des égalités.
-
_-Gaara-_
- Membre Complexe
- Messages: 2813
- Enregistré le: 03 Nov 2007, 14:34
-
par _-Gaara-_ » 28 Jan 2008, 17:34
lapras a écrit: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
-
nodgim
- Habitué(e)
- Messages: 2002
- Enregistré le: 27 Jan 2008, 10:21
-
par nodgim » 29 Jan 2008, 18:52
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. :triste:
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.
-
lapras
- Membre Transcendant
- Messages: 3664
- Enregistré le: 01 Jan 2007, 12:00
-
par lapras » 29 Jan 2008, 19:27
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 :)
-
nodgim
- Habitué(e)
- Messages: 2002
- Enregistré le: 27 Jan 2008, 10:21
-
par nodgim » 30 Jan 2008, 18:59
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 :pi:
-
lapras
- Membre Transcendant
- Messages: 3664
- Enregistré le: 01 Jan 2007, 12:00
-
par lapras » 30 Jan 2008, 20:27
Qu'on soit bien d'accord :
on compte les diagonales qui ne sont pas des côtés.
-
nodgim
- Habitué(e)
- Messages: 2002
- Enregistré le: 27 Jan 2008, 10:21
-
par nodgim » 31 Jan 2008, 18:25
Si tu veux, mais c'est encore mieux pour l'exemple que j'ai donné :id:
-
Patastronch
- Membre Irrationnel
- Messages: 1345
- Enregistré le: 22 Aoû 2005, 23:53
-
par Patastronch » 31 Jan 2008, 21:31
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é.
-
lapras
- Membre Transcendant
- Messages: 3664
- Enregistré le: 01 Jan 2007, 12:00
-
par lapras » 31 Jan 2008, 21:45
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.
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 32 invités