Exercice n°4 : éléments de correction
Le singe sauteur
(exercice national)

1. Le nombre 4 est atteignable car
    
2. Le singe n’a pas le choix : et … il est bloqué !!
    
3. Le nombre 9 est atteignable car on a ,
   sans jamais sortir de l’intervalle [0 ; 9].
    
4. Les exemples précédents traitent les carrés 4 et 9.
   Le cas échéant la recherche pour 16 peut donner :
   ,
   en remarquant que l’on ne sort jamais de l’intervalle [0 ; 16].
   L’observation des sommes produites peut amener la solution générale :
   
   
   ( termes qui groupés par 2 donnent 1, soit termes égaux à 1)
   On obtient donc soit .
    L’on reste bien dans l’intervalle .
   D’où est atteignable.
5. 1. Si le nombre n est atteignable, la somme se termine par + n, sinon on sort de l’intervalle et à l’avant-dernière étape on est en 0.
      Il existe donc des a_i valant 1 ou -1 tels que .
      Dans cette somme on sépare les termes positifs dont on note la somme S₊ des termes négatifs dont on note la somme S_-.
      On a alors : S₊ = S_-.
      On calcule ensuite :
      On en déduit que : d’où et donc 4 divise le produit  n(n - 1).
      Donc n est de la forme 4k ou 4k+1.
      Par exemple 18 n’est pas atteignable.
       
   2. La réciproque est fausse puisque 5 x 4 est multiple de 4 et que 5 n’est pas atteignable.
       
6. L’idée est de transformer une configuration de signes + - en - +, cela va ajouter 2 au nombre N.
   Ensuite on complète par la suite et l’on trouve .
   Remarquons que la séquence donnant N se termine par et commence par 1 + 2 + 3.
   On note S(i) la somme partielle des i-premiers termes, le premier signe – apparaissant en position i + 1.
   Alors , car .
   On change alors la sous-séquence i - (i + 1) en -i + (i + 1), ce qui est possible.
   On ajoute la séquence , ce qui assure que est lui aussi atteignable.