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

Réseau routier Shaadokien

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.


 
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 : 3208
Lieu: Luxembourg

réseau routier shadokieb

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 : 5,382E+3

Réseu routier 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 : 3334

Réseu routier 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,896E+3

Réseau routier Shadookien

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

Réseau routier Sadokien

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éseau routier Shadokiien

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 Shadokein

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

Réseau routier Shhadokien

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

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

Réseau routier Shadokin

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

Réseau routier Shadkien

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

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

réseau routier shasokien

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

réseau routier shasokien

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

Réseau routier Shadoien

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 Shadokiien

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

Réseau ruotier 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 : 1819

Réseau rooutier Shadokien

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

Réseau routier Shadokie

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éseau routiee shadokien

273.205 = 273 Km

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

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

Réseau routtier 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 : 3334

Réseau routier Shadkoien

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 routiet 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 shadolien

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 31ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
30-10-2011 Enigmes Mathématiques
P2T
Nombre naturel dans un repère par gabrielduflot
27-07-2009 Enigmes Mathématiques
P2T
Et l'échelle choit par Vasimolo
27-10-2009 Enigmes Mathématiques
P2T
Mars attaque par Vasimolo
18-09-2011 Enigmes Mathématiques
P2T
11-09-2010 Enigmes Mathématiques
P2T
Suite logique par lerusse67
14-09-2013 Enigmes Mathématiques
02-07-2013 Enigmes Mathématiques
P2T
20-03-2019 Enigmes Mathématiques
P2T
Triangles par Anapurna
19-09-2009 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) — 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 quatre sommets d un carre de 100 km (3) — Quatres villes sont situees aux quatre sommets (3) — Reseau a un noeud maths route minimale (3) — Shadok construction (2) — Quatre villes sont situees aux quatre sommets d un carre. optimisation (2) — Quatre ville sont situees aux quatres sommets dun carre (2) — Calcule 273 avec 1-25-5-6-100-2 (2) — Quatre villes sont situees aux quatre sommets (2) — Quatres villes sont situees aux quatres sommets d un carre (2) — Cote carre png (2) — Quatre villes sont situees aux quatres sommets (2) — 4 villes sont situees aux 4 sommets (2) — Carre pose sur ses sommets (2) — 4 villes sont situees aux quatres sommets d un carre de cote 100km (2) — Quatres villes sont situees au sommets d un carre de cote 150 km (2) — Quatre villes sont situees aux quatres cotes (2) — La ville carre problemes (2) — Enigmes maths arbre (2) — Enigme calcul 273 (1) — Trouver 273 (1) — Quatre villes sont situees aux quatres sommet d un carre de cote (1) — Trouver 273 avec (1) — Dans le desert quatre villes sont situees aux sommets (1) — Quatre ville sont situees aux quatre sommets d un carre de cote (1) — Quatre villes sont situees au quatre sommets d un carre de cote 100kms. on se propose de relier (1) — Quatres villes sont situees aux quatres (1) — Quatre villes situees aux quatre sommets d un carre de cote 150km (1) — Reseau routier au mali (1) — Combien y a t il de 1 de 0 a 256 (1) — Reseau routier noeud (1) — Quatres villes sont situees (1) — Quatre villes sont situees aux quatre sommet d un carre de cote 100 km. (1) — Quatre villes situes aux quatre sommets (1) — Probleme de steiner et reseau de route (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 100 km (1) — Probleme des quatres villes (1) — Les routes le plus court possible a construir dans un carre pour joindre les quatre sommet (1) — Probleme quatre ville carre (1) — Quatre villes sont situees aux quatre sommets d un carre. calculer la longueur totale minimale du reseau (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) — Souhaite les relier par le reseau routier le plus court (1) — Probleme maths relier 4 villes a meme distance (1) — Reseau routier probleme (1) — R?seau routier 150km (1) — Quatre villes sont situees au quatre sommets d un carre de cote 150km (1) — Math probleme 4 villes situees aux 4 sommets d un carre (1) — Quatre villes sont situees aux quatre sommets d un carre pdf (1) — Quatres villes sont situes aux quatre sommets d un carre de cote (1) — Somme des distances aux sommets d un triangle (1) — Quatres villes sont situes aux quatre sommet (1) — Configuration du reseau routier au mali (1) — 4villes sont situes au 4sommets d un carr (1) — Quatre villes sont situees aux quatres sommets d un carre de 150 km (1) — Trigo derivation quatre villes aux quatre sommets (1) — Quatre villes sont situes aux quatres sommets d un carre de cote 150 km (1) — Quatre ville sont reliees aux quatre sommets (1) — Enigme parcours routier (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 villes sont situees aux quatres sommet d un carre de cote (1) — Quatre ville carre (1) — 4 villes sont situees aux 4 sommets d un carre de 100km de cote (1) — Quatre villes sont situees aus quatre sommets d un carre de cote 150km. on se propose de les relier par un reseau d autoroutes de longueur totale minimale. pour simplifier les calculs on convient que le cote du carre est egal a 1 (1) — Probleme d optimisation relier les sommets d un carre (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) — Steiner distance minimale ville (1) — Quatres villes sont situees aux quatres sommet d un carre de cote (1) — Enigme routier (1) — (1000001)? (1) — 4 villes distance carre enigme (1) — Quatres villes sont situees aux quatres sommets d un carre g(x) (1) — 4 villes sont situees au 4 sommet d un carre on propose de les reliees (1) — Ville carr?e (1) — Quatre villes sont situees aux quatre sommets d un carre de cote (1) — Quatre villes sont situees au sommet (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