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
[+]

 #26 - 06-11-2011 10:38:05

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 2209
Lieu: 94110

Réseau rouiter Shadokien

La longueur de route optimale s'obtient en traçant une route horizontale (ou verticale) centrée sur le centre du carré de longueur telle que les 4 routes joignant ses extrémités aux 4 sommets du carré forment un angle de 60° avec la direction du premier tronçon.
La longueur totale obtenue est alors de [latex]100 * (1+ sqrt(3))[/latex]
soit 273.205 km

#0 Pub

 #27 - 06-11-2011 16:46:24

fuyuki
Habitué de Prise2Tete
Enigmes résolues : 25
Messages : 13

Réseau routier Shadoken

en utilisant la méthode de l'arbre minimal de Steiner je trouve 273(,22) :
http://i41.servimg.com/u/f41/12/91/14/40/image_11.jpg
avec la distance qui est entre une ville et le le point de steiner opposé on a une distance de 100 km et la distance entre les deux point de steiner est d'environ 42,26 ...
donc on a : 4*100 - 3*42.26 = 273,22km

 #28 - 07-11-2011 00:54:09

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

Réseau routire Shadokien

Bravo à tous pour vos réponses. Il vrai que c'est un classique désolé pour le doublon.
Même si toutes vos démonstrations montre que le minimum est 273 km aucune ne prouve qu'il y a deux solutions. Voici donc démonstration qui permet d'en obtenir deux.

http://img4.hostingpics.net/pics/740644rseaushadock.png

Soit l'angle orienté [latex]x=(\vec{Ch};\vec{CF})[/latex].
Vous pourrez vérifier que:
[TeX]Fh=50.tan(x)[/TeX]
[TeX]EF=y=100(1-tan(x))[/TeX]
[TeX]BF=z=\frac{50}{cos(x)}[/TeX]
On cherche donc les angles [latex]x[/latex] vérifiant : [latex]4z+y[/latex] est minimal.
Soit [latex]f(x)=4z+y=4*\frac{50}{cos(x)}+100(1-tan(x))[/latex]

Alors [latex]\fbox{f'(x)=\frac{-5\pi*[cos^2(x)+sin(x)*(sin(x)-2)]}{9*cos^2(x)}}[/latex]

Je ne sis pas résoudre ce genre de chose pour trouver les extremum locaux du fait que la dérivée ne s'annule en aucun point, mais Wolfram Alpha donne :

[latex]x=\frac{\pi}{6}[/latex] ou [latex]x=\frac{5\pi}{6}[/latex] pour [latex]x \in [0;2\pi][/latex] avec une longueur minimale de 273 km

Shadock smile


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

 #29 - 07-11-2011 09:55:27

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

Réseau routier Shaokien

Hello,
C'est un carré tongue il n'y a pas à prouver qu'il y a deux solutions,  si on en a une on peut évidemment la tourner tongue et/ou la symétriser

Sur les arbres de Steiner en général on peut démontrer assez facilement que leur nœuds intermédiaires ont 3 branches et que ces branches sont à 120degres l'une de l'autre.

Pour les 120 degrés j'ai une demo sans calcul (mais qui ne sera peut être pas comprise de tout le monde, il faut certaines notions):

Imaginons donc 3 points A,B,C dans une disposition non pathologique (pas alignés etc...) et que ces 3 points soient reliés par un nœud intermédiaire avec donc 3 branches.
La fonction distance, qui a un point du plan associe la distance au point A a comme gradient en tout point (sauf A) un vecteur unité radial au point A. La fonction distance totale donc qui a un point du plan associe la somme des distances à  A B et C a donc un gradient qui s'annule lorsque 3 vecteurs unités respectivement radial à A B et C ont une somme nulle, ce qui arrive uniquement au point du plan ou les branches sont a 120deg l'une de l'autre.

Ça prouve extremum et non minimum mais on peut facilement prouver que c'est un min et non un max.
Comme on peut appliquer ce raisonnement sur toute sous partie de notre réseau même lorsque celui ci est plus gros on voit qu'il est stable uniquement dans ces conditions sur chaque nœud intermédiaire.

(Pour prouver qu'un nœud a 4 branches est plus couteux que 3 il faut faire le calcul une fois,  ici je ne prouve que l'histoire des 120 deg)

 #30 - 07-11-2011 10:47:14

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3823
Lieu: hébesphénorotonde triangulaire

réseau routuer shadokien

Bonjour,

Et si c'était un rectangle, au lieu d'un carré, y aurait-il deux solutions ?

[/fin du mode flemmard qui n'a pas envie de chercher]
Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #31 - 07-11-2011 11:54:26

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

Réseeau routier Shadokien

J'avoue que je ne comprends pas la réponse [latex]x=\frac{5\pi}{6}[/latex] : il me semble que d'après la figure, x ne peut pas dépasser [latex]\frac{\pi}{2}[/latex].

 #32 - 07-11-2011 15:22:48

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

réseau riutier shadokien

La valeur [latex]x=\frac{5\pi}{6}[/latex] c'est la même figure tournée de 90deg ou symétrisée par rapport à la diagonale principale.

Avec un rectangle (pas trop aplati) il y aurait 2 minimums locaux, avec cette forme, mais un seul serait minimum global, celui ou le segment milieu commun est parallèle au grand bord.

 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

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) — 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