Je vais faire une démonstration par récurrence sur n.
Si il y a un seul saut à faire, le problème est trivial.
S'il n'y a que deux sauts à faire le problème est trivial aussi : un des deux premiers sauts est bon comme premier saut et l'autre sera bon pour conclure.
Pour n>2, je suppose que la sauterelle peut éviter (n-2) points de M si elle a (n-1) sauts à faire, je suppose aussi que la sauterelle peut éviter (n-3) points de M si elle a (n-2) sauts à faire, et je vais prouver qu'elle peut éviter (n-1) points de M si elle a n sauts à faire.
Premier cas : supposons que la sauterelle n'atterrisse pas sur un point de M mais qu'elle saute par dessus d'un point de M en faisant le plus long saut possible. C'est le cas le plus simple : la sauterelle fait d'abord ce plus long saut, puis on applique simplement l'hypothèse de récurrence après le premier saut car il ne lui reste que (n-2) points de M à éviter et elle a encore (n-1) sauts à sa disposition.
Deuxième cas : supposons que la sauterelle n'atterrisse pas sur un point de M et qu'elle ne saute pas par dessus d'un point de M en faisant le plus long saut possible. Après, ce plus long saut, il lui resterait alors à faire (n-1) sauts. Soit x le premier point de M qui arrive après l'endroit où se trouve la sauterelle après avoir fait le plus long saut en premier. Par hypothèse de récurrence, la sauterelle peut éviter tous les points de M-{x}. Si jamais la sauterelle ne passe pas par x, c'est gagner. Si jamais elle passe par x, on permute son premiers saut (le plus long) avec celui qui est après le moment où elle arrive en x et c'est gagné aussi.
Troisième cas : supposons que la sauterelle atterrisse sur un point de M en faisant le plus long saut possible. On fait alors faire à la sauterelle le plus long saut possible parmi ceux qui ne l'amènent pas sur un point de M. Ce saut existe bien puisque il existe n sauts possibles et qu'il n'y a que (n-1) points dans M. Si la sauterelle a sauté par dessus un point de M en faisant ce saut, tout est fini grâce à l'hypothèse de récurrence (comme dans le premier cas). Sinon, on note A le nombre de points de M compris entre l'origine et le point (inclus) de M où la sauterelle arrive en faisant le plus long saut possible comme premier saut.
Troisième cas, partie 1 : A>0. On remplace le premier saut de la sauterelle par un saut qui ne l'amène pas sur M et qui est en plus tel qu'elle ne tombe pas non plus sur un point de M en faisant le plus long saut juste après ce premier saut. Ceci est toujours possible car il n'y a plus que (n-1-A) points de M après le point de M où la sauterelle arrive en faisant le plus long saut possible comme premier saut. Or, (n-A) sauts sont OK comme premier saut. De plus, comme A>0, on aura alors fin grâce à l'hypothèse de récurrence car la sauterelle n'aura plus que (n-2) sauts à faire et que (n-3) points de M à éviter.
Troisième cas, partie 2 : A=0. On fait comme dans la partie 1 de ce troisième cas. On ne peut conclure directement que si un deux points de M sont passés avec les deux premiers sauts. Si ce n'est pas le cas, on doit avoir recourt au même artifice que dans le second cas : on néglige le premier point de M arrivant après le second saut quitte à permuter (si nécessaire) le saut qui suit le contact ((éventuel) entre la sauterelle et ce point) et le saut le plus long.
Accueil 
