Manœuvres et cabotage

par **piko30** 09 Déc 2011, 21:51

Bonsoir à tous
voila j'ai un petit souci, rien de méchant, mais je dois m'absenter peu être jusqu'à jeudi, départ demain après midi, alors je ne sais pas ou envoyer vos solutions au "Grand Maître" ou bien plancher sur le nouveau problème en attendant que je vous donne les solutions à mon retour.

par **pierre du rail - 61** 09 Déc 2011, 22:47

Bonsoir,
Autre solution, nous prenons une semaine de vacances et les résultats sont reportés au lundi 19 avant que le nouveau problème ne soit présenté.
Et nous = :dodo:

Cordialement.
Pierre

par **Jojo37** 10 Déc 2011, 00:37

Bonsoir à tous.
Ayant un week-end chatgé,si l'on repousse au 19/12 cet exercice,celà ne peut que m'arranger,ne l'ayant pas encore regardé.
Le "maitre" peut dire ce qu'il en pense.
Bon week-end à tous.

par **bogie-wogie** 11 Déc 2011, 22:21

Oh, mais le mètre, il est fort complaisant (ou con plaisant pour les mauvaises langues :prrrt:

) donc reporter au 19 décembre, ça me convient tout à fait. D'autant plus que je viens moi-même d'avoir un samanche particulièrement chargé.

Et puisqu'il faut prendre une décision, c'est donc officiel : résultats du problème en cours et nouveau défi le lundi 19 décembre, dans la soirée... :yin

(cela vous laissera plus de temps pour trouver la bonne réponse :hinhin

)

bw

par **bogie-wogie** 12 Déc 2011, 23:33

Pour vous consoler de ne pas avoir de nouveau problème à vous mettre sous la dent ce soir, je vous propose une petite conférence didactique... Alors accrochez vos ceintures pour un petit tour de voltige à travers les sombres allées du triage de ouagons...

La règle Qs

Cette règle est relativement simple à comprendre tout autant qu'à appliquer, et si son domaine d'application peut paraître assez restreint, elle n'en est pas moins fort utile dans des circonstances où on ne l'attend pas.

Tout d'abord, pourquoi " Qs " ? Le Q vient de ce que cette règle concerne la queue de la rame à trier. Et le s se rapporte à une destination " suivante ", en d'autres termes la première destination à suivre celles déjà présentes dans la rame. Cette destination s ne doit en fait pas déjà se trouver elle-même au sein de la rame pour que la règle reste applicable dans tous les cas.

Cette règle Qs s'énonce ainsi : si en queue d'une rame X on ajoute une nouvelle destination S, alors la nouvelle rame XS se trie en un nombre u de manœuvres égal au nombre t de manœuvres nécessaires pour trier la rame X augmenté de la parité p de ce nombre t, soit u = t+p. Il reste préciser que la parité p = 0 si t est pair et que p = 1 si t est impair.

Rien de tel que quelques exemples simples pour mieux comprendre cette règle. Ainsi partant de la rame CBDA qui se trie en t = 6 manœuvres, la rame augmentée CBDAE (où S=E) se triera elle aussi en 6 coups puisque t est pair : u = t+p = 6+0.

Si par contre on prend une rame telle que CBEDA qui se trie en 7 manœuvres, alors la rame augmentée avec S=F, c'est-à-dire CBEDAF, se triera en 8 coups (7+1, du fait que t est impair et donc que p=1). On peut même aller plus loin et affirmer que dans ce cas il y a au moins deux solutions distinctes possibles pour trier CBEDAF (ou toute rame XS telle que X se trie en un nombre impair de manœuvres). Nous verrons pourquoi plus loin avec une méthode d'obtention de ces deux solutions.

Des exemples, c'est bien joli, mais qui nous garantit que cela marche dans tous les cas ? Le cas pair est le plus facile à examiner. Ce qu'il faut bien voir c'est que dans ce cas la rame triée, une fois les manœuvres terminées, se retrouve toujours sur la voie de départ (voie 0). Et cela reste vrai quel que soit le nombre de manœuvres effectuées tant que ce nombre est pair ! Il suffit donc de laisser le wagon S là où il se trouve au départ et de ne pas le déplacer : comme S est la toute dernière destination ce wagon est déjà à la bonne place dans la rame. On effectue alors le triage des autres wagons (rame X) qui se retrouveront eux aussi nécessairement dans le bon ordre sur la voie 0 de départ une fois triés, juste devant le wagon S resté immobile. Et notre rame XS sera totalement triée sans avoir nécessité une seule manœuvre supplémentaire.

Pour le cas impair c'est moins évident. On peut toutefois illustrer le principe au moyen d'un exemple parmi les plus simples. Considérons donc la rame de deux wagons X=BA. Cette rame se trie en trois coups comme le montre le schéma suivant. C'est d'un niveau élémentaire aussi je n'entrerai donc pas dans les détails, mais on constate (et c'est important) qu'à la fin la rame triée se trouve sur l'autre voie (voie 1) que celle de départ.

Ajoutons à présent un nouveau wagon C en queue de rame pour obtenir XS=BAC. On démontre (mais entrer dans ces détails nous entraîneraient trop loin) que lorsque le dernier wagon de la rame est celui ayant la dernière destination, la meilleure solution est toujours obtenue en un nombre pair de manœuvres. C'est-à-dire que ce dernier wagon est déjà en bonne position, sur la bonne voie, et ne doit pas bouger. Dans le cas de notre courte rame BAC cela signifie qu'on peut totalement ignorer le wagon C et concentrer nos efforts sur BA. Mais ça, on sait déjà le faire en 3 manœuvres comme on l'a vu ci-dessus !

Une première solution consiste donc à trier BA et comme la rame triée se trouvera sur la voie 1 (autre que celle de départ, le nombre de manœuvres étant impair) il faudra une manœuvre supplémentaire (et une seule) pour ramener cette rame (désormais AB) sur la voie 0 de départ et lui rattacher le wagon C en queue. C'est ce que montre le schéma suivant. Il faut donc bien ici 3+1=4 manœuvres pour effectuer le tri complet.

Mais il existe une autre façon de procéder (ou de voir les choses, c'est selon). Au lieu de trier BA normalement puis de ramener la rame triée de la voie 1 à la voie 0 de départ, on peut dès le début des opérations déplacer la rame à trier (ici BA) sur la voie 1 puis effectuer son tri à partir de là. Comme le nombre de manœuvres est impair, la rame triée finira sur " l'autre " voie, c'est-à-dire la voie 0, celle sur laquelle attend le wagon C.
Il nous faut donc une manœuvre supplémentaire pour déplacer la rame BA de la voie 0 vers la voie 1, mais à la fin la rame triée se retrouve directement sur la voie 0 sans manœuvre additionnelle ! Cette deuxième solution est illustrée par le schéma suivant.

En résumé, quelle que soit la méthode utilisée, il nous faudra toujours une manœuvre supplémentaire, soit tout au début du triage, soit tout à la fin (et dans certains cas cette manœuvre supplémentaire peut être effectuée en cours de triage, donnant une ou même plusieurs autres solutions, mais les conditions pour que cela soit possible sont plus complexes et pourront faire l'objet d'un autre article, plus fouillé).

Et enfin ce qu'il faut bien noter c'est que si les exemples utilisés ici sont élémentaires, le raisonnement présenté en est indépendant et cette méthode est valable (et utilisable) pour toute rame X se triant en un nombre impair de manœuvres, quelle que soit sa longueur ou sa complexité.

A titre d'exercice, partant de la rame BEDAC, qui se trie en 7 manœuvres, vous pouvez essayer de trouver les deux solutions pour trier BEDACF en 8 manœuvres.

Et pour conclure, encore une petite remarque : si le tri de la rame X possède plusieurs solutions, le nombre de solutions pour trier la rame XS en sera multiplié d'autant. Ainsi à partir de BDAEC qui se trie en 7 coups par deux solutions distinctes, on obtiendra 4 solutions pour trier BDAECF en 8 coups. Mais ce n'est pas toujours rigoureusement vrai car tout en étant obtenues par des cheminements différents certaines solutions peuvent parfois se révéler être identiques au final.

bw :ugeek:

par **piko30** 19 Déc 2011, 14:20

Bonjour à tous
et bien nous sommes le 19, il faudrait vous dépêcher de me faire parvenir vos solutions :gne:

Je n'ai reçu qu'une seul réponse pour le moment :pleure:

par **pierre du rail - 61** 19 Déc 2011, 22:50

Bonsoir,
C'est vrai, il faut envoyer vos travaux. :gne:

Personnellement, j'ai une petite idée sur celui qui a déjà fait son envoi :siffle:

Cordialement.
Pierre

par **piko30** 20 Déc 2011, 00:08

pierre du rail - 61 a écrit:Bonsoir,
C'est vrai, il faut envoyer vos travaux.
Personnellement, j'ai une petite idée sur celui qui a déjà fait son envoi
Cordialement.
Pierre

Bonsoir
Effectivement, je comprend Pierre que tu puis avoir une idée, mais il y a tellement longtemps que cette solution est arrivée que je l'avais oubliée :oops: