omb
Menu principal
Sujets d'articles
OMB 2004 Finale MAXI Question 4 - Solution de Philippe Schram Informations | BxMO 2017 | SBPM  
OMB 2004 Finale MAXI Question 4 - Solution de Philippe Schram
1893 vues  | Retourner à la liste des questions

Question :

Une liste initiale contient tous les entiers de 1 à 2004 dans un ordre quelconque.

L'opération suivante lui sera appliquée de manière répétée :

Si la première valeur de la liste est le nombre , les premières valeurs sont récrites dans l'ordre inverse de celui où elles étaient (les autres valeurs sont inchangées). Notons que si , la liste n'est pas modifiée.


(a) Existe-t-il une liste initiale telle qu'après lui avoir appliqué l'opération quatre fois successivement, le nombre 1 apparaisse en première position (sans que 1 soit apparu plus tôt en première position) ?

(b) Existe-t-il une liste initiale telle qu'après lui avoir appliqué l'opération dix-sept fois successivement, le nombre 1 apparaisse en première position (sans que 1 soit apparu plus tôt en première position) ?

(c) Existe-t-il, pour tout naturel tel que , une liste initiale telle qu'après lui avoir appliqué l'opération fois successivement, le nombre 1 apparaisse en première position (sans que 1 soit apparu plus tôt en première position) ?

(d) Pour toute liste initiale, existe-t-il nécessairement un naturel tel qu'après avoir appliqué l'opération à la liste fois successivement, le nombre 1 apparaisse en première position ?



Solution de Philippe Schram :


Résolvons uniquement les points c) et d), les points a) et b) n'étant qu'une application numérique.


c) Construisons pour cela une opération inverse. Cette opération dit que si un se trouve en -ième place, alors on peut inverser tous les nombres de la 1ère jusqu'à la -ième place.

(Notons que pour chaque opération, il n'y a qu'une seule opération inverse tandis que pour une opération inverse donné, il y a plusieurs opérations dont l'opération est l'inverse)

Nous allons nous donner la suite 1,2,...,2004 où les nombres sont dans l'ordre.

Tout d'abord, nous appliquons l'opération inverse sur le 2e nombre, puis sur le 3e, etc jusqu'au -ième.

Comme l'opération inverse échange entre autre le premier et le dernier terme du « lieu d'opération », le chiffre 1 ne va plus apparaître en premier lieu.

Si maintenant, à la suite qu'on vient de construire, on applique fois l'opération, on va retourner à la suite 1,2,...,2004 sans que le 1 apparaisse en premier lieu entre-temps.

Donc, pour chaque , il existe une telle suite initiale.


d) Tout d'abord, on constate le suivant : il n'y a « que » 2004!, donc un nombre fini de possibilités pour arranger la suite. Comme ce nombre est défini, l'opération va donc, à un moment donné, décrire une boucle. En effet, si une fois on arrive à une suite qu'on a déjà toruvé précédemment, il faut nécessairement y avoir une boucle.

Soit l'ensemble de tous les nombres qui vont arriver en premier lieu après une certain nombre d'opérations.

Si le plus grand nombre de arrive en premier lieu, il sera renvoyé sur une place où, sans vouloir être mélodramatique, il ne pourra jamais être « libéré » par un des autres nombres, vu qu'ils lui sont inférieur. On réitère pour le 2e nombre, pour le 3e, etc jusqu'au nombre le plus petit de . Or, si ce nombre n'est PAS 1, il y aura un nombre plus petit que le minimum qui va figurer en premier lieu.

Par suite, la construction de serait fausse et on retomberait à une descente infinie, ce qui n'est pas possible, vu le fait que K ne peut compter que 2004 nombres au maximum. Par suite, à partir d'un moment donné, le nombre 1 va figurer éternellement en premier lieu.



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 :