Une première remarque : pour une rame de longueur donnée, par exemple 5 wagons, le nombre de rames différentes possible n'est pas infini. Et le nombre de "problèmes" intéressants, c'est-à-dire qui ne soient pas évidents à résoudre, est encore plus restreint. Mais il y en a tout de même pas mal. Alors comment faire la sélection ?
En première approche, avec n wagons (ou n lettres) on peut constituer nn rames différentes. Ainsi, pour n= 2 on aura : 22=4 rames de 2 wagons. Ce sont : AA, AB, BA et BB. On voit tout de suite que les rames AA et BB ne présentent strictement aucun intérêt. D'une manière générale les répétitions de lettres en succession sont à bannir. Ainsi la rame "BAAACC" est, du point de vue de notre triage, équivalente à la rame "BAC". Si on ne retient que les rames sans lettres "bégayées" (parce que les répétitions sont admissibles lorsqu'elles sont séparées par une lettre différente, comme dans "BACA" où le C sépare les deux A) le nombre de rames possibles se détermine au moyen d'une magnifique formule itérative dont je vous fais grâce ici. Sachez simplement qu'elle donne les résultats suivants :
- rames à 1 wagon : 1
- rames à 2 wagons : 2
- rames à 3 wagons : 8
- rames à 4 wagons : 44
- rames à 5 wagons : 308
- rames à 6 wagons : 2612
- rames à 7 wagons : 25988
etc.
Si vous voulez connaître le etc., consultez "The Encyclopedia of Integer Sequences" de Sloane et Plouffe, chez Academic Press (1995), ISBN 0-12-558630-2, suite M1866. (Petite parenthèse en passant : le nom de "Plouffe", ça ne s'invente pas et malgré les apparences ce n'est pas un poisson d'avril avant l'heure !)
Ensuite, parmi toutes les rames acceptables (par exemple les 308 rames de 5 wagons) je choisis celles qui m'ont donné un peu plus de fil à retordre (eh oui, j'ai résolu toutes les rames jusqu'à 5 wagons et à peu près un quart de celles à 6 wagons
). Le niveau de "difficulté" est donc tout à fait subjectif et très personnel. Il n'y a pas vraiment de critère pour classer les solutions et le mieux qu'on puisse faire est d'écarter dans un premier temps les problèmes les plus évidents, des rames telles que "ABCDE" par exemple (0 manoeuvre nécessaire), ou "ABDCE" qui se résoud en 3 manoeuvres. De même, à l'autre bout de l'échelle, une rame telle que "EDCBA" nécessite 9 manoeuvres (le maximum pour une rame de 5 wagons) mais aucune réflexion, aucune astuce : sans intérêt.Pour les rames de 5 wagons ce sont en fait les problèmes se résolvant en 6 manoeuvres qui offrent le plus d'intérêt (et de difficulté). Pour les rames de 6 wagons, comme nous le verrons, ce sont les problèmes dont la solution requiert au moins 7 ou 8 manoeuvres. Ceux à 9 ou 10 manoeuvres sont en général plus laborieux à résoudre mais sans présenter ce petit côté "astuce à trouver". Et celui à 11 manoeuvres, "FEDCBA", la seule solution consiste à déplacer les wagons un par un d'une voie à l'autre, ce qui n'est guère fascinant...
Quant aux rames de 7 wagons, je n'ai fait qu'effleurer la question pour l'instant. Nous aurons sans doute l'occasion d'explorer ce domaine ensemble.
Vous voyez donc ce qui vous attend (mais il aura bien des occasions de faire des digressions avec d'autres types de manoeuvres, du moins je l'espère et j'ai quelques idées !) En attendant, bon courage.
bw
Pierre, effectivement bien réveillé... 
