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 : 3328

Réseau routire 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 : 2797
Lieu: Luxembourg

réseau roytier shadokien

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 : 4776

réseau rputier shadokien

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 : 3328

Réseau rutier Shadokien

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,601E+3

Réseu routier Shadokien

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 : 3133

téseau routier shadokien

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éeau 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éseua routier Shadokien

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 : 820
Lieu: Seahaven island

Réseau routier Shadokin

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 : 3003
Lieu: Fanning Island-?-Lac Tele,Mali

réseau routier sgadokien

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 : 1768

Réseua routier Shadokien

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 : 1383
Lieu: Coutiches

Réseau routier Shhadokien

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 router 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 : 1473

Réseau rouiter 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 : 2213

Réseau routier Shadokie

[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 : 3328

Réseau ruotier Shadokien

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 shadojien

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 : 3328

réqeau 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 : 1768

réseau routier shadojien

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 : 483
Lieu: Ardèche

Réseau routier Shaokien

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.

Résau routier Shadokien

273.205 = 273 Km

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

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

Réseau routier Shdokien

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 : 3328

réseau routier shasokien

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 routier shadokieb

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észau routier shadokien

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 : 

Dans une course, vous doublez le 19ème, en quelle position êtes-vous ?

Sujets similaires

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