omb
Menu principal
Sujets d'articles
OMB 2007 Finale MINI Question 2 - Solution de Hugo Templier Informations | BxMO 2017 | SBPM  
OMB 2007 Finale MINI Question 2 - Solution de Hugo Templier
1139 vues  | Retourner à la liste des questions

Question :

Dans un centre ferroviaire, les installations permettent de détacher deux ou plusieurs des derniers wagons du train puis de les rattacher aux premiers wagons (ou à la locomotive, si aucun wagon n'a été laissé) après avoir inversé l'ordre des wagons détachés. Par exemple, le train représenté ci-dessous où on détache les quatre derniers wagons


devient après une telle manoeuvre


Trier les wagons d'un train consiste à replacer ces wagons dans un ordre bien déterminé après un certain nombre de manoeuvres.

(a) Est-il possible de trier les wagons du train figuré ci-dessous pour obtenir l'ordre « a-b-c-d » ?

Si oui, quel est le nombre minimum de manoeuvres nécessaires ?

(b) Est-il toujours possible de trier tous les wagons d'un train ? Expliquer votre réponse.

(c) Est-il toujours possible de trier un train de trois wagons en au plus une manoeuvre ? en au plus deux manoeuvres ? en au plus trois manoeuvres ?



Solution de Hugo Templier :


(a) Oui en quatre manoeuvres :

1 : c b d a
2 : a d b c
3 : a d c b
4 : a b c d


(b) Oui car on peut toujours déplacer un wagon au bout du train pour ensuite le placer à n'importe quelle position. En appliquant cette méthode et en commençant par placer le 1er wagon de l'ordre, puis le 2e et ainsi de suite, on peut trier n'importe quel train.

(c) Avec 1 manoeuvre : non car si le 1er wagon de l'ordre est au milieu, il faudrait 2 manoeuvres pour le placer à l'avant.

Exemple : c a b
1ère manoeuvre : c b a
2e manoeuvre : a b c

Avec 2 manoeuvres : non car si le 1er wagon de l'ordre est au milieu et le 2e wagon de l'ordre en 1er lieu, il faudrait 3 manoeuvres pour le placer.

Exemple : b a c
1ère manoeuvre : b c a
2e manoeuvre : a c b
3e manoeuvre : a b c

Exemple : b a c
1ère manoeuvre : c a b
2e manoeuvre : c b a
3e manoeuvre : a b c

Avec 3 manoeuvres : oui car quel que soit l'ordre des wagons, avec 3 manoeuvres et 3 wagons, il y a toujours moyen d'appliquer la méthode décrite en (b).



Revenir à la question


 
Les commentaires appartiennent à leurs auteurs. Nous ne sommes pas responsables de leur contenu.
Membres
Prénom :

Nom :

Mot de passe : 

Conserver la connexion

Récupérer mot de passe
Recherche
Le site officiel de l'Olympiade Mathématique Belge
Contact webmasters :