Une longue remise en ordre

Le problème
STRATÉGIE à choisir et ANIMATION
LE PLUS LONG RECLASSEMENT et ANIMATION
ANALYSE et résultats



"Nul ne peut être un mathématicien accompli
s'l n'a pas l'âme d'un poète
."

KARL WEIERSTRASS, LETTRE à SOPHIA KOVALEVSKAYA, 1883.




Le problème Sur l'idée du G2940 de Diophante.fr

Zig a sur une étagère de sa bibliothèque une collection de n ouvrages mathématiques qu'il a étiquetés et rangés de 1 à n.
En son absence, Puce mélange l'ordre des ouvrages.
A son retour Zig demande à Puce de remettre les volumes dans le bon ordre, c'est à dire de gauche à droite : 1,2,..n , et lui impose le processus suivant : si l'ouvrage étiqueté n° k est à droite de la position n° k, alors cet ouvrage est placé en position n°k.
Par exemple, si l'étagère contient dans cet ordre les ouvrages 4,1,3,2, Puce prend soit l'ouvrage n°1 qu'il place en première position et l'ordre des ouvrages devient 1,4,3,2 soit l'ouvrage n°2 qu'il place en deuxième position et l'ordre des ouvrages devient 4,2,1,3.

Q1
Démontrer que Puce est certain de remettre la totalité des ouvrages dans le bon ordre en un nombre fini d'étapes quel que soit le choix de l'ouvrage à reclasser à chacune de ces étapes.

Q2 Déterminer le plus grand nombre possible d'étapes que le processus peut demander quand à chaque étape on prend l'ouvrage qui se trouve le plus à droite des ouvrages à reclasser. Application numérique n = 20. Temps de reclassement d'un ouvrage: 3 secondes.
Déterminer le temps total maximum de la remise en ordre.

ANIMATION avec la procédure de la question Q1 : une certaine liberté dans le choix de l'ouvrage à prendre.

Pour
remettre les volumes dans le bon ordre, c'est à dire de gauche à droite : 1,2,..n , on utilise le processus suivant :
si l'ouvrage étiqueté n° k est à droite de la position n° k, alors cet ouvrage peut être placé en position n°k.

Dans cette partie, le choix du livre est libre dès lors que cette contrainte est respectée.

Dans l'animation

- Choisir d'abord le nombre de livres à ranger avec le bouton fléché.
- Choisir le mode d'exécution : MANUEL, AUTOmatique ou ULTRA Rapide.
- Choisir d'entrer éventuellement les numéros des livres en cochant le bouton adéquat.
  Si ce bouton n'est pas coché les livres, gardent les numéros affichés. Ceux-ci ont été tirés aléatoirement.
- On peut redemander le MÉLANGE des livres : bouton MÉLANGE, chaque ouvrage occupera une autre place tout en gardant sa couleur.
- Chaque clic sur le bouton COULEURS, fait basculer entre des livres colorés au hasard ou bien des livres ayant tous la même couleur.

En mode MANUEL,
- il est possible de choisir le livre à déplacer, ce livre respectant la condition ci-dessus, en le cliquant.
  S'il ne respecte pas la condition imposée, il n'est pas cliquable et il ne se passe rien.
- En cliquant le BOUTON FLÉCHÉ, un livre est choisi au hasard.
  Ce livre bien entendu est à droite de la place correspondant à son numéro.

En mode AUTO,
- le rangement des livres se fait de façon automatique pas à pas, chaque livre étant choisi au hasard en respectant la contrainte ci-dessus.
  Il suffit d'observer...

En mode ULTRA rapide,
- les étapes sont calculées, le rangement est simulé mais on ne le voit pas.
  Ceci permet d'obtenir le calcul du nombre d'étapes lorsque le nombre d'étapes devient très grand,
  par exemple avec une liste de 20 ouvrages dans un certain ordre.

- Enfin dans tous les cas, on peut moduler la vitesse d'exécution.

ANIMATION sur la question Q2 : TROUVER le plus long RECLASSEMENT.


Dans cette partie, la contrainte est de
prendre l'ouvrage qui se trouve le plus à droite des ouvrages à reclasser.

Dans l'animation

on procède de la même façon que dans l'animation précédente.

Par contre la stratégie étant imposée pour le choix du livre à déplacer, il suffit de cliquer la flèche dans tous les modes MANUEL, AUTO ou bien ULTRA rapide, pour procéder à une étape (mode MANUEL) ou au rangement complet des ouvrages.

 




ANALYSE et résultats

Très vite, on peut observer que le nombre maximal d'étapes est obtenu avec la stratégie de la deuxième partie.

Le temps de rangement peut devenir très grand lorsque les ouvrages sont classés d'une certaine façon.
Trouver des dispositions donnant un nombre d'étapes maximal.

Essayer de faire un maximum d'observations avant d'aller ci-dessous ou ICI chez Diophante.fr pour en savoir un peu plus.

DÉMONSTRATION mathématique

    Il vaut mieux ne pas déranger les livres...


Menu trucs  Accueil