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

Réesau 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 : 2715
Lieu: Luxembourg

Réseau routier hSadokien

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

réseay 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 : 3319

Réseau routier Shadokin

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

réseau routier shadpkien

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

Réseau routier Shhadokien

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 routierr 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 roitier 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 : 808
Lieu: Seahaven island

réseau routier shadolien

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

résezu routier 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 : 1747

téseau 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 : 1374
Lieu: Coutiches

réseau riutier shadokien

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 rotier 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 : 1434

Réseau rouier 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 : 2211

Réseau routier Shadokine

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

Réseau routier hSadokien

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 Shadoien

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

réseau routier shadokoen

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

Réseau routier SShadokien

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 : 479
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.

réseau routier dhadokien

273.205 = 273 Km

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

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

résrau 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 : 3319

Réseau routier Shadkien

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édeau routier 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 Shadokienn

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

Sujets similaires

Sujet Date Forum
30-10-2011 Enigmes Mathématiques
P2T
15-12-2014 Enigmes Mathématiques
16-12-2015 Enigmes Mathématiques
P2T
Des nombres binaires par Promath-
20-12-2015 Enigmes Mathématiques
P2T
Maths et guerre par fr-de-f11
08-12-2008 Enigmes Mathématiques
P2T
Un cadeau exigeant par Lise-et-Paris
22-10-2013 Enigmes Mathématiques
P2T
Preuve 2=1 par Mariiella
12-09-2011 Enigmes Mathématiques
27-10-2011 Enigmes Mathématiques
P2T
L'indice de l'air par nodgim
15-10-2016 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) — 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