Journal Problème de train

Posté par (page perso) .
Tags : aucun
0
28
août
2003
Bon, en ce moment c'est la mode, et il y a un problème récréatif qui n'est pas très connu, et qui est assez délicat.

Il s'agit de déplacer des wagons à l'aide d'une locomotive. La configuration initiale est la suivante :

http://morvan.nerim.net/pro/pb_train.png(...)

Le but est d'échanger les places des deux wagons (A et B) puis de ramener la locomotive (L) à sa position initiale.

La loco est la seule à pouvoir se déplacer de façon autonome.

Les wagons s'accrochent et se décrochent à volonté (pour peut qu'ils soient en contact, entre eux ou avec la loco).

Les wagons et la loco ne peuvent quitter les rails. Les seuls rails disponibles sont ceux qui figurent sur le dessin.

Il y a bien une solution.

Le retour à la position initiale de la loco est une difficulté

Il n'y a pas d'astuce tordue.

La solution nécessite pas mal de déplacements (mais pas 80).
  • # Re: Problème de train

    Posté par . Évalué à 1.

    bon bin j'arrive pas a charger l'image. mais j'ai une question: ca m'a l'air d'etre un probleme du meme type que la tour d'hanoi nan ???
  • # Re: Problème de train

    Posté par . Évalué à 1.

    Euh ... On a le droit d'acrocher les wagons à n'importe quel bout de la loco ? Et celle-ci peut tirer OU pousser les wagons ? Et elle peut faire une marche arrière quand elle veut ?

    Dans ce cas, on a :
    L va pousser A en v3
    L va se connecter à B en restant "au-dessus" de lui
    L tire B à la position qu'occupait A
    L fait le tour (passe par la voie tout en bas) pour remonter à v3 s'accrocher à A
    L tire A pour l'amener à la position initiale de B
    L, qui tirait A, se retrouve en bonne position pour revenir à sa position initiale

    6 déplacements (c'est ridicule comme nombre de déplacement)

    Alors, il y a 2 choses :
    1/ Soit j'ai suffisament bouffé d'algos pour être capable de trouver la solution triviale (je ne voit vraiment _pas_ la difficulté de la chose)
    2/ Soit il manque des infos qui invalident la solution du dessus

    J'aurais tendance à penser à la solution 2/ ;) Des précisions ?

    PS : Accessoirement, c'est quasiment un swap de 2 variables a et b ;)
    • [^] # Re: Problème de train

      Posté par . Évalué à 2.

      L tire B à la position qu'occupait A
      L fait le tour (passe par la voie tout en bas) pour remonter à v3 s'accrocher à A


      Ta loc va défoncer la butée en fin de v1: longueur 5m. Longueur de la loc: 10m :-)
    • [^] # Re: Problème de train

      Posté par (page perso) . Évalué à 1.

      Dans le premier déplacement de ta solution, comment L pousse A en v3? L'aiguillage de v1 n'est pas assez long (5m) pour permettre à L (10m) d'y aller pour passer de VL à VA... Où alors on peut passer d'une voie à l'autre sans passer par la voie d'aiguillage? Le pbm n'est pas assez clairement exposé je pense...
      • [^] # Re: Problème de train

        Posté par . Évalué à 1.

        Il manque plusieurs éléments dans l'énoncé :

        Quelle est la règle précise de passage des aiguillages ?
        Quelle est la règle d'acrochage des wagons (sont-ils obligés d'être en ligne, ou peut-il y avoir un angle entre eux -du moment qu'ils se touchent en un point-) ?
  • # Problème de train

    Posté par . Évalué à 1.

    Je suis idiot ou c'est la solution ?

    L->v2
    L->B : L+B->v3
    L->A: L+A->v1
    L->v3 (sans s'atteler à B)
    L->v2
    L->A : L+A->v2
    L+A -> position initiale de B
    L->v2
    L->v1
    L->B : L+B -> position initiale de A
    L->v1
    L->position initiale de L
  • # Re: Problème de train

    Posté par (page perso) . Évalué à 1.

    Bon sang ! Si vous voulez résoudres des problèmes mathématiques faites des études de maths ou d'informatique. Ou alors achetez-vous un bouquin de maths et, comme Fermat, annotez des trucs dans la page (et quand vous savez pas écrivez que vous avez fait la démonstration mais qu'elle tient pas dans la marge). :)
  • # Re: Problème de train

    Posté par . Évalué à 0.

    Bonjour,

    je crois que j'ai une solution :
    La loco L arrive sur V2.
    Un aiguilleur positionne les rails pour pour que la loco (en marche arriere) arrive sur rails (longueur ???) de B
    Un autre aiguilleur positionne l'aiguillage pour que le Wagon B + loco arrivent sur V2 et la loco pousse le Wagon tout au bout de v2 (Totu juste, marche avant, faut un sacré conducteur de train)

    Une fois cela, la loco L refait marche arriere, l'aiguilleur change l'aiguillage, la loco arrive au contact de A
    La loco prend A et fait marche arriere pour arriver sur le rail v3 (attention a l'aiguillage : la loco L va d'abord sur les rails ou se trouvait B, puis change de direction (donc d'aiguillage) pour pousser A tout au fond, comme ça L sort la premiere du rail v3) sans tamponner la fin de rail(v3 = 30 metre, L+A=15 metres, le conducteur a de la marge, a moins d'etre bourré)
    Une fois cela fait, le cheminot revient la ou se trouvait B (v2), avec le bon aiguillage. L s'accroche A B, refait marche arriere pour aller en direction de v3, va sur v3 (L entre en premier sur V3) avec B d'accroché. A, L et B sont donc sur v3 (assez de place, v3 = 30 metres)

    Une fois B entierement sur v3, on change l'aiguillage pour aller de v3 vers là ou se trouvait A et L positionne B la ou etait A
    Ensuite L decroche B, change de direction et revient accrocher A.
    On change l'aiguillage et L+A vont vers les rails ou se trouvait B (L passe en premier)
    L decroche A la ou se trouvait B puis continue sa route sur v2.
    On change l'aiguillage pour aller de v2 vers la ou se trouvait L et c'est gagné !

    Sam, qui revait d'etre responsable cheminot/logistique/transport à la cokerie de Drocourt (qui n'existe plus) et dont le systeme ferroviaire etait nettement plus compliqué que cet exercice.
    • [^] # Re: Problème de train

      Posté par (page perso) . Évalué à 2.

      Un aiguilleur positionne les rails pour pour que la loco (en marche arriere) arrive sur rails (longueur ???) de B

      Ok, donc, sur la voie de B on a : la loco puis B (vers le haut)

      Un autre aiguilleur positionne l'aiguillage pour que le Wagon B + loco arrivent sur V2

      Donc sur V2 on a B puis la loco (ils sont descendu en marche arrière)

      la loco pousse le Wagon tout au bout de v2

      ???
      B traverse la loco ?

      Non, la loco ne peut pas traverser le wagon, ni l'inverse !
      Mauvaise solution !

      Sam, qui revait d'etre responsable cheminot/logistique/transport à la cokerie de Drocourt

      Heureusement qu'ils ne t'ont pas pris c'aurai été un massacre ! ;o)
  • # Re: Problème de train

    Posté par . Évalué à 1.

    L pousse B sur la voie de A
    L continue à pousser B qui pousse A vers V1
    On laisse A dans V1
    on tire un peu B et on laisse B dans la voie initiale de A.
    L fait le tour pour tirer A vers V2
    L et A rentre dans V2
    Puis L pousse A vers V3 (dans l'ancienne voie de B)
    On laisse A dans la voie initiale de B,
    L retourne dans sa voie initiale.

    Et voila, même pas besoin de V3!
    • [^] # Re: Problème de train

      Posté par . Évalué à 1.

      Je pense que tu n'as pas le droit de passer de B vers A sans passer par v3 avant.
    • [^] # Re: Problème de train

      Posté par (page perso) . Évalué à 1.

      L pousse B sur la voie de A

      Pas possible !

      C'est un aiguillage, pas un virage.

      Si L va directement avec B sur la voie de A on obtient :
      A puis L puis B.

      Donc, ce n'est pas bon.
      • [^] # Re: Problème de train

        Posté par . Évalué à 2.

        Est-ce qu'un wagon lache avec une vitesse non nulle continue a rouler par inertie ?
        • [^] # Re: Problème de train

          Posté par (page perso) . Évalué à 1.

          ;o)

          En fait ça n'a pas d'importance (si la loco peut le lancer elle peut aussi le déposer en douceur).

          Par contre il s'arrête en buté ... et ne repart pas en sens inverse ! ;o)
          • [^] # Re: Problème de train

            Posté par . Évalué à 1.

            Alors c'est bon :

            L va en v2
            L va accrocher B
            L tire B en v2
            L pousse B en v1
            L lache B
            L va accrocher A
            L pousse A et accroche B a A
            L tire A et B et lache B a la place initiale de A
            L continue a tirer A en v3
            L pousse A en v2
            L tire A puis le lache avec de la vitesse
            L revient a sa place initiale
            A s'arrete doucement a la place initiale de B

            C'est "tricky" mais tu m'as dit qu'on a le droit
            • [^] # Re: Problème de train

              Posté par . Évalué à 1.

              Sur le même principe :

              L va en v2
              L va accrocher B
              L tire B en v2
              L pousse B en v1
              L lache B
              L va accrocher A
              (Variante à partir d'ici)
              L tire A jusqu'au fond de v2
              L repart jusqu'à la place initiale de A, et continue jusqu'à l'embranchement avec v1
              L acroche B, et revient le déposer à la place de A
              L revient à v2
              L tire A, puis le lache et part vers la position initiale de B (De façon que A s'arrête après l'aiguillage)
              L revient sur v2 at accroche A
              L va au fond de v2 en tirant A
              L va ensuite vers la position initale de B en poussant A
              L reprend sa position initiale

              Ca évite de calculer la force pour que le wagon s'arrête juste au bon endroit ;)
              • [^] # Re: Problème de train

                Posté par . Évalué à 1.

                Dans ma solution, si le wagon ne s'est pas arrete a la bonne place, la loco va le mettre convenablement et revient :)
                J'aimerais quand meme savoir s'il y a une solution sans ce "truc".
              • [^] # Re: Problème de train

                Posté par (page perso) . Évalué à 1.

                Idem que pour l'autre solution ce n'est pas une approche satisfaisante

                (mais c'est une ruse amusante)
            • [^] # Re: Problème de train

              Posté par (page perso) . Évalué à 1.

              L tire A puis le lache avec de la vitesse
              L revient a sa place initiale

              ???

              Par ou passe L ?

              Non, il n'est matériellement pas possible de changer l'aiguillage entre le passage de L et celui de A !!! (Le passage d'un aiguillage demande une certaine énergie)

              Bien essayé, mais il y a une solution sans cette manoeuvre qui ne peut entraîner qu'un déraillement du train !!!

              (En fait tu as passé un premier cap : arriver à échanger A et B en ayant la loco du mauvais coté ;o))
  • # Re: Problème de train

    Posté par . Évalué à 3.

    J'AI !!!

    L va en v2
    L va accrocher B
    L tire B en v2
    L pousse B en v1
    L lache B
    L va accrocher A
    L pousse A et accroche B a A
    L tire A et B et lache B a la place initiale de A
    L continue a tirer A en v3
    L pousse A a la place initiale de B
    L detache A et revient en v3
    L accroche B et le tire en v3
    L pousse B et accroche A
    L tire A et B en v3
    L pousse A et B et lache A en v1
    L lache B a la place initiale de A
    L va chercher A en v1
    L pousse A a la place initiale de B
    L lache tout et rentre a sa place initiale

    tain j'ai perdu mon après-midi là-dessus...
    • [^] # Re: Problème de train

      Posté par (page perso) . Évalué à 2.

      Bravo !!!

      tain j'ai perdu mon après-midi là-dessus...

      Oui, c'est assez acrocheur comme problème.

      J'ai connu un type qui y avait passé sa soirée (sans succès), et qui m'a dit le soir : je trouverais... c'était il y a 9 ans... je ne l'ai jamais revu.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.