Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#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?
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!
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
#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 :
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,
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,
... / ...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.
Voici le cœur du programme de dénombrement:
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
#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
... / ...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
... 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