Il me semble que l'exemple du sujet (qui donne (10,8,5) pour(1,4,2,3,7,6,5,9,10,8)) montre que la suite dont vous parlez n'est pas extraite... Ou alors je n'ai pas compris ce que vous dites.
Concours commun des mines MP MATHS 1
Re: Concours commun des mines MP
Re: Concours commun des mines MP
Au temps pour moi, je suis allé vite en besogne : la méthode est plutôt de partir du plus haut terme de la dernière pile, puis de revenir dans le temps au moment précis où l'on a posé
le terme en question, et de passer au plus haut terme de la pile précédente, etc...
Difficile de formaliser sans récurrence, effectivement.
le terme en question, et de passer au plus haut terme de la pile précédente, etc...
Difficile de formaliser sans récurrence, effectivement.
Professeur de Mathématiques en MP*/MPI* au lycée Hoche
Re: Concours commun des mines MP MATHS 1
D'ailleurs, si je ne m'abuse, une récurrence (finie) sur le numéro de la pile pour montrer que tout élément de la pile i est le i eme terme d'une i-liste décroissante extraite de la liste initiale me parait bien plus simple à rédiger qu'une récurrence sur s.
Pour i=1 c'est évident
Prenons i >=2
Un élément z de la pile i ne peut être plus grand que tous les éléments de la pile i-1 qui le précèdent dans la liste a (sinon il ne serait pas sur une nouvelle pile)
Donc il est plus petit qu'un certain élément de la pile i-1 numéroté avant lui dans la liste a et l'hypothèse de récurrence achève la preuve de l'hérédité
Si quelqu'un a une démo par récurrence sur s, je suis preneur (je ne vois pas très bien quel prédicat poser)
Pour i=1 c'est évident
Prenons i >=2
Un élément z de la pile i ne peut être plus grand que tous les éléments de la pile i-1 qui le précèdent dans la liste a (sinon il ne serait pas sur une nouvelle pile)
Donc il est plus petit qu'un certain élément de la pile i-1 numéroté avant lui dans la liste a et l'hypothèse de récurrence achève la preuve de l'hérédité
Si quelqu'un a une démo par récurrence sur s, je suis preneur (je ne vois pas très bien quel prédicat poser)
Professeur de maths MP Lycée Sainte-Geneviève
Re: Concours commun des mines MP MATHS 1
J'ai procédé comme vous pour la récurrence sur s, mais en affirmant qu'en utilisant le processus sur une liste a' semblable à a en ayant retiré les les valeurs des éléments de la s-ème pile on obtient exactement la même configuration pour les s-1 premières piles. On peut alors utiliser l'hypothèse de récurrence. Mais c'est cest moins rigoureux que la récurrence sur i en effet.
2016-2018 : MPSI/MP*
2018-... : dept maths ENS de Lyon
2018-... : dept maths ENS de Lyon