1)    a)  Quel est le dossard du skieur qui passe en dernier pour un effectif de 27 skieurs? 54 skieurs? Justifier les réponses.

b) Exposer une méthode permettant de répondre à cette question pour un effectif plus important, par exemple en se ramenant à un effectif plus faible que celui proposé (il n'est demandé ni "formule", ni démonstration.)

2)    Le perchman fait maintenant passer 2 skieurs sur 3, en commençant par les dossards 1 et 2, les recalés revenant comme précédemment se remettre en bout de file.

Quel est le dossard du skieur qui passe en dernier si l'effectif vaut 3^p, p étant un entier naturel non nul? Justifier la réponse.

Solution.

La calculatrice va nous permettre de remplir, grâce à un programme, le tableau demandé et de faire un certain nombre d'essais pour pouvoir conjecturer et développer une méthode.

1) Commençons par prendre n = 14  et regardons ce qui nous reste après chaque "tour".

Départ:   L₀ = {1;2;3;4;…;12; 13; 14}              14 éléments

                 L₁ = {2; 4; 6; 8; 10; 12; 14}                7 éléments

                 L₂ = {4; 8; 12}                                     3 éléments

                 L₃ = {4; 12}                                         2 éléments

                 L₄ = {12}                                              1 élément

Remarquons que:

Pour passer de L_n à L_n+1, on prend un terme sur deux de L_n.

 Si L_n et L_n+1 se terminent par le même nombre, le premier nombre de L_n+2  est le deuxième de L_n+1

Si L_n et L_n+1 ne se terminent pas par le même nombre, le premier nombre de L_n+2  est le premier de L_n+1

Créons un programme utilisant cet algorithme:

Utilisons ce programme pour remplir le tableau proposé:

Pour 27 et 54 regardons ce que donne le programme.

  Donc avec 27 et 54 skieurs on terminera par les dossards 22 et 44.

  En faisant d'autres essais avec des puissances de 2 on constate que c'est le plus grand numéro qui passe en dernier.

Donc il suffit de se ramener à une puissance de 2  pour connaître le dernier à passer.

Supposons que n = 260, on fait passer les  dossards 1, 3, 5, et 7 les dossards 2, 4, 6 et 8 sont passés au bout de la file et le dernier de la file a le numéro 8. Comme il ne reste que 256 skieurs, c'est le 256 ème qui passera en dernier, c'est à dire celui qui porte le dossard n°8.

On peut aussi remarquer que le dernier à passer porte le numéro double du nombre de skieurs à éliminer pour arriver à la plus grande puissance de 2 inférieure au nombre de départ.

  3)       S'il y a 3^p skieurs, après un passage de toute la file, il ne reste plus que 3^p-1 skieurs qui ont pour dossards les numéros 3, 6, 9, …. 3^p. (c'est à dire les nombres de la forme 3k)

Après le deuxième passage de toute la file, il ne reste plus que 3^p-2 skieurs qui ont pour dossards les numéros  9, 18, 27, …. 3^p. (c'est à dire les nombres de la forme 9k)

Et le denier de la file a toujours le même numéro. En poursuivant ainsi, le dernier à passer sera le numéro 3^p.

Complément.

" Et si on écrivait un programme pour résoudre cette question dans le cas n quelconque."

Commençons par prendre n = 65  et regardons ce qui nous reste après chaque "tour".

Départ:   L₀ = {1;2;3;4;…;63; 64; 65}              65 éléments

                 L₁ = {3; 6; 9; 12; …57; 60; 63}          21 éléments

                 L₂ = {3;12; 21; 30; 39; 48; 57}           7 éléments

                 L₃ = {3; 30; 57}                                   3 éléments

                 L₄ = {57}                                              1 élément

Remarquons que:

Pour passer de L_n à L_n+1, on prend un terme sur trois de L_n.

 Si L_n et L_n+1 se terminent par le même nombre, le premier nombre de L_n+2  est le troisième de L_n+1

Si  L_n+1 se termine par l'avant dernier de L_n , le premier nombre de L_n+2  est le deuxième de L_n+1

Si  L_n+1 se termine par l'avant avant dernier de L_n , le premier nombre de L_n+2  est le premier de L_n+1

Créons un programme utilisant cet algorithme:

(pour simplifier le programme on s'arrêtera dès que la liste L1 aura moins de trois éléments, on affichera les deux dernières listes  et on terminera éventuellement à la main)

Exécutons ce programme.

Choisissons n = 65

Le dernier à passer sera donc le dossard 57.

Et pour n = 47

Le dernier à passer sera le dossard 30.

Et si on complète le tableau de départ: