Forum de mathématiques - Bibm@th.net

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Le chef de gare

Hello,

  Voici le plan d'une gare :

Les ronds désignent des quais, les numéros des trains qui sont à quai, et les traits sont les voies.
Votre mission : déplacer les trains pour qu'ils échangent de place : le 1 à la place du 7, le 2 à la place du 6, le 3 à la place du 5, et le 4 inchangé.
A vous de le faire en effectuant le minimum de mouvements possibles.

Fred.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chef de gare

Salut,

j'ai trouvé au total 12 mouvements de train

▼détails

3 pour permuter 1 & 7
6 pour permuter 2, 6 & 4
3 pour permuter 3 & 5

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : Le chef de gare

Salut à tous.

▼Texte caché

voilà , je propose un déplacement angulaire de 720° .

Tout d'abord on remarque que 4 gares sont désservies par 4 voies.
alors  1 arrive à la gare 8 et se range sur une voie libre pendant que 7 prend sa place en  1 ,
puis 1 peut arriver en 7.

la meme chose pour 3 et 5 , à la différence que 4 se range sur la ligne 4-2 ; à son tour 3 vient se ranger sur
la ligne 4-6  pour que 5 vienne prendre la place de 3 . Puis 3 peut donc venir en 5 , et 4 reprend sa place.

il reste ainsi la permutation de 2 et 6 , ou 2 vient se ranger sur la voie 8 - 1  pour que  6 puisse venir prendre sa place en passant par 8.  puis 2 peut donc rejoindre 6 en passant aussi par 8.

                                                                                           à plus

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Le chef de gare

Re-

@Freddy : Mince, je m'étais arrivé à plus de mouvements, il va falloir vérifier.

@jpp : Je ne l'ai pas précisé dans l'énoncé, mais un train ne peut pas s'arrêter sur une voie. Il doit s'arrêter à un quai.

Fred.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chef de gare

Re,

@Fred : je te donne les manip' si tu veux, je ne pense pas m'être trompé.

Il faut le faire dans l'ordre que j'ai indiqué ; on remarque que le dernier transfert est le symétrique du premier, puisque le second transfert libère le quai qu'occupait le train #4.

Dernière modification par freddy (28-10-2011 12:34:15)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Le chef de gare

Re,

  Oui, mais je veux que le 4 reste à la même place....
Là, tu le fais aller tout en bas....

Fred.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chef de gare

Re,

je viens de relire le sujet, et je vois qu'en effet, il faut laisser le 4 à la même place.

Donc au temps pour moi, I try again !

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : Le chef de gare

re.

▼Texte caché

les 4 voies intérieures font une astroide. les voies extérieures seront quartier supérieur, quartier inférieur , premier et dernier quartier.

alors 4 descend sur l'astroide en direction de 6 et en meme temps 2 et 6 font la meme  chose
      2 -> 8 ->6 et 6 -> 4->2 toujours sur l'astroide.

ils roulent donc dans le sens horaire sur cette astroide.

au meme moment  3 et 5 tournent sur le quartier supérieur dans le sens direct  et 1 et 7 dans le quartier inférieur dans le sens direct  si bien que 3 et 5 d'une part et 1 et 7 d'autre part ont pu permuter en précisant que pendant que 3 et  5 se trouvent sur le petit cercle du quartier supérieur , 4  est passé par 6 et 5 et est revenu à son point de depart.  de meme , en synchronisant 2 et 6 ont pu permuter en passant respectivement par 8 et 4 quand il n'y avait pas de trains.

les trains sont donc obligés de se mouvoir en meme temps et de synchroniser les manoeuvres.

  n.b.  Fred , je venais juste de m'apercevoir qu'il y avait des voies extérieures , pourtant j'avais mes lunettes.
  ça craint quand meme.

Dernière modification par jpp (28-10-2011 13:29:35)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le chef de gare

Salut à tous,

les trains sont donc obligés de se mouvoir en meme temps et de synchroniser les manoeuvres.

Fred, je ne voudrais pas faire de peine à jpp, mais est-ce bien conforme à l'esprit de l'énoncé ? J'avais cru comprendre que les mouvements se succédaient ?

je veux que le 4 reste à la même place....

Fred, veux tu dire que le 4 doit être à la même place à la fin des opérations, ou bien veux-tu dire qu'on ne doit à aucun moment toucher au 4 ?

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : Le chef de gare

re.

tu dois avoir raison nérosson il doit falloir les bouger un par un" façon puzzle " ou plutot façon pousse pousse.

par contre on peut quand meme bouger le 4  et le remettre à sa place.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Le chef de gare

Re-

  Vous avez raison, les trains ne peuvent bouger que les uns après les autres, le 4 peut bouger mais doit revenir à sa place
à la fin... et Nerosson ne devrait pas autant douter de lui-même!

Fred.

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le chef de gare

Salut à tous,

Nérosson, il avait bougrement raison de douter de lui-même ! ! !

J'ai trouvé un os dans ma solution et je viens d' effacer mon poste précédent. Putain de quatre ! ! !

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : Le chef de gare

re.

je l'ai en 17 coups. et je peux détailler.
                                                               à plus.

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : Le chef de gare

Bonsoir,

▼15 mouvements

chaque train va au quai vide...
2,4,3,5,3,6,2,1,5,4,6,4,5,7,1

amatheur

Membre

Inscription : 02-10-2011

Messages : 299

Re : Le chef de gare

bonjour.
solution en 14 mouvements:

▼solution

24627146534654.

désolé, je n arrive pas à utiliser la balise correctement. quelqu'un pourrait me corriger s'il vous plait.

[EdIt] by yoshi
Pas d'espaces dans les balises quelles qu'elles soient !

Dernière modification par yoshi (29-10-2011 15:08:44)

amatheur

Membre

Inscription : 02-10-2011

Messages : 299

Re : Le chef de gare

salut
une autre en 13 mouvements:

▼solution

6542652436571

Dernière modification par yoshi (29-10-2011 15:09:49)

amatheur

Membre

Inscription : 02-10-2011

Messages : 299

Re : Le chef de gare

re
qu'il soit maudit ce chiffre 13; j'ai beau faire varier l'ouverture, je n'arrive pas à faire mieux!

▼@yoshi

merci pour la correction.

j'ai pigé le truc!

Dernière modification par amatheur (29-10-2011 15:27:56)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le chef de gare

Sazlut à tous,

Puisque je ne suis bon à rien, je vais essayer de saboter le travail des autres en espérant (sans trop y croire) avoir davantage de succès.

@amatheur,

J'ai vérifié ta solution en 14 mouvements. Si en partant du haut et dans le sens des aiguilles d'une montre, j'appelle les quais A B C D E F G H, ta solution me donne : A4, B3, C2, D1, E7, F6, G5, H vide.Ce qui n'a pas l'air de coller avec l'énoncé.

En dépit du soin que j'y ai mis, je peux me tromper. Si c'est le cas, n'hésite pas à me mettre le nez dans mon caca : au point où j'en suis...

Ci-dessous, ma vérification

Dernière modification par nerosson (29-10-2011 17:48:31)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le chef de gare

Salut à tous,

@amatheur,

Tu vas croire que je t'ai dans le nez : pas du tout, mais en vérifiant ta solution à 13, je trouve :
A4, B3, C2, D1, E7, F vide, G5, H6.

Ci-dessous ma vérification (pas très lisible, je sais):

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le chef de gare

Salut à tous, 

Ma technique de vérification ne devrait pas être mauvaise, puisque j'ai vérifié la solution en 15 mouvements de totomm et que je l'ai trouvée juste :

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : Le chef de gare

Bonsoir,

Tout à fait d'accord avec les vérifications de nerosson : les solutions à 14 et 13 mouvements d'amatheur ne correspondent pas à la demande de l'énoncé.
Pour optimiser et valider j'ai utilisé un algorithme de graphe transcrit en Python.

Cordialement

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le chef de gare

Salut à tous,

Hourrah ! ! ! J'ai trouvé ma vocation : casseur ! Dorénavant, je participerai à toutes les manifestations, armé d'un manche de pioche.

Pour optimiser et valider j'ai utilisé un algorithme de graphe transcrit en Python.

Pas étonnant que moi, je me sois planté : avec mon papier et mon crayon !

Dernière modification par nerosson (30-10-2011 15:37:35)

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : Le chef de gare

re,

Pour éviter toute confusion, mieux vaut garder les notations de l'énoncé :
Au début les trains de 1 à 7 sont sur les quais respectifs de 1 à 7, le quai 0 est le quai vide.

Voici les mouvements numérotés de 0 à 15 sortis par mon programme Python :
0 [0, 1, 2, 3, 4, 5, 6, 7] le quai vide est en 0
1 [2, 1, 0, 3, 4, 5, 6, 7] le quai vide est en 2  ; le train 2  a rejoint le quai 0
2 [2, 1, 4, 3, 0, 5, 6, 7] le quai vide est en 4  ; le train 4  a rejoint le quai 2
3 [2, 1, 4, 0, 3, 5, 6, 7] le quai vide est en 3  ; le train 3  a rejoint le quai 4
4 [2, 1, 4, 5, 3, 0, 6, 7] le quai vide est en 5  ; le train 5  a rejoint le quai 3
5 [2, 1, 4, 5, 0, 3, 6, 7] le quai vide est en 4  ; le train 3  a rejoint le quai 5
6 [2, 1, 4, 5, 6, 3, 0, 7] le quai vide est en 6  ; le train 6  a rejoint le quai 4
7 [0, 1, 4, 5, 6, 3, 2, 7] le quai vide est en 0  ; le train 2  a rejoint le quai 6
8 [1, 0, 4, 5, 6, 3, 2, 7] le quai vide est en 1  ; le train 1  a rejoint le quai 0
9 [1, 5, 4, 0, 6, 3, 2, 7] le quai vide est en 3  ; le train 5  a rejoint le quai 1
10 [1, 5, 0, 4, 6, 3, 2, 7] le quai vide est en 2  ; le train 4  a rejoint le quai 3
11 [1, 5, 6, 4, 0, 3, 2, 7] le quai vide est en 4  ; le train 6  a rejoint le quai 2
12 [1, 5, 6, 0, 4, 3, 2, 7] le quai vide est en 3  ; le train 4  a rejoint le quai 4
13 [1, 0, 6, 5, 4, 3, 2, 7] le quai vide est en 1  ; le train 5  a rejoint le quai 3
14 [1, 7, 6, 5, 4, 3, 2, 0] le quai vide est en 7  ; le train 7  a rejoint le quai 1
15 [0, 7, 6, 5, 4, 3, 2, 1] le quai vide est en 0  ; le train 1  a rejoint le quai 7

Pour rechercher une solution par programme, c'est plus facile en cherchant le parcours du "quai 0". cela revient à chercher un parcours des arêtes du graphe dans lequel les arêtes sont parcourues une fois, et 2 au maximum pour certaines...

Cordialement

amatheur

Membre

Inscription : 02-10-2011

Messages : 299

Re : Le chef de gare

salut à tOus
@NEROsson le casseur!
ce que j'ai compris de l’énoncé, c'est que seul l'endroit ou on devrait placer les trains 123 et 4 est stipulé, pour le reste des trains, rien ne nous oblige à les placer dans l'ordre décrit par totomm, quand on dit 1 à la place du 7, ça ne nous donne aucune information sur l’emplacement du 7. ou peut être c'est que j'ai mal interprété, j’attend confirmation de FRED

Dernière modification par amatheur (29-10-2011 18:55:39)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Le chef de gare

Re-

@amatheur : je n'ai peut-être pas été très clair, mais dans mon premier post, je parle d'échanger les positions. Donc je veux que le 1 soit à la place du 7 et le 7 à la place du 1.

@tous : je me doutais bien en posant cette énigme que les certains allaient se ruer sur Python.
Allez, il y a un défi associé pour les programmeurs. Trouvez toutes les solutions en 15 coups (qui est l'optimum, je crois).
Vous allez voir, vous allez être surpris!

Fred.