Aide pour les futurs mathématiciens
 
AccueilAccueil  PortailPortail  RechercherRechercher  S'enregistrerS'enregistrer  Connexion  

Partagez
 

 Problem 6 IMO 2009 (Day2)

Aller en bas 
AuteurMessage
samir
Administrateur
samir

Nombre de messages : 1872
Localisation : www.mathematiciens.tk
Date d'inscription : 23/08/2005

Problem 6 IMO 2009 (Day2) Empty
MessageSujet: Problem 6 IMO 2009 (Day2)   Problem 6 IMO 2009 (Day2) EmptyJeu 16 Juil 2009, 18:02

Problem 6 IMO 2009 (Day2) Pb610

_________________
وتوكل على الحي الذي لا يموت وسبح بحمده
Revenir en haut Aller en bas
http://mathsmaroc.jeun.fr
ephemere
Féru


Nombre de messages : 43
Date d'inscription : 14/10/2006

Problem 6 IMO 2009 (Day2) Empty
MessageSujet: Re: Problem 6 IMO 2009 (Day2)   Problem 6 IMO 2009 (Day2) EmptySam 05 Sep 2009, 12:59

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.
Revenir en haut Aller en bas
 
Problem 6 IMO 2009 (Day2)
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Rohatsu
» division par 7
» bête étrange découverte au Panama. Le 18.09.2009
» ORPHANEWS: Bulletin du 11 Février 2009
» Budget 2009 à régulariser début janvier : écart de 1 centime

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum des amateurs de maths :: Olympiades :: Divers-
Sauter vers: