Inscription / Connexion Nouveau Sujet
Arbre de Steiner
Bonsoir à tous,
Comment relier les 6 points suivants (sommets de carrés de coté 1km) en utilisant un réseau de longueur totale minimale ?
On ne demandera pas la démonstration du minimum, c'est en général un problème NP-complet 
Donc n'hésitez pas quelque soit la valeur que vous proposez, le gagnant sera celui qui propose la plus petite longueur et vous avez le droit à plusieurs offres 
Bonjour,
Le réseau est dessiné n'importe où dans le plan, pas seulement en suivant les lignes pointillées.
Effectivement j'ai juste mis des pointillés pour qu'on comprenne la configuration des points mais on peut les relier comme on veut.
J'ai de gros doutes sur la faisabilité de la proposition de derny, peux tu nous expliquer comment tu fais ?
Cliquez pour afficherToi au moins dpi je te crois sur parole mais tu es passé par où pour avoir une telle valeur ?
Si on trace juste ABCDEF tous les points sont reliés et la distance est 5. On peut mieux faire bien sûr.
j'ai relié tous les points avec tous les autres ...en effet un réseau de
5 ne relie pas par exemple A avec E directement....
salut
en reliant simplement AE, EC et E relié à B, D et F on trouve
je pense qu'on peut faire mieux en connaissant l'arbre de Steiner à quatre points et par symétrie par rapport à la médiatrice m du segment [AF] en considérant trois points P, Q et R sur m avec :
P relié à A et F, R relié à C et D
et Q relié à B et E (et même probablement Q milieu de [BE])
dpi, je viens de comprendre, tu as fais la somme de toutes les distances entre 2 points. Je suis d'accord sur le calcul mais ce n'est pas vraiment la question donc c'est normal que tu sois bien au-dessus de la valeur attendue. Je préfère le problème initial parcequ'on doit choisir un chemin justement mais ta question est intéressante aussi.
carpediem je confirme qu'on peut faire mieux et sans trop se compliquer la vie, pourquoi donc tracer AE et EC ? Tu atteins le point F et le point D, quel sera le chemin le plus court pour atteindre A et C en partant de F et D ?
Re-bonjour
J'ai fait ça rapidement sur un coin de table donc je me suis peut-être trompé dans mes calculs (je vous laisse contrôler en fonction du croquis ci-dessous).
Effectivement et cela revient à la même chose que ce qu'expliquait carpediem dans un second temps.
Faisons le calcul pour convaincre derny, en prolongeant la droite horizontale, qui nous donne 4 triangles rectangle.
Donc longueur totale
C'est une belle idée mais on peut effectivement faire mieux, enfin peut-être pas mieux que mathafou quand même mais on peut donner la valeur exacte
J'aime bien le travail des abeilles de mathafou
le segment NOP donne le meilleur résultat avec un angle
35°9 par rapport à la verticale.
Vassillia : oui je donnais un exemple simple pour descendre en dessous de 5 ...
en fait avant de proposer ce que j'ai ensuite proposer comme idée et traduit par la figure de derny avec trois points j'étais aussi parti sur l'idée de quatre points + le milieu de [BC] ... mais pas été aussi loin que l'expert mathafou 
bon j'avais cours ... mais je ne pense pas que j'aurai trouvé car j'avais conservé les points M et Q sur la médiatrice de [AF] ...
carpediem tu es sur que est inférieur à 5 ?
Mais passons, c'est pas important, au final vous avez eu la bonne idée avec l'angle de 120° mais il faut effectivement en mettre partout comme le propose mathafou.
Et c'est pour cette raison que je ne pense pas non plus qu'on puisse faire mieux. Par contre allez encore un petit effort pour la valeur exacte ? Si personne ne se dévoue, je le ferai.
Sur la figure de Mathafou, les points FMA sont sur un cercle de rayon 1/V3 et OMB sont sur un cercle de rayon 1/2V3. Il se pourrait (simple intuition) que MN soit sur la droite joignant les 2 centres.
>carpediem
J'avais vu.....
>derny
Je sais que tu est un spécialiste de ce genre.
J'ai essayé ok pour le cercle de rayon 1/
3 passant par FMA ;par contre ne serait-ce pas ONB pour l'autre.
Ah oui forcément, ça va être plus facile de minimiser la longueur totale si on calcule comme carpediem 
mais bon ça arrive à tout le monde et puis si tu pensais à tes élèves du cours d'après, tu as une bonne excuse
Bonne idée derny, ce ne sera pas les centres mais construire les cercles circonscrits à FMA et ONB va nettement faciliter le calcul
Bonjour,
Tout d'abord j'ai oublié de remercier Vassillia pour ces questions variées et intéressantes 
Ensuite, pour
Il se pourrait (simple intuition) que MN soit sur la droite joignant les 2 centres.
Mais je trouve ainsi 4,628454 comme valeur approchée, au lieu des 4,625 annoncés par mathafou.
Et les angles ne sont pas tous de 120°.
il ne s'agit pas de la ligne des centres !
sur la figure
pour avoir 3 angles de 120° en M (condition nécessaire pour une distance totale minimale)
la droite (MN) est bissectrice de l'angle AMF
elle doit donc passer par un certain point qui n'est pas le centre du cercle (AMF) mais ...
(angles inscrits etc)
la figure clé sur les bissectrices d'angles inscrits :
et pareil pour l'autre cercle avec un point J défini de même
donc la droite (MN) cherchée est la droite (IJ)
Ah ben ça avance, bravo mathafou
Je vous recommande l'utilisation de ce théorème pour ceux qui ne le connaissent pas mais vous n'êtes pas obligé de cliquer sur le lien si vous voulez chercher sans
Bonjour
je me suis permis d'ôter les h surnuméraires dans les mots "hypoténuse" du 28-09-21 à 14:04, ça me piquait trop les yeux
super problème, très intéressant, et super contributions des intervenants !
Bonjour,
Au réveil...
En prenant les cercles de derny et un angle générateur de 30° on obtient une salade de 3
soit 4.7643319..
Donc il faut travailler sur l'angle pour confirmer mathafou
Après des calculs bourratifs...
L'angle cherché est 36.20602312° et le total des segments 4.625181601..
Avec la structure en "abeille" on ne trouve pas mieux
Je peux donner tous les segments si nécessaire.
Bonjour dpi, perroquet et à tous
Vous êtes d'accord sur la solution. Je pense qu'à présent il est inutile de blanker. Perroquet, peux-tu donner le détail de ta solution qui donne en effet une solution simple (cela me ferait gagner du temps car, malheureusement, j'ai des obligations qui me privent de temps et de sérénité indispensables pour ce genre de problèmes).
Je me permets de compléter la figure de mathafou.
On a AM+MF+MN+NB+NO = IJ.
Je me sers de l'indication de mathafou sur la bissectrice de l'angle inscrit et de celle de vassilia (théorème de Ptolémée) pour les quadrilatère inscrits AMFI et BJON.
Ah oui !!!
étant donné un triangle équilatéral inscrit dans un cercle
quel que soit M sur l'arc (AB) on a MA+MB =MC
en effet Ptolémée dixit
MB.AC + MA.BC = MC.AB et comme AB = BC = AC ...
Bien vu GBZM, je fais comme toi, et ensuite ça vient facilement avec Pythagore. Jolie persévérance dpi, je ne suis pas une grande adepte des calculs bourrins mais je ne veux pas t'en décourager pour autant.
@derny et @dpi:
le principe de mon calcul est à peu près celui que @GBZM expose le 29 septembre à 9h13 (j'utilise un segment deux fois plus long), et il y a une démonstration par @mathafou à 10h18.
Bonsoir
« je reviens ».
Merci à tous pour cette démonstration élégante (et merci aussi à titre posthume à Ptolémée).
Je viens de trouver une nouvelle façon élégante de résoudre ce problème.
Traçons toujours les 2 cercles O1 et O2 de rayons 1/V3 et 1/2V3.
Traçons AO et BF qui se coupent en V. Ce point est donc le point d'inversion des parties droite et gauche et de rapport ½. V sera donc aux 2/3 de MN. Ses coordonnées sont donc faciles à calculer ainsi que AV.
Traçons la médiatrice à AV. A une distance de la droite AV de AV/2V3 se trouve le centre O3du cercle passant par AMV. L'intersection des 2 cercles O1 et O3 donne le point M. Puis sur la droite MV on aura N (MV=2VN).
Annuler
connectez vous