Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 30-10-2011 17:42:55

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3332

Réseaau routier Shadokien

Tout comme Clydevil je vous propose une énigme de minimisation d'un parcours routier.


Problème :

Quatre villes (shadoks), GA, BU, ZO et MEU sont situées sur les sommets d'un carré de côté 100 km.
La direction départementale de l'équipement souhaite les relier les unes aux autres par un réseau routier le plus court possible.

http://img11.hostingpics.net/pics/488460ReseauroutierShadock.png

Au début ils pensèrent relier les 4 villes par un réseau simple de 300 km de ville en ville. Mais grâce au Théorème de Pythagore qu'ils maîtrisent sur le bout des doigts ils trouvent un réseau constitué des 2 diagonales du carré totalisant 282 km. Malheureusement leurs ingénieurs savent qu'il existe une meilleure solution qu'ils ne trouvent pas...
Pouvez-vous les aider ?

Amusez-vous bien! smile
Shadock

CASE REPONSE : Réponse en kilomètre arrondi au plus près.



Annonces sponsorisées :

 
Réponse :

"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
  • |
  • Répondre

#0 Pub

 #2 - 30-10-2011 18:02:35

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2844
Lieu: Luxembourg

réseau routier shasokien

Bonjour,
Les quatre villes sont reliées à un axe central de longueur 50 km.
D'où L = 50 + 4 V(25²+50²) = 50 + 100 V5 = env. 273,6 km.
Mais pour démontrer rigoureusement que ce réseau est optimal ... ?
Bonne soirée.
Frank

 #3 - 30-10-2011 18:28:34

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4981

réseau routier shadokizn

Un petit article sur cet intéressant problème lié à celui de Steiner : http://apmeplorraine.free.fr/modules/probleme/PB53.pdf

Vasimolo

 #4 - 30-10-2011 18:36:29

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3332

Réseau routier SShadokien

Je ne connaissais pas merci big_smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #5 - 30-10-2011 18:40:34

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,708E+3

Réseau routier Shaodkien

Je ne suis pas sûr du  lien mais ça me rappelle un truc posté il y a peu...
http://www.prise2tete.fr/forum/viewtopic.php?id=8325

273 km   ?

 #6 - 30-10-2011 20:12:06

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3227

Réseau routier Shaadokien

Je connais, il faut prendre des angles 120°. D'ailleurs c'est une généralité pour rejoindre 3 points disposés de façon aléatoire, à la condition qu'il n'y a pas un des 3 angles>120°.

 #7 - 30-10-2011 20:28:23

Cédric-29
Habitué de Prise2Tete
Enigmes résolues : 16
Messages : 17

réseay routier shadokien

Imaginons que GA et MEU soient reliées par un élastique ainsi que BU et ZO et que l'on cherche à rapprocher les centres de ces deux élastiques. En résolvant le problème d'optimisation de la distance totale, on s'aperçoit qu'il n'est pas nécessaire qu'ils se touchent (où l'on retrouverait alors la configuration diagonale) pour obtenir la distance totale minimale de  [latex]100(1+\sqrt{3})[/latex]) soit 273 km.

Je ne sais pas prouver qu'il s'agit du meilleur résultat possible, ce n'est d'ailleurs peut-être pas le cas, mais n'imaginant pas qu'il puisse y avoir des courbes dans la solution optimale, cette solution me paraît être une bonne candidate.

 #8 - 30-10-2011 21:14:42

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

réseau routier shadojien

Sentiment de déjà-vu...

La minimisation de la longueur totale me semble passer par l'existence d'un axe central :

http://www.prise2tete.fr/upload/MthS-MlndN-488460ReseauroutierShadock.png

La longueur totale de la route ainsi tracée (avec un peu de Pythagore et deux calculs à la noix) est de [latex]4 \sqrt{50^2+x^2}+100-2x[/latex].

La dérivée par rapport à x de ce truc vaut [latex]\frac{4x}{\sqrt{50^2+x^2}} - 2[/latex] ; elle s'annule quand [latex]2x=\sqrt{50^2+x^2}[/latex] soit, en passant au carré, [latex]x=\frac{50}{\sqrt{3}}[/latex], et la distance, qui est alors minimale (je passe l'étude de signes rébarbative), vaut [latex]100+100 \sqrt{3}[/latex] soit un peu plus de 273 kilomètres.


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #9 - 30-10-2011 22:05:55

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 851
Lieu: Seahaven island

réseau routiee shadokien

Je ne connaissais pas merci

Tu veux dire les Steiner tree? :p
De manière général c'est NP complet mais par contre on sait caractériser les minimums.
Ce sont des arbres, donc les nœuds intermédiaires ont 3 branches toujours à 120deg l'une de l'autre.
Avec un rectangle et non un carré par exemple on en trouve 2 qui "marchent" mais un seul minimum global, c'est ce genre de choix qui en fait un problème NP.

 #10 - 31-10-2011 00:58:24

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

réseau toutier shadokien

Je donne la meme solution que pour clydevil, ce qui pour ton enigme donne 273.205080758

J'explique.
Je joins 2 villes 2 a 2 en diagonale sur une longeur de Y = 57.735026919
puis je join ces 2 points de rencontre au centre ou chaque demi segment est egal a X  = 21.132486541

pour trouver il suffit de trouver le plus court chemin total de 2Y+X. soit la derivee de 2Y+x =0
ou encore trouver X qui repond a l'equation: 3X^2+300X+5000=0

PS: on avait deja resolu ce genre de probleme avec des fournis ou taupes qui creusent des tunnels....


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #11 - 31-10-2011 06:28:45

NickoGecko
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1772

Réseau routier Shadokiien

Bonjour,


La géométrie suivante me semble minimiser la longueur totale du réseau, et je ne me suis pas foulé pour la dérivée grâce à Wolfram Alpha.

http://www.prise2tete.fr/upload/NickoGecko-reseaushadock.jpg


La longueur totale du réseau minimale dans cette configuration vaut 273,2 km, pour "x" valant 21,13 km.

Resterait à prouver qu'il s'agit bien de la solution minimale "absolue".

Bonne journée,


Il aurait pu pleuvoir, con comme il est ! (Coluche)

 #12 - 31-10-2011 07:10:26

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1415
Lieu: Coutiches

Réseau routier Shdaokien

J'obtiens 273.3 avec un H qui cherche à ressembler à un X smile

 #13 - 31-10-2011 09:42:50

Promath-
Elite de Prise2Tete
Enigmes résolues : 18
Messages : 1416
Lieu: Au fond de l'univers

réseau routirr shadokien

J'ai trouvé 273 en tracant un segment qui passe par le milieu de 2 côtés opposés et en prenant 1/4 de la longueur pou neutral trcer une diagonale heu:: m'a tu compris?


Un promath- actif dans un forum actif

 #14 - 31-10-2011 11:02:27

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1530

Résau routier Shadokien

On va imaginer un réseau qui serait composé d'une ligne droite de longueur X, située à 50 km au nord / au sud des villes; terminées par 4 lignes droites (de même longueur) qui relient une ville à l'extrémité de ligne la plus proche.

Si la ligne droite est de longueur X, les portions qui la relient aux villes sont de longueur [latex]\sqrt{(\frac{100-x}{2})^2+50^2}[/latex]
Du coup, le réseau mesure alors au total
[TeX]x+4\sqrt{(\frac{100-x}{2})^2+50^2}[/TeX]
On cherche à minimiser sa taille totale: calculons la dérivée.
[TeX]1+\frac{x-100}{\sqrt{(\frac{100-x}{2})^2+50^2}}[/TeX]
Celle-ci s'annule pour
[TeX]100-x = \sqrt{(\frac{100-x}{2})^2+50^2}\\
(100-x)^2 = (\frac{100-x}{2})^2+50^2\\
20000 -600x + 3x^2 = 0\\
\Delta = 360000-240000 = 120000 = (200\sqrt{3})^2\\
x = 100-100\frac{\sqrt{3}}{3}
[/TeX]
(l'autre solution est supérieure à 100)
Pour x inférieur à cette valeur, la dérivée est négative; et positive pour x supérieur.
Du coup, le minimum est atteint pour cette valeur de x, et vaut
[TeX]100(1+\sqrt{3})[/TeX]
soit environ 273 km

 #15 - 01-11-2011 02:54:09

FRiZMOUT
Verbicruciste binairien
Enigmes résolues : 49
Messages : 2216

Réseau routier Shadoken

[latex]100(1+sqrt(3))[/latex] km.

http://upload.wikimedia.org/wikipedia/commons/e/e4/Steiner_4_points.svg

 #16 - 01-11-2011 11:09:53

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3332

réseau routier shafokien

A force de connaitre les énigmes par coeur vos réponses deviennent compendieuses.

A la fin je vous proposerai ma solution (peut-être un peu capilotracté) mais qui n'a pas encore été proposée. smile

Bonne continuation à ceux qui cherche, et bravo à ceux qui trouve.
Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #17 - 01-11-2011 12:36:09

Psykotaker
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 28
Lieu: Université Paul Verlaine

réseau routier shadokieb

Voila ce que je propose

http://img4.hostingpics.net/pics/656150ReseauroutierShadock.jpg

On relie à mit chemin entre GA et BU un péage A qui relie le péage B qui se trouve lui même à mit chemin entre MEU et ZO

Donc les distance GA-ZO et BU-MEU seront de... 200 Km !

Il est inutile d'ajouter une route similaire entre le milieu de [MEU GA] et le milieu de [BU ZO], on obtiendrais les même résultats...


Je ne pense pas que se soit la solution attendu... C'est beaucoup trop simpliste...


Quand les choses deviennent trop compliquées, il est parfois normal [...] de se demander : ai-je posé la bonne question ?

 #18 - 01-11-2011 14:41:46

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3332

Résau routier Shadokien

En revanche la distance total de ton parcours :
De GA à BU = 100 km
De Zo à MEU = 100 km
Et de A à B =100 km
Conclusion 300 km...


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #19 - 01-11-2011 14:58:26

NickoGecko
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1772

Réseau routier Shadoken

J'ai appris le mot "compendieux" aujourd'hui, comme quoi, ce post n'était pas si redondant que cela !
Et j'utilise de + en + Wolfram !
Donc : merci !


Il aurait pu pleuvoir, con comme il est ! (Coluche)

 #20 - 01-11-2011 17:27:30

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 491
Lieu: Ardèche

réseau rputier shadokien

Problème connu.
L'arbre de Steiner donne pour longueur minimale [latex]100(1+\sqr3)[/latex]
soit 273.2 km

 #21 - 02-11-2011 01:28:47

freedomAO
Habitué de Prise2Tete
Enigmes résolues : 49
Messages : 12
Lieu: Vottem; Liège; Belgique.

téseau routier shadokien

273.205 = 273 Km

 #22 - 02-11-2011 11:40:20

Bamby2
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 152

Résaeu routier Shadokien

je poste ce lien ici, car perso je n'ai jamais trop réfléchis sur les ellipses, et la j'y trouve une belle application smile
http://xavier.hubaut.info/coursmath/app/minima.htm

 #23 - 02-11-2011 13:33:37

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3332

Réseau routier Shdokien

A la demande de certain joueurs les deux énigmes sur les réseaux routiers finiront en même, d'où un rajout d'heure pour celle-ci.

Encore plein de bonne réponse.  smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #24 - 02-11-2011 14:31:52

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

réseau eoutier shadokien

100+100√3

Avec une forme d'enveloppe, les calculs sont pas méchants mais fastidieux à réécrire ici.

 #25 - 03-11-2011 22:56:21

nicolas647
Passionné de Prise2Tete
Enigmes résolues : 24
Messages : 96

Réseau routier SShadokien

Le réseau doit ressembler à ça :

http://www.prise2tete.fr/upload/nicolas647-res-shad.png

En choisissant bien les longueurs, la longueur totale du réseau est de :
[TeX]\frac8{\sqrt3}+2(1-\frac1{\sqrt3})\approx273[/TeX]

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

Sujets similaires

Sujet Date Forum
30-10-2011 Enigmes Mathématiques
28-10-2011 Enigmes Mathématiques
14-10-2010 Enigmes Mathématiques
P2T
Oooooor par SaintPierre
07-04-2011 Enigmes Mathématiques
P2T
Enigme des oeuf par kais6928
07-06-2011 Enigmes Mathématiques
P2T
Un peu de physique... par SaintPierre
12-02-2011 Enigmes Mathématiques
P2T
La ronde des fourmis par Vasimolo
16-10-2009 Enigmes Mathématiques
P2T
Premiers? par Yanyan
22-12-2011 Enigmes Mathématiques
11-09-2008 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)
Quatre villes sont situees aux quatre sommets d un carre (27) — Quatre villes sont situees aux quatre sommets d un carre de cote 150 km (12) — Quatre villes sont situees aux quatre sommets d un carre de cote 100 km (9) — Quatres villes sont situees aux quatres sommets (6) — Quatre villes sont situees aux quatre sommets d un carre de cote 150km (4) — Calcul enigme obtenir 273 avec 1 25 5 6 2 100 (4) — Reseau a un noeud maths route minimale (3) — Quatres villes sont situees aux quatre sommets (3) — Quatre villes sont situees aux quatre sommets d un carre de 100 km (3) — Quatres villes sont situes aux quatres (3) — 1-distance entre le noeud et l arbre (distance de steiner) (3) — 273 avec 1 25 5 6 100 2 (3) — Quatres villes sont situees au sommets d un carre de cote 150 km (2) — 4 villes sont situees aux 4 sommets (2) — Quatre villes sont situees aux quatre sommets (2) — Carre pose sur ses sommets (2) — 4 villes sont situees aux quatres sommets d un carre de cote 100km (2) — La ville carre problemes (2) — Quatre villes sont situees aux quatres cotes (2) — Calcule 273 avec 1-25-5-6-100-2 (2) — Enigmes maths arbre (2) — Quatre ville sont situees aux quatres sommets dun carre (2) — Quatre villes sont situees aux quatre sommets d un carre. optimisation (2) — Quatre villes sont situees aux quatres sommets (2) — Cote carre png (2) — Quatres villes sont situees aux quatres sommets d un carre (2) — Shadok construction (2) — Enigme parcours routier (1) — Quatre ville carre (1) — Enigme de trouver la distance la plus court entre 4 villes (1) — Quatres villes sont situees aux quatres sommet d un carre (1) — Quatre ville sont reliees aux quatre sommets (1) — 4 villes sont situees aux 4 sommets d un carre de 100km de cote (1) — Trigo derivation quatre villes aux quatre sommets (1) — Somme des distances aux sommets d un triangle (1) — Ville carr?e (1) — Quatres villes sont situes aux quatre sommet (1) — Configuration du reseau routier au mali (1) — Quatre villes sont situees aux quatres sommets d un carre de 150 km (1) — Quatre villes sont situes aux quatres sommets d un carre de cote 150 km (1) — Quatre villes sont situees aux quatres sommet d un carre de cote (1) — 4villes sont situes au 4sommets d un carr (1) — Quatre villes situes aux quatre sommets (1) — Quatres villes sont situes aux quatre sommets d un carre de cote (1) — (1000001)? (1) — Quatres villes sont situees aux quatres sommets d un carre g(x) (1) — 4 villes distance carre enigme (1) — 4 villes sont situees au 4 sommet d un carre on propose de les reliees (1) — Enigme routier (1) — Quatres villes sont situees aux quatres sommet d un carre de cote (1) — Probleme d optimisation relier les sommets d un carre (1) — Steiner distance minimale ville (1) — Diagonale dans un reseau routier carre (1) — Quatres villes sont situees aux quatre sommets d un carre (1) — Qutres villes quatres sommets d un carre de cote 150 km (1) — Quatre villes sont situees aux quatre sommets d un carre de cote (1) — Quatre villes sont situees aux quatre sommets d'un carre de cote 100 km (1) — Probleme quatre ville carre (1) — Quatre villes situees aux quatre sommets d un carre de cote 150km (1) — Quatres villes sont situees aux quatres (1) — Reseau routier noeud (1) — Quatre villes sont situees au quatre sommets d un carre de cote 100kms. on se propose de relier (1) — Quatres villes sont situees (1) — Trouver 273 avec (1) — Quatre ville sont situees aux quatre sommets d un carre de cote (1) — Dans le desert quatre villes sont situees aux sommets (1) — Trouver 273 (1) — Enigme calcul 273 (1) — Quatre villes sont situees aux quatre sommet d un carre de cote 100 km. (1) — Quatre villes sont situees aux quatres sommet d un carre de cote (1) — Reseau routier au mali (1) — R?seau routier 150km (1) — Quatre villes sont situees aux quatre sommets d un carre pdf (1) — Probleme maths relier 4 villes a meme distance (1) — Souhaite les relier par le reseau routier le plus court (1) — Reseau routier probleme (1) — Math probleme 4 villes situees aux 4 sommets d un carre (1) — Quatre villes sont situees au quatre sommets d un carre de cote 150km (1) — Quatre villes sont situees aux quatre sommets d un carre de cote 150 km. on se propose de les relier par un reseau (1) — Quatre villes a b c et d sont situees aux quatres sommets d un carre de cote 100km. a (1) — Quatre villes sont situees au sommet (1) — Quatre villes sont situees aux quatre sommets d un carre. calculer la longueur totale minimale du reseau (1) — Probleme de steiner et reseau de route (1) — Probleme des quatres villes (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete