Forum des énigmes mathématiques :
Defi 207 : Tous les chemins mênent à Rome...

Salut,

Une petite idée d'énigme me traîne dans la tête depuis quelques jours et après avoir réfléchi à sa mise au point, je pense qu'elle mérite ses 4 étoiles. Vous me direz ce que vous en pensez.

Alors voilà. Le principe est très simple. La station de métro (parisien) la plus proche de chez moi est la station MOUTON-DUVERNET sur la ligne 4 au sud. J'ai décidé de faire une petite visite du métropolitain en me rendant à la station ROME (au nord-ouest sur la ligne 2) en empruntant exactement une fois chaque ligne.

De plus les règles suivantes sont à respecter :

*"Emprunter une ligne" signifie faire un trajet entre (au moins) 2 stations de la ligne. Passer par une station de la ligne ne suffit pas.
* Les lignes concernées sont les lignes 1;2;3;4;5;6;7;8;9;10;11;12;13;14.
* Les petites lignes de jonction 7bis et 3bis ne sont pas concernés mais il est possible de les emprunter .
* En revanche, il est interdit d'emprunter le RER ou le Tramway.
* Il est possible de passer plusieurs fois par la même station, y compris celle de départ et celle d'arrivée.
* Attention aux stations multiples ! Par exemple, les stations CHATELET, LES HALLES et CHATELET-LES HALLES sont 3 stations distinctes.
* Il est bien sûr interdit de sortir du métro pour changer de ligne. En revanche, marcher en sous sol pour prendre une correspondance est autorisé. Certaines longues correspondances sont indiquées en blanc. (Par exemple le trio mentionné juste au-dessus.) Il est ainsi possible, lors d'une correspondance, de passer par une station de RER sans emprunter ce dernier.

Voilà. J'espére n'avoir rien oublié. Je joins une photo du plan de métro mais je vous conseille d'aller sur le site de la RATP pour en obtenir une version plus lisible.



La question est la suivante :

Quel est le nombre minimum de stations que je dois emprunter pour réussir ce périple ?

Vous indiquerez dans votre réponse la suite des stations visitées.

Bon courage !

minkus

PS : J'avoue ne pas avoir (encore) cherché de réponse à ce problème. On verra qui obtiendra le meilleur score !

C'est vraiment un coup à prendre un poisson. Seul le meilleur score sera récompensé, mais je me lance.
Voici le périple que j'ai imaginé.

Ligne 4 : Mouton Duvernet - Denfert Rochereau
Ligne 6 : Denfert Rochereau - St Jacques - Glacière - Corvisart - Place d'Italie
Ligne 7 : Place d'Italie - Les Gobelins - Censier - Place Monge - Jussieu
Ligne 10 : Jussieu - Gare d'Austerlitz
Ligne 5 : Gare d'Austerlitz - Quai de la Rapée - Bastille
Ligne 1 : Bastille - St Paul - Hôtel de Ville
Ligne 11 : Hôtel de Ville - Rambuteau - Arts et Métiers
Ligne 3 : Arts et Métiers - Temple - République
Ligne 9 : République - Strasbourg St Denis - Bonne Nouvelle - Grands Boulevards - Richelieu Drouot
Ligne 8 : Richelieu Drouot - Opéra
Opéra - Auber - Havre Caumartin - St Lazare en souterrain.
Ligne 14 : St Lazare - Madeleine
Ligne 12 : Madeleine - St Lazare
Ligne 13 : St Lazare - Liège - Place de Clichy
Ligne 2 : Place de Clichy - Rome

On utilise 29 stations différentes en comptant celles de départ et d'arrivée (on passe plusieurs fois par certaines).

Bonsoir,

graphes et optimisation... rigolo
J'adooore le titre "Tous les chemins mènent à Rome...".
Bon, voici un premier jet, mais assez content de moi je poste finalement de suite.
Arf, j'avais lu en diagonale et cherché le plus court chemin mais il devrait ici coïncider avec le plus petit nombre de stations "empruntées" (du moins je l'espère).
Le minimum inaccessible est évidemment 12 (sans compter le départ et l'arrivée, 14 sinon) et je n'ai pas mieux que 21 (ou 23 donc), ce qui par ailleurs s'effectue en 24 "trajets".

Voici mon parcours:
Mouton-Duvernet
L4 :
Denfert-Rochereau

L6 :
Saint-Jacques
Glacière
Corvisart
Place D'Italie

L5 :
Campo Formio
Saint-Marcel
Gare D'Austerlitz

L10:
Jussieu

L7 :
Sully Morland
Pont Marie
Chatelet

L11:
Hotel de Ville

L1:
Chatelet

L14:
Pyramides
Madeleine

L8 :
Concorde

L12:
Madeleine
Saint-Lazare

L13:
Miromesnil

L9 :
Saint-Augustin

pieds
Saint-Lazare

L3 :
Europe
Villiers

L2 :
Rome

Et le même en image :


Voila. Les stations en italique sont celles rencontrées pour la seconde fois (donc exclues du dénombrement).
Toutes les lignes ont été empruntées, quant à savoir s'il existe un chemin "plus court"... je le saurais à la correction.

Merci pour cette belle énigme.

Bonjour à tous,
bonjour Minkus,

Merci pour l'énigme, voici ma proposition :

Ligne 4 : Mouton-Duvernet --> Denfert-Rochereau = +2
Ligne 6 :  --> Gare Montparnasse = +3
Ligne 13 : --> Duroc = +1
Ligne 10 : --> Sèvres-Babylone = +2
Ligne 12 : --> Concorde = +4
Ligne 8 :  --> Madeleine = +1
Ligne 14 : --> Châtelet = +2
Ligne 1 :  --> Hôtel de Ville = +1
Ligne 11 : --> République = +3
Ligne 5 :  --> Gare de l'Est = +2
Ligne 7 :  --> Chaussée d'Antin-Lafayette = +4
Ligne 9 :  --> Havre-Caumartin = +1
Ligne 3 :  --> Villiers = +3
Ligne 2 :  --> Rome = +1

En n'empruntant donc qu'une seule fois chaque ligne, pour un total de 30 stations.

Après plusieurs tentatives et en espérant ne pas m'être planté dans les plans du métro...

Pour passer dans le moins de stations possibles et étant donné que nos stations de départ et d'arrivée sont sur une seule ligne, il faut essayer de passer par un maximum de stations comportant 4 ou 5 lignes.

On a 5 stations satisfaisant ces conditions : Châtelet, République, Nation, Montparnasse-Bienvenüe et St-Lazare.

Je vous propose donc un périple passant 2 fois par ces 5 stations, par 3 stations intermédiaires et nos stations de départ et d'arrivée.

10 stations seront donc visitées !

De Mouton-Duvernet, je prends la ligne 4 jusqu'à Montparnasse-Bienvenüe.
De là, je prends la ligne 13 jusqu'à St-Lazare.
De là, je reviens à Montparnasse-Bienvenüe par la ligne 12.
De là, je prends la ligne 6 jusqu'à Nation.
De là, je prends la ligne 1 jusqu'à Châtelet.
De là, je prends la ligne 14 jusqu'à St-Lazare.
De là, je prends la ligne 3 jusqu'à République.
De là, je prends la ligne 11 jusqu'à Châtelet.
De là, je prends la ligne 7 jusqu'à Jussieu.
De là, je prends la ligne 10 jusqu'à Gare d'Austerlitz.
De là, je prends la ligne 5 jusqu'à Bastille.
De là, je prends la ligne 8 jusqu'à République.
De là, je prends la ligne 9 jusqu'à Nation
De là, je prends enfin la ligne 2 jusqu'à Rome.

Les 14 lignes ont été empruntées exactement une fois.

On visite 10 stations.

Je ne pense pas que ce soit pertinent de passer d'une station à l'autre par les sous-sols... Ca fait visiter deux stations sans prendre de ligne...

Si je n'ai pas oublié de stations à 4 lignes ou plus, je pense avoir le minimum... Je pense...

Salut,
J'ai trouvé une solution à 29 stations (30 avec celle de départ), j'ai pas cherché mieux

Les stations de correspondance sont mises comme première station de la nouvelle ligne (et n'apparaissent pas comme dernière station de la précédente)

ligne 4:
1. Mouton-Duvernet
ligne 6:
2. Denfert
3. St-Jacques
4. Glacière
5. Corvisart
ligne 5:
6. Place d'italie
7. Campo Formio
8. St Marcel
ligne 10:
9. Austerlitz
Ligne 7:
10. Jussieu
11. Sully Morland
12. Pont Marie
Ligne 1:
13. Chatelet
Ligne 11:
14. Hôtel de ville
15. Rambuteau
ligne 3:
16. Arts et métiers
17. Temple
Ligne 9:
18. République
ligne 8:
19. Strasbourg St Denis
20. Bonne nouvelle
21. Grands boulevards
22. Richelieu Drouot
23. Opéra
24. Madeleine
Ligne 12:
25. Concorde
Ligne 14:
26. Madeleine
Ligne 13:
27. St Lazare
28. Liège
Ligne 2:
29. Place de Clichy
30. Rome

Merci Minkus pour cette énigme qui mérite bien ses quatre étoiles.

Je propose le périple suivant:

Ligne 4, de MoutonD à Denfert : 1 station
Ligne 6, de Denfert à Montparnasse (par Raspail et Vavin) : 3 stations
Ligne 13, de Montparnasse à Saint-Lazare (par Duroc,SFXavier,Varenne,Invalides,ChampsElClé,Miromesnil): 7 stations
Ligne 14, de Saint-Lazare à Gare de Lyon (par Madeleine,Pyramides et Chatelet) : 4 stations
Ligne 1, de Gare de Lyon à Bastille: 1 station
Ligne 8, de Bastille à République (par CheminVert,Saint Seb,FillesDuC): 4 stations
Ligne 11, de République à Chatelet (par ArtsetM,Rambut,HdV):4 stations
Ligne 7, de Châtelet à Jussieu (par PontMarie, SullyM):3 stations
Ligne 10, de Jussieu à Austerlitz: 1 station
Ligne 5, d'Austerlitz à Oberkampf (par la Râpée, Bastille,Brégurt,RLenoir): 5 stations
ligne 9, d'Oberkampf à Havre-Caumartin (par République,Strasbourg,BonneNouvelle,Gds Boulevard, Richelieu,Chaussee d'Antin):7 stations
Ligne 6: de HavreCaumartin à Saint Lazare; 1 station
Ligne 12: de Saint Lazare à Pigalle par Trinité,NDLorette,SaintGeorges): 4 stations
Ligne 2: de Pigalle à Rome (par Blanche et Clichy): 3 stations
ce qui fait 48 stations sans compter la station de départ.
  

J'ajoute que j'ai utilisé les 14 plans des lignes fournis par la RATP via Internet. Les correspondances et les noms des stations y sont clairement indiqués. Je me suis interdit d'emprunter une ligne et de faire demi-tour en restant sur la même ligne; il me semble que ce n'est pas permis et j'espère qu'il n'y aura pas de controverse?
A bientôt!

Bonsoir,

Je tente le coup...
Voici la suite des stations visitées :

Le nombre minimum de stations que j'ai du emprunter pour réussir ce périple est

Merci Minkus et A+, KiKo21.

P.S. Tu as bien fait d'aller à la pêche au candidat en trainant sur le forum

Salut. Un peu surpris par le succés énorme de cette énigme

Outre le célèbre "Veni vidi vici", l'histoire n'a pas retenu ce que César disait aux guerriers qui essayaient d'envahir sa cité : "Si tu viens à Rome en char, prépare toi à Rentrer Avec Tes Pieds !" (Non non il n'y a pas de contrepèterie.)

A part kioups, qui a confondu nombre de stations visitées et nombre de stations de changement de ligne, tous les autres ont compris l'énoncé et que l'on prenne en compte le nombre total de stations du parcours ou le nombre de stations "visitées" au moins une fois, le chemin le plus court parmi ceux proposés, est bien celui de Manpower et Kiko21, avec un total de 26 stations en comptant MOUTON et ROME. Le fait qu'ils aient trouvé exactement le même parcours laisse à penser qu'il s'agit bien de LA solution mais personnellement je ne l'affirmerai pas

Bravo donc à tous les deux (avec une image à la clé en plus) et bravo aussi aux autres pour avoir tenté leur chance.

minkus

bravo à manpower et à kiko pour cette belle énigme de minkus

superbe image-solution de kiko

Salut MKS et MKY,

Merci pour vos compliments. Je n'ai joué que de la gomme sur ce coup
C'est mon coté pédagogue, "un bon dessin vaut mieux qu'un long discours"
Bravo et bonne chance à Manpower qui n'a que 89 heures d'avance en moyenne sur moi.
Mais je garde espoir, et comme l'a écrit Jean de la Fontaine, "rien ne sert de courrir, il faut partir à point".

A+, KiKo21.

t'as quel dossard, kiko  ?  

> MKY : Tu ne crois pas si bien dire !!

Nous avons une tortue à la maison : Il s'appelle Charly et ressemble tout à fait au dossard 89.
Je dois être influencé par sa présence...
Et nous avons aussi Gaston en pension, la tortue d'amis partis en vacances.
Promis, je vous mettrai les photos des bolides

A+, KiKo21.

citation :
Nous avons une tortue à la maison : Il s'appelle Charly

On dit pas un tortu dans ces cas là ?

en tout cas, le tort tue

J'aurais dû dire : Nous avons une tortue mâle à la maison...  

Après avoir étudier le singulier et le pluriel (enigmo, énigmi),nous passons à l'étude du genre aujourd'hui

TORTUE :
- au masculin : UN MAUL
- au féminin : UNE COCOTTE

A+, KiKo21.

^{P.S. Ce soir USA Perpignan - Stade Toulousain}

Félicitations aux deux vainqueurs

Cette d'énigme... tient beaucoup de la roulette russe.  

oui, avec 5 balles

Salut Bornéo,

citation :
Cette d'énigme... tient beaucoup de la roulette russe.

Minkus serait gérant de tripot clandestin "no limit" ?
J'avais quand même pris mes précautions...



ce qui donnait



En transformant le trajet à pied de Mouton-Duvernet à Denfert-Rochereau en trajet métro par la ligne 4,
cela donnait 21 stations en utilisant 3 lignes (2,4 et 6).
Alors quand je suis arrivé à 23 stations avec 14 lignes de métro, je me suis dit que je pouvais tenter le coup...

A+, KiKo21.

P.S. Je n'ai pas calculé le temps du parcours !!!!

citation :
A part kioups, qui a confondu nombre de stations visitées et nombre de stations de changement de ligne,

Pour moi, "visiter" une station, c'est emprunter ses couloirs... Dommage, je la sentais bien cette énigme !

Bonjour à tous et compliments aux deux vainqueurs!

Quand l'énigme a été posée, j'ai essayé, à la hâte, de faire faire cela par Maple et je me suis planté.
D'autre part je n'avais pas vu qu'on peut aller à pied de Saint Lazare à Saint Augustin (ce n'est pas l'une des "longues correspondances indiquées en blanc").
Moins perturbé depuis hier, j'ai repris mon programme.
Il semble bien fonctionner et confirmerait que le minimum est bien de 25 trajets élémentaires.
Par contre, il me donne une solution un peu différente, vers la fin, de celle des deux vainqueurs.
Au deuxième passage au Chatelet:
Aller jusqu'à Saint-Lazare par la 14
puis à Saint-Augustin à pied
puis à Havre-Caumartin par la 9
puis à Opéra par la 3
puis à la Madeleine par la 8
puis à Saint Lazare par la 12
puis à la place Clichy par la 13
et enfin à Rome par la 2

Merci encore à Minkus pour cette énigme.

salut rogerd

dommage de ne pas la faire figurer sur le plan, à la "kiko", pour la visualiser

A la Drüker : " kiko, si tu nous regardes..."

MKY, si tu es bien sage !!!

merci pour les adeptes du métro

mikayaou:
je ne me sens pas assez expert pour faire ce travail..
Ce serait bien si kiko voulait bien s'en charger???

Rogerd, si tu es sage

kiko:

J'attends bien sagement!

Salut,

On oserait même demander d'avoir aussi les deux tracés superposés

Puisque tout le monde a été bien sage...

A+, KiKo21.

Merci kiko, c'est très joli!

joliiiiiiiii kiko, belle animation pédagogique

Reste plus à analyser celle où le circuit de marche est le moins long ( examiner les correspondances dans la partie différentielle, à compter de Madeleine... )

Une ptite étude sur le terrain, minkus ?

mikayaou

Minkus faisant une marche autour de la Madeleine...
Ne te serais-tu pas inspiré de Brassens?

avec ses contrepets, je verrai minkus avec Fernande, plutôt qu'avec Madeleine...

Censure