Bon, bah, cf le dessin. Je trouverais:
72 millions de pesos... sans être bien sûr

Les tronçons à construire sont d'abord des 4 moins chers :

5 8
5 7
1 4
3 7

Puis 3 des moins chers suivants, tout en vérifiant que le graphe final est bien connexe :

4 5
2 5
6 8

La minimalité du coût est facile à prouver : on a besoin d'au moins 7 tronçons pour faire communiquer les 8 stations, et on a pris les 7 tronçons les moins chers.

++

Bonjour,

Voici 2 solutions à 72 millions de pesos:

1-4  10
2-5  11
3-7  10
4-5  11
5-7  10
5-8  09
6-8  11

et

1-4  10
2-7  11
3-7  10
4-5  11
5-7  10
5-8  09
6-8  11


A+,
gloubi

J'oubliais la subsidiaire: Le dernier métro de françois (1980)

Juste avant de poster j'ai cru voir que j'ai oublié «Truffaut»

Pour calculer le nombre minimum de tronçons, on raisonne de la manière suivante :
Si on choisit un point au hasard, à chaque autre point correspond un tronçon pour raccorder ce dernier aux précédents.
Il y a donc au minimum n-1 tronçons. Donc ici 7 tronçons minimum.
Il suffit de vérifier si dans les 7 tronçons les moins chers on fait intervenir tous les points.
C'est le cas pour les tronçons :
à 9M de pesos :5-8
à 10M de pesos : 1-4,3-7,5-7
à 11M de pesos :2-5 ou 2-7, 4-5,6-8.
Pour un coût total de 9+30+33=72 M de pesos.

Q.S. : Le dernier métro ??

Bonjour
tout d'abord je suppose qu'il y a une seule ligne, c'est à dire qu'une station ne peut être liée à plus de 2 autres stations...
dans ce cas, le trajet le plus avantageux serait : 1-4-6-8-5-2-7-3 pour la modique somme de 75 millions de pesos!

dans l'autre cas, qui aurait été trop facil... la réponse aurait été
      2  
1-4-5-8-6
      7
      3
pour un total de 72 millions de pesos

mais je suppose que la réponse voulu était de 75...

merci minkus
Mathieu

Bonjour

voici ma reponse

Salut minkus, voici ma solution.
Tout d'abord, j'ai cherche un minimum possible: sachant qu'il faut construire 7 troncons, les 7 couts les plus petits sont: 09 10 10 10 11 11 11
Il est possible de les utiliser les 7; le reseau a construire sera alors:
(MP = millions de pesos)
5-8  9MP      5-7  10MP      3-7  10MP      1-4  10MP
4-5  11MP      6-8  11MP      2-5  11MP
Ceci donne un cout total de 72MP.

Pour la question subsidiaire, j'ai cru reconnaitre Gerard Depardieu; pourquoi cette image, je n'en ai aucune idee, alors je pense qu'il y a un rapport avec le metro; je parie qu'il y a une longue histoire d'amour en rapport avec le metro et que ceci est la fin heureuse de l'histoire.
(Si ceci est vrai, pourrais-tu SVP mettre dans ta reponse le nom du film et des principaux acteurs?)

Merci minkus pour ton petit challenge
dami22sui

bonjour :

je propose :

1-4
2-5
3-7
4-5
5-8
6-8
5-7

Ce qui couteras millions de pesos.

Bonjour,

Au risque de me tromper, je me lance quand même ...
Les liaisons utilisées sont :
    3-7 (10 M)

Bonjour,

Au risque de me tromper, je me lance...
Les tronçons utilisés sont :
   3-7 (10M)
   2-7 (11M)
   2-5 (11M)
   5-8 (09M)
   6-8 (11M)
   4-6 (13M)
   1-4 (10M)
Ce qui fait 75 M de pesos.  

Bonsoir minkus

Je conseillerais au président de construire les sept tronçons suivants : 6-8, 5-8, 4-5, 1-4, 5-7, 2-7, 3-7.
Cela coûtera 11 + 9 + 11 + 10 + 10 + 11 + 10 = 72 millions de pesos.

Le plan du métro montre que toutes les stations sont reliées entre elles :

6--8--5--4--1
           |
     2--7--3

Quant à Catherine et Gérard, aucune idée...

Cordialement
Frenicle

bonjour Minnkus
à partir de 5 : 54 (11) et 41 (10); 52 (11); 58 (9); 57 (10)
bifurcation en 7 : 73 (10) et 76 (11)
on peut aussi remplacer 76 par 86 (11)
coût : 9 + 10*3 + 11*3 = 72
le premier tronçon relie deux stations; tout nouveau tronçon relié à ce qui est déjà fait relie une nouvelle station; il faut donc sept tronçons; il suffit de choisir les moins chers

*challenge en cours*

Il faudra au minimum 7 tronçons pour relier les 8 stations

Si on regarde les tronçons il y a 1 tronçon (5-8) à 9 millions, 3 tronçons (1-4, 3-7 et 5-7 ) à 10 millions et 4 tronçons (2-5, 2-7, 4-5 et 6-8) à 11 millions. Le minimum de coût pour la construction de 7 tronçons sera de 9+3*10+3*11=72 millions.

Les solutions à 72 millions seront obtenues en prenant les tronçons à 9 et 10 et trois tronçons parmi les quatre à 11. Il ne reste plus qu'à vérifier si on dessert toutes les stations

En final on obtient deux solutions
Solution 1  avec les tronçons 1-4, 2-5, 3-7, 4-5, 5-7, 5-8 et 6-8
Solution 1  avec les tronçons 1-4, 2-7, 3-7, 4-5, 5-7, 5-8 et 6-8

Qui desservent l'ensemble des stations pour 72 millions, selon les schéma ci-dessous

Il faut un minimum de 7 tronçons, les moins chers étant, 5-8, 1-4, 3-7, 5-7, 2-5, 4-5 et 6-8 pour un coût total de 72 millions de pesos.
Question subsidiaire: Depardieu et Deneuve dans Le dernier métro de Truffault (comme le temps passe...)

Bonsoir,

si j'ai bien tt lu, alors on relie dans ce sens les stations:
1-4-5-8-6-2-7-3, et cela coute alors 75MP

L'image correspond au film "le dernier métro",avec Deneuve et notre Depardieu national....
a+

Pour relier les 8 stations entre elles, il faut au minimum 7 tronçons.
Si on trouve un réseau de 7 tronçons parmi les moins chers et qui connectent toutes les stations entre elles, on aura trouvé une solution.
Je propose la solution suivante, elle pèse 72 M, utilise 7 tronçons, dont celui de 9 M, les 3 de 10 M et 3 de 11 M parmi les 4 possibles (par contre, je te dis pas la galère pour relier S1 à S6) :

Les travaux les moin couteux suront de construire (dans l'ordre):
Le tronçon 1-4
Le tronçon 4-5
Le tronçon 5-8
Le tronçon 8-6
Le tronçon 6-2
Le tronçon 2-7
Le tronçon 7-3

Pour un cout total de : 75 millions de pesos ^^

Par contre la question subsidiaire ... Peu etre pour le plaisir de mettre une image =p

Bonjour,

Pour tout relier, il faut un minimum de 7 lignes.
En regardant les coûts minimums (ou minima), on voit un 9, trois 10, quatre 11.
Le minimum théorique pour 7 lignes serait alors de 9+10+10+10+11+11+11 = 72.

En pratique:
On prend les lignes 5-8 (9), 1-4 (10), 3-7 (10), 5-7 (10).
Ensuite, pour les lignes qui font 11, il y a 2-5, 2-7, 4-5, 6-8.
Le 6 n'est pas encore relié, il faut donc 6-8.
Les 1 et 4 sont isolés, il faut donc 4-5.
Il faut encore relier la 2, avec soit 2-5, soit 2-7.

Le coût sera donc de 72 millions de peso.
On a 2 solutions:

1-4 / 2-5 / 3-7 / 4-5 / 5-7 / 5-8 / 6-8
1-4 / 2-7 / 3-7 / 4-5 / 5-7 / 5-8 / 6-8

merci pour cette énigme.

_{N'empêche, un capitale avec seulement 8 stations de métro, c'est pas beaucoup...
Il doit sûrement s'agir de Grytviken...}

Tiens, je me rends compte que j'ai oublié la subsidiaire:
il s'agit d'un image du "dernier métro".

Bonsoir
Je propose le tronçon   1-4-5-8-6-2-7-3    pour 1 coût de 75 millions
A+

Donc je dirais:
il faut que la ligne passe, dans l'ordre, par les stations:
3 -> 1 -> 4 -> 8 -> 5 -> 7 -> 2 -> 6 ce qui couterait un total de 15+10+7+9+10+11+13= 75 millions de pesos

Merci pour l'énigme

Je propose cette solution à 72 millions de pesos.

Il construit les tronçons 1-4,4-5,3-7,7-5,5-8,8-6,7-2          
            1
            |
            4
            |
   3--7--5--8--6
        |
       2

pour 72 millions de pesos

Bonjour,

Je pense qu'il faut construire 7 tronçons pour assurer une desserte de toutes les stations avec un coût de construction minimal. Ce sont les tronçons (coût entre parenthèses) :

1 - 4 (10)
2 - 5 (11)
3 - 7 (10)
4 - 5 (11)
5 - 7 (10)
5 - 8 (9)
6 - 8 (11)

Cela donne un coût de construction total de 72.

Il y a une variante dont le coût et le nombre de tronçons sont identiques ; on y construit le tronçon 2 - 7 (11) à la place du tronçon 2 - 5 que j'ai indiqué dans ma solution.

Merci pour le défi.

Salut :

1-4
2-5
2-7
3-7
4-5
5-8
6-8

Tres cher président,
je vous propose de construire les tronçons:
1-4 / 4-5 / 5-8 / 8-6 / 6-2 / 2-7 / 7-3 pour une somme de 75M
si ce n'est pas assez, en rajoutant 15M on boucle la boucle (tronçon 3-1)
pour ce qui est de la photo je dirais que ce tramway se nomme désir...

le truc c'est qu'ilo doit y avoir 2 directions pour chaques stations sauf pour les deux terminus c'est pour cela qu'on voit G 2pardieu et C 2neuve

Alors pour faire le moins cher possible
On construit les trnçons suivant 1-4 4-3 3-7 7-5 5-8 8-6 6-2 ce qui nous donne un total de 77 millions de pesos

Bonjour,

Pour relier huit stations, il faut au moins 7 tronçons.
On peut se débrouiller pour construire le réseau complet avec les sept moins chers:
1-4 : 10 millions de pesos
4-5 : 11 millions de pesos
5-8 : 9 millions de pesos
8-6 : 11 millions de pesos
5-7 : 10 millions de pesos
7-3 : 10 millions de pesos
7-2 : 11 millions de pesos

Les stations sont bien toutes reliées et la construction coutera 72 millions de pesos.

merci pour l'ennigme

1/4
4/5
5/8
6/8
3/7
2/7
2/4

Et pour l'image je ne trouve pas!

Bonjour,

Le coût minimal était bien 72 millions de pesos et plusieurs solutions étaient possibles.

L'image était bien sûr extraite du "dernier métro" de François Truffaut et non pas du "tramway nommé désir"

minkus