Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#26 24-01-2022 18:34:45

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 314

Re : diagonales_d_un_polygone

Bonsoir ...

Oui, je pense que des diagonales ne se coupent pas; Sont-elles bien otées ???

Par exemple, sur le décagone, les sommets sont A en haut à droite (gauche des tirets), puis BCDEFGHIJ en tournant trigo.
Alors, [AG] ne coupe pas [BF] par ex, etc ... Mais les droites peuvent se recouper à l'extérieur ! Mais pas toujours !

Quelles sont les données précises de l'énoncé ? Points intérieurs seulement ou non ? Ce n'est pas le même problème ...

Pourquoi (n-4) ? Si on choisit une diagonale, elle ne pourra couper les 2*(n-4) autres qui aboutissent aux extrémités, plus d'autres ... :=((

Dernière modification par Bernard-maths (24-01-2022 18:47:21)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#27 24-01-2022 18:42:43

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 072

Re : diagonales_d_un_polygone

Bonsoir,
sont elles bien toutes ôtées... ?
en tout cas l énoncé est très bref et je l 'ai recopié mot pour mot dans le premier post. Mais même un auteur prof de math, fût il Normalien et agrégé peut se tromper?

Bernard-maths a écrit :

Pourquoi (n-4) ? Si on choisit une diagonale, elle ne pourra couper les 2*6 autres qui aboutissent aux extrémités, plus d'autres ... :=((

C est ce que j essaie de voir sur ton schéma

Dernière modification par Zebulor (24-01-2022 18:47:13)


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#28 24-01-2022 18:48:25

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 314

Re : diagonales_d_un_polygone

C'est pas 2*6, mais 2*(n-4) !

Peut-êtr qu'il faut compter le nombre de sommets d'un côté, puis de l'autre, et en déduire le nombre de diagonales sécantes possible ... ?

En prenant les différents types de diagonales issues d'un sommet ?


En attendant, comment ai-je trouvé la formule de jpp ? Bien que je comprenne pas bien sa méthode ...

Je sui parti deN=n(n-3)/2 (an² + bn + c) ! Et j'ai identifié avec les valeurs connues pour n = 3, 4 et 5 ...ce qui donne (n²-3n+2)/3.

Et voilà !

Dernière modification par Bernard-maths (24-01-2022 19:12:08)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#29 24-01-2022 18:52:02

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 072

Re : diagonales_d_un_polygone

Peut être mais pour le moment je suis aveugle!

Zebulor a écrit :

chacune des N diagonales rencontre N-1-2(n-4) autres diagonales..

Je pressens que c est faux pour un polynome quelconque ..

sur ton schéma cette affirmation ne semble pas coller : chaque diagonale ne rencontre pas le même nombre de diagonales

@Bernard : par identification ?! pourquoi pas qui sait !

Les $C_n^{4}$? parce qu'il y a autant de côtés que de sommets. Et parce que 2 diagonales sont formées par 4 sommets, ce qui donne une intersection.

Le nombre total d'intersections est le nombre de quadruplets possibles pris parmi $n$ sommets.

Dernière modification par Zebulor (24-01-2022 22:07:24)


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#30 24-01-2022 20:15:04

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 314

Re : diagonales_d_un_polygone

Oui, je commence à mieux interpréter, un quadruplet est comme un quadrilatère, à 4 côtés et 2 diagonales ... Si on en choisit 2 sur les 6, les côtés se recoupent sur un sommet, ou pas, il ne reste que les 2 diagonales qui se coupent !

C'est bien vu. Et ma méthode a redonné le même résultat. Donc le corrigé est faux ???


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#31 24-01-2022 21:39:24

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 072

Re : diagonales_d_un_polygone

Bien vu de la part de jpp..
sauf manque de lucidité de ma part j'ai bien l'impression que le corrigé est faux !
Il écrit :
"Considérons une diagonale joignant deux sommmets A et B. Au mieux elle intersecte toutes les diagonales sauf elle même, les n-4 diagonales issues du sommet A et différentes d'elle même et les n-4 diagonales issues du sommet B et différentes d elle même.
Donc chacune des N diagonales rencontre N-1-2(n-4) autres diagonales. On obtient ainsi le nombre maximal de points d'intersection distincts.

En procédant ainsi, on a compté chaque point d'intersection deux fois (une fois par diagonale). Au total on trouve $\frac {n(n-3)(n^2-7n+14)} {8}$ points d intersection."

Est ce que ca ne serait pas plutôt :"un nombre maximal de points d'intersection". Parce que le nombre maximal semble bien être $C_n^{4}$ pour un polynôme irrégulier.. non?

Dernière modification par Zebulor (25-01-2022 09:16:46)


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#32 25-01-2022 18:59:38

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 314

Re : diagonales_d_un_polygone

Bonsoir Zebulor, et les zautres !

Le raisonnement énoncé est insuffisant, comme je l'ai remarqué en notant d'autres diagonales non sécantes ET ne passant pas par les 2 sommets de la diagonale choisie !

On se trompe bien nous-même, les autre aussi parfois. A moins que l'énoncé soit mal "énoncé" ...

Bonne nuit (ne nuit pas), Bernard-maths


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#33 27-01-2022 06:34:16

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : diagonales_d_un_polygone

Bonjour,

Deux diagonales se croisant à l'intérieur d'un polygone convexe à (N) sommets, dépourvu de tout élément de symétrie, sont caractérisées par les paires d'entiers (i, j) et (k, l) vérifiant les conditions:

0 < i < k< j < l ≤ N .

D'un point de vue algorithmique, le dénombrement des (s) points d'intersection (supposés non confondus) résulte de l'imbrication de 4 boucles:


0-->S
For(I, 1, N-3, 1)
For(J, I+2, N-1, 1)
For(K, I+1, J-1, 1)
For(L, J+1, N, 1)
S+1-->S
End:End:End:End

La durée d'exécution du programme augmente rapidement avec le nombre (N) de sommets; elle est probablement proportionnelle à N4.

Les résultats obtenus jusqu'à 20 sont donnés par le polynôme: s = N(N-1)(N-2)(N-3)/24 .

Dans le cas du décagone étudié par Bernard-maths, on retrouve bien le nombre de points d'intersections, égal à 210 .

1      2      3      4      5      6      7      8      9     10     11     12     13     14     15     16     17     18     19     20
0      0      0      1      5    15    35    70   126   210   330   495   715  1001  1365  1820  2380  3060  3876  4845

Dernière modification par Wiwaxia (27-01-2022 11:08:23)

Hors ligne

#34 27-01-2022 07:14:43

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 072

Re : diagonales_d_un_polygone

Bonjour,
merci Wiwaxia !


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#35 27-01-2022 10:44:24

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 314

Re : diagonales_d_un_polygone

Bonjour à tous !

Wiwaxia, merci pour ces calculs. Ta méthode numérique revient à ce qui suit géométriquement !

Je me permets de revenir sur la discussion #30, avec 2 figures pour illustrer :

LABjMoJ7ske_Bib-d%C3%A9cagone-et-diagonales-2022-01-27.png

La figure déjà vue, mais uniformisée ... puis le quadrilatère du choix de 4 sommets, édulcorée !

Ce quadrilatère (ici) a 4 sommets rouges non consécutifs, ses 4 côtés oranges sont des diagonales ayant un sommet en commun, donc "inintéressantes", mais ses diagonales mauves se coupent toujours en un point, rouge !

Ainsi chercher un point d'intersection de diagonales revient à chercher un quadrilatère.

Si il y a des sommets consécutifs, entre ces sommets, c'est un côté du (déca)-gone au lieu d'une diagonale, mais cela ne change pas la suite pour les 2 diagonales.

Et ça donne donc Cn4 façons de faire ! Que va pouvoir nous dire jpp !!!??? Hou hou !

Bernard-maths

Dernière modification par Bernard-maths (27-01-2022 10:52:40)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#36 27-01-2022 11:31:47

jpp
Membre
Inscription : 31-12-2010
Messages : 1 105

Re : diagonales_d_un_polygone

Salut ,

Mon raisonnement était celui-ci :

On choisit au hasard 4 sommets du polygone convexe irrégulier ;

A chaque choix , on génére un quadrilatère convexe et ses deux diagonales , ce qui donne un unique point d'intersection .

Le reste c'est de la combinatoire : il faut compter le nombre de ces quadruples de sommets .

[tex]N = C_n^4 = \cfrac{n!}{4!.(n-4)!} = \cfrac{n.(n-1).(n-2).(n-3)}{24}[/tex]

n , étant le nombre de sommets du polygone .

Hors ligne

#37 27-01-2022 11:36:22

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 072

Re : diagonales_d_un_polygone

Bonjour à tous!
salut Bernard et jpp.
Je me posais un tite question : celle de trouver le nombre de points d'intersections de diagonales d'un polygone convexerégulier de $n$ côtés.

Dernière modification par Zebulor (27-01-2022 11:37:07)


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#38 27-01-2022 12:03:33

jpp
Membre
Inscription : 31-12-2010
Messages : 1 105

Re : diagonales_d_un_polygone

Zebulor ;

Pour les polygones réguliers a côtes et sommets impairs je pense que la formule fonctionne aussi .

C'est une autre paire de manches avec les autres  a cause des multiples symétries . Chaque polygone "pair" est un cas a lui tout seul . Peut-être que Je me trompe .

Hors ligne

#39 27-01-2022 13:58:54

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 314

Re : diagonales_d_un_polygone

Hello jpp !

T'avais trouvé le bon truc dès le début, bravo  et merci !

Quant aux polygones réguliers convexes, on peut penser aux pairs et aux impairs ; aussi aux invariants ?

B-m


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#40 27-01-2022 15:00:23

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 072

Re : diagonales_d_un_polygone

Rebonjour,

Bernard-maths a écrit :

Le raisonnement énoncé est insuffisant, comme je l'ai remarqué en notant d'autres diagonales non sécantes ET ne passant pas par les 2 sommets de la diagonale choisie !

Est ce qu'on ne pourrait pas les dénombrer?


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#41 27-01-2022 18:39:52

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 314

Re : diagonales_d_un_polygone

Bonsoir Zebulor !

Maintenant que le tit problème est réglé, je n'ai plus vraiment envie de chercher plus, à moins que tu n'aies de bonne raisons ...

J'ai tellement d'autres choses en cours, et qui m'attendent !

Cordialement, Bernard-maths

Dernière modification par Bernard-maths (27-01-2022 18:40:26)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#42 27-01-2022 18:44:23

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 072

Re : diagonales_d_un_polygone

Bonsoir Bernard.
c'était une question ouverte pour tous... je comprends bien que chacun a ses occupations!
Cordialement de même


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#43 28-01-2022 10:08:31

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 314

Re : diagonales_d_un_polygone

Bonjour à tous !

Ce n'est pas parce que j'ai d'autres choses à poursuivre que mes neurones me laissent tranquille sur des questions subsidiaires !

Adonc, on peut chercher tous les points d'intersections de 2 diagonales, intérieurs ou extérieurs au polygone convexe, diagonales qui ne se coupent qu'en 1 point, donc autre que les sommets, en supposant, au plus, qu'aucune diagonale n'est parallèle à une autre ... Vu ?  Comparer les points intérieurs et extérieurs ... aussi !

Bon amusement, Bernard-maths.

Dernière modification par Bernard-maths (28-01-2022 10:12:18)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#44 28-01-2022 10:37:25

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : diagonales_d_un_polygone

Bonjour,

Bernard-maths a écrit :

... / ...Adonc, on peut chercher tous les points d'intersections de 2 diagonales, intérieurs ou extérieurs au polygone convexe, diagonales qui ne se coupent qu'en 1 point, donc autre que les sommets, en supposant, au plus, qu'aucune diagonale n'est parallèle à une autre ...

Les points d'intersection intérieurs et extérieurs des diagonales (i, j) et (k, l) ne diffèrent que par l'ordre mutuel des indices de ces dernières: en convenant de prendre:

Min(i, j, k, l) = i > 0; Max(i, j, k, l) ≤ N ; k < l ,

il se présente 3 possibilités:
a) i < j < k < l : points situés à l'extérieur du polygone;
b) i < k < j < l:  points situés à l'intérieur;
c) i < k < l < j : points située à l'extérieur,
3 cas à chacun desquels correspond une énumération particulière.

Donc en perspective deux autres programmes amusants.

Cordialement, W

PS: programmes qui, testés jusqu'à 20 et sauf erreur de programmation, conduisent aux mêmes résultats.
Tout se ramène en fait au dénombrement des combinaisons de quatre indices vérifiant (i, a, b, c) vérifiant:

0 < i < a < b < c ≤ N .

Le problème n'est pas pour autant résolu, car les contraintes sont insuffisantes et ne distinguent pas les diagonales des arêtes:  (j - i = 1 ou N-1) et/ou (l - k = 1 ou N-1).

Dernière modification par Wiwaxia (29-01-2022 08:42:46)

Hors ligne

#45 29-01-2022 14:57:17

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : diagonales_d_un_polygone

Bonjour,

Il faut reprendre le dénombrement à partir des restrictions les plus générales:

0 < i < j ≤ N; i < k < l ≤  N ,

en excluant les segments croisés, vérifiant par conséquent: k < j < l ,
et dont les intersections se situent à l'intérieur du polygone.

On est conduit à envisager 3 sortes d'intersection:
# celles de deux arêtes, caractérisées par [(j - i)=1 OU (N-1)] ET [(l - k)=1] ,
# celles de deux diagonales, caractérisées par [(j - 1)≠1 ET (N-1)] ET [(l - k)≠1] ,
# celles d'une arête et d'une diagonale;
d'où pour chaque valeur de (N) trois résultats dont la somme correspond au nombre total des intersections extérieures au polygone, soit 2*C(N4).

La programmation sur calculatrice reste possible bien que plus lourde, mais le temps d'exécution devient franchement rédhibitoire; il faut ici utiliser l'ordinateur.

LADnDoUsPBO_R%C3%A9sultats-N=4-80.png

Voici le cœur du programme de dénombrement:

 CONST Nmax = 80;

 TYPE Liste_E = ARRAY[4..Nmax] OF Z_32;

 VAR LstA, LstB, LstC, LstD: Liste_E;

 ... / ...

 PROCEDURE Enumeration(VAR L_A, L_B, L_C, L_D: Liste_E);
   VAR Dij, Dkl, N, N_1, i, j, k, l: Byte; Sa, Sb, Sc: Z_32;
       Aij, Akl, Bjkl, NAij, NAkl: Bool; La, Lb, Lc, Ld: Liste_E;
   BEGIN
     E(1015); Wt(5, 5, 'N ='); E(00110);
     FOR N:= 4 TO Nmax DO
       BEGIN
         N_1:= N - 1; We(15, 5, N, 6);
         Sa:= 0; Sb:= 0; Sc:= 0;
         FOR i:= 1 TO N_1 DO
           FOR j:= (i + 1) TO N DO
             BEGIN
               Dij:= j - i; Aij:= ((Dij=1) OR (Dij=N_1));
               NAij:= (Dij<>1) AND (Dij<>N_1);
               FOR k:= (i + 1) TO N_1 DO
                 FOR l:= (k + 1) TO N DO
                   BEGIN
                     Dkl:= l - k; Akl:= (Dkl=1); NAkl:= (Dkl<>1);
                     Bjkl:= ((k>j) AND (l>j)) OR ((k<j) AND (l<j));
                     IF Bjkl THEN
                       IF (Aij AND Akl)
                         THEN Inc(Sa)
                         ELSE IF (NAij AND NAkl) THEN Inc(Sc)
                                               ELSE Inc(Sb)
                   END
             END;
         La[N]:= Sa; Lb[N]:= Sb; Lc[N]:= Sc;
         Ld[N]:= (Sa + Sb) + Sc
       END;
     L_A:= La; L_B:= Lb; L_C:= Lc; L_D:= Ld
   END;

 BEGIN
   Enumeration(LstA, LstB, LstC, LstD);
   Aff_L;
 END.

Dernière modification par Wiwaxia (29-01-2022 16:19:03)

Hors ligne

#46 29-01-2022 15:29:21

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 072

Re : diagonales_d_un_polygone

Bonjour Wiwaxia,
voilà de quoi donner à réfléchir ou (re)donner le goût de programmer.
Merci


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#47 29-01-2022 17:28:09

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 314

Re : diagonales_d_un_polygone

Bonjour à tous !

Et tout cela n'exclut pas un ptite formule ?

euh ... combien y-a-t-il de droites, les côtés du polygone exclus ?

B-m


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#48 29-01-2022 22:48:07

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : diagonales_d_un_polygone

Bernard-maths a écrit :

... / ...Et tout cela n'exclut pas un ptite formule ?

euh ... combien y-a-t-il de droites, les côtés du polygone exclus ? ...

À priori, autant que de paires de sommets, soit N(N - 1)/2 , parmi lesquels les (N) côtés du polygone et N(N - 3)/2 diagonales.

Pour les nombres des divers points d'intersection, d'autres sont mieux armés que moi pour répondre.

Bonne fin de soirée, W.

PS: il n'est pas interdit de consulter l'Encyclopédie en Ligne des Suites Entières:
https://oeis.org/A000096
https://oeis.org/A212343
https://oeis.org/A117662

Dernière modification par Wiwaxia (29-01-2022 23:22:58)

Hors ligne

#49 30-01-2022 07:58:11

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : diagonales_d_un_polygone

Bonjour Bernard-maths

Bernard-maths a écrit :

... Et tout cela n'exclut pas un ptite formule ? ...

Et même plusieurs:

F1(N) = N(N - 3)/2
F2(N) = N(N - 3)(N-4)/2
F3(N) = N(N - 3)(N - 4)(N - 5)/12

qui impliquent un rapport simple entre chaque polynôme et le précédent:
F2(N) = F1(N)*(N - 4)
F3(N) = F2(N)*(N - 5)/6 .

La somme des 3 fonctions conduit à un résultat déjà connu:
F(N) = F1(N) + F2(N) + F3(N) = [N(N - 3)/12](N² - 3N + 2] = N(N - 1)(N - 2)(N - 3)/12 = 2*C(N4) .

Dernière modification par Wiwaxia (30-01-2022 08:35:02)

Hors ligne

#50 30-01-2022 13:30:23

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 314

Re : diagonales_d_un_polygone

Bonjour à tous !

Voilà bien une bonne démarche, me semble-t-il !

2*Cn4 = deux fois Cn4 ! Or Cn4 est le nombre de points d'intersections intérieurs au polygone ... donc il y en a autant dehors ! C'est ce qui m'a amené à vous poser la question ...

Autrement je ne retrouve plus le calcul qui m'avait donné ce résultat !??? Ou bien j'ai fait une erreur ?

B-m

Dernière modification par Bernard-maths (30-01-2022 16:38:10)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
quaranteneuf plus soixante quinze
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums