Exercice de SUP sur suites et permutation
Répondre à la discussion
Affichage des résultats 1 à 19 sur 19

Exercice de SUP sur suites et permutation



  1. #1
    MPSI92

    Exercice de SUP sur suites et permutation


    ------

    Bonjour,

    J'essaye de résoudre un problème depuis plusieus jours sans succès. Quelqu'un a-t-il une idée sur la solution ?

    Soit ak une suite croissante de n éléments positifs (a1, …, an) 0<a1...<an
    Soit bk une suite croissante de n éléments positifs (b1, …, bn) 0<b1...<bn
    Soit ck une permutation de la suite ak : {c1, …, cn} = {a1, …, an}
    Démontrer que la somme de ak * bk >= somme de ck * bk

    Merci à tous pour votre aide

    -----

  2. #2
    JPL
    Responsable des forums

    Re : Exercice de SUP sur suites et permutation

    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  3. #3
    MPSI92

    Re : Exercice de SUP sur suites et permutation

    Ok, merci pour ce lien que je découvre
    Quelques infos sur mes recherches (depuis samedi quand même !), ça devient mon obsession.
    J'ai essayé la récurrence, mais ça ne marche pas car pas possible à mon avis de passer d'une permutation n+1 éléments à une permutation à n éléments
    J'arrive pour n=2 (évident), pour n=3 (facile) et pour quelques cas pour n=4, mais je n'arrive pas à trouver une astuce ou un raisonnement général.
    Donc si quelqu'un l'a déjà résolu, ça m'aiderait bien. Ca semble être un classique de SUP.
    Merci encore à tous les matheux
    Pour info, c'est un sup de LLG qui m'a soumis cet exo, mais ne m'a pas donné la solution

  4. #4
    Universus

    Re : Exercice de SUP sur suites et permutation

    Bonjour,

    Ça semble se faire par récurrence, mais en deux étapes. Donc supposons que le résultat est vrai pour tout et tâchons d'en déduire le résultat pour

    Première étape : supposons que la permutation de fixe le dernier terme, c'est-à-dire que . Ainsi, en comparant les deux sommes, nous avons , de sorte que nous pouvons nous ramener au cas et le résultat est vrai.

    Seconde étape : supposons que dans la permutation de , . Cherchons le terme valant et considérons la transposition de l'ensemble . En appliquant cette transposition à , nous obtenons un -plet vérifiant l'hypothèse faite à la première partie. Ainsi, si nous pouvons montrer que est inférieur à (qui vaut ), nous pourrions conclure par la première partie. Or, cette inégalité n'est que le cas .

  5. A voir en vidéo sur Futura
  6. #5
    ansset
    Animateur Mathématiques

    Re : Exercice de SUP sur suites et permutation

    supposons que tu ne changes que an en aj et réciproquement.
    la somme ck.ak=bk.ak -(an-aj)bn+(an-aj)bj
    soit ck.ak=bk.ak -(an-aj)(bn-bj) qui est <=0
    donc le simple déplacement seul de an vérifie ta proposition.
    or tu peut classifier tes permutations en partant à chaque fois du plus plus grand an restant , dans un ordre unique.
    et chaque permutation t'amène à une valeur inférieure.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  7. #6
    ansset
    Animateur Mathématiques

    Re : Exercice de SUP sur suites et permutation

    sachant qu'ne totale permutation peut s'écrire comme une suite unique ou il est par exemple interdit de changer 2 fois.
    ici an et aj en l'occurence.
    si on repermute aj alors celà revient à avoir permuter an en ak.
    désolé, j'ai oublié d'ecrire somme sur qcq lignes du message précédent.
    Dernière modification par ansset ; 29/01/2015 à 17h44.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  8. #7
    ansset
    Animateur Mathématiques

    Re : Exercice de SUP sur suites et permutation

    en fait il y a même encore plus simple en changeant aj par ak avec j<k
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  9. #8
    Médiat

    Re : Exercice de SUP sur suites et permutation

    Bonjour,

    ansset, je ne suis pas sûr de comprendre votre explication, une permutation est un produit de transpositions (généralement non disjointes), mais elles ne font pas toutes baisser la valeur, puisque lorsque l'on applique la deuxième, l'ordre n'est déjà plus l'ordre initial et peut remettre les éléments transposés dans le bon ordre (ce qui augmente la somme).

    Quitte à travailler dans cette direction, j'utiliserais plutôt le théorème qui dit qu'une permutation peut se décomposer en cycles disjoints, car il ne reste plus qu'à démontrer que le résultat est valide pour un cycle.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  10. #9
    ansset
    Animateur Mathématiques

    Re : Exercice de SUP sur suites et permutation

    je vais essayer de reformuler plus proprement tout à l'heure.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  11. #10
    ansset
    Animateur Mathématiques

    Re : Exercice de SUP sur suites et permutation

    en me relisant, c'est faux tel qu'écrit.
    je ne peux itérer si simplement.
    mais je poursuis mon idée de démarche.
    Cdt
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  12. #11
    Médiat

    Re : Exercice de SUP sur suites et permutation

    Je n'ai pas réfléchi à la méthode pour les cycles, mais la solution d'Universus me paraît plus simple ; personnellement je la modifierais un peu (je garde l'idée de la récurrence) :
    Dans le cas (n + 1) :

    soit il existe un élément invariant et on est revenu au cas (n)
    soit il n'y a aucun élément invariant, et dans ce cas il y a forcément un tel que , en appliquant la transposition qui remet à sa place on est revenu au cas (n) avec un delta dans la somme qui est dans le bon sens (enfin si je ne me suis pas vautré (si je me suis vautré, il suffit de choisir un tel que ))
    Dernière modification par Médiat ; 30/01/2015 à 10h56.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  13. #12
    contrexemple

    Re : Exercice de SUP sur suites et permutation

    Salut,

    En posant que ak=somme(ui,i=1..k) et bk=somme(vi,i=1..k), avec les ui=a(i)-a(i-1)>0 et vi=b(i)-b(i-1)>0 en posant a(0)=0 b(0)=0
    Alors tu peux me semble-t-il en tirer une solution générale.

    Cordialement.

  14. #13
    Médiat

    Re : Exercice de SUP sur suites et permutation

    Ce que j'ai développé dans le message #11 permet de faire la démonstration pour les cycles de façon plus simple.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. #14
    ansset
    Animateur Mathématiques

    Re : Exercice de SUP sur suites et permutation

    Citation Envoyé par Médiat Voir le message
    Je n'ai pas réfléchi à la méthode pour les cycles, mais la solution d'Universus me paraît plus simple ; personnellement je la modifierais un peu (je garde l'idée de la récurrence) :
    Dans le cas (n + 1) :

    soit il existe un élément invariant et on est revenu au cas (n)
    soit il n'y a aucun élément invariant, et dans ce cas il y a forcément un tel que , en appliquant la transposition qui remet à sa place on est revenu au cas (n) avec un delta dans la somme qui est dans le bon sens (enfin si je ne me suis pas vautré (si je me suis vautré, il suffit de choisir un tel que ))
    j'en suis revenu aussi à la lecture de son intervention.
    j'ai cherché plus direct, mais sans aboutir.
    justement ds le sens des cycles, mais cela semble moins évident.
    Cdt
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  16. #15
    Médiat

    Re : Exercice de SUP sur suites et permutation

    Un cycle de taille n+1 peut toujours s'écrire comme un cycle de taille n composé avec une permutation, en choisissant bien la permutation, la récurrence est assurée.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  17. #16
    ansset
    Animateur Mathématiques

    Re : Exercice de SUP sur suites et permutation

    j'ai un doute sur le terme "cycle" que tu emplois.
    dans l'absolu, un cycle concerne l'ensemble des éléments, mais il peut être constitué de plusieurs cycles disjoints.
    pardon si cette question est un peu en dehors de "l énigme" proposée.
    EDIT :je connait déjà la réponse à l'avance.
    une somme de cycles peut être considérée comme un seul cycle.
    Dernière modification par ansset ; 30/01/2015 à 12h38.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  18. #17
    Médiat

    Re : Exercice de SUP sur suites et permutation

    Citation Envoyé par ansset Voir le message
    j'ai un doute sur le terme "cycle" que tu emplois.
    dans l'absolu, un cycle concerne l'ensemble des éléments, mais il peut être constitué de plusieurs cycles disjoints.
    pardon si cette question est un peu en dehors de "l énigme" proposée.
    Une permutation peut se décomposer en cycles disjoints, si chaque cycle fait baisser la somme des éléments qu'il modifie sans modifier la somme des autres (ceux qui ne bougent pas), alors la composition de cycles disjoints (c'est le mot important) fait baisser la somme globale.

    Donc il reste à démontrer qu'un cycle fait baisser la somme, ce qui peut se faire facilement avec ce que je propose dans le message #15 (et qui n'est pas loin de la solution d'Universus)
    Dernière modification par Médiat ; 30/01/2015 à 13h17.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  19. #18
    ansset
    Animateur Mathématiques

    Re : Exercice de SUP sur suites et permutation

    oui, c'est plus clair. ( pour moi j'entend )
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  20. #19
    MPSI92

    Re : Exercice de SUP sur suites et permutation

    Ca y est, j'y suis arrivé !

    Merci à tous pour vos commentaires, ils m'ont largement aidé, et cela m'a permis de "converger" vers la solution, que je décris ci-dessous.

    D'abord reformulons le problème :
    L'énoncé dit que quelque soit la permutation s de (a1,…, an), la somme de bk*as(k) est inférieure à la somme de bk*ak
    Cela veut aussi dire que le maximum de la somme de bk*as(k) pour toutes les permutations de (a1,…,an) est atteint pour la permutation identité (s(k)=k)

    Si on prend une permutation s telle qu'il existe k pour lequel s(k+1) < s(k), démontrons qu'elle n'est jamais maximale

    En effet, si on prend une permutation s1 telle que s1=s si i#k et i#k+1, et s1(k)=s(k+1) et s1(k+1)=s(k), alors s1 est "meilleure" que s

    En effet, si on fait la différence somme de bk*as1(k) - somme de bk*as(k), on voit qu'elle est positive ( on trouve (bk+1-bk)*(as(k)-as(k+1) )

    Par conséquent, la permutation maximale a comme propriété : quelque soit k=1..n-1, s(k+1) >= s(k) (et même s(k+1) > s(k) car c'est une permutation donc s(k+1)#s(k)

    Maintenant, démontrons alors que celle-ci est forcément l'identité (c'est assez facile par l'absurde).

    Supposons qu'elle ne soit pas l'identité
    Soit k le premier élément tel que s(k)#k
    k est forcément <= n-1 (si k=n, alors s est l'identité donc absurde)
    s(k) est forcément > k (car s(k-1)=k-1, s(k)>s(k-1) et s(k)#k
    Il existe forcément j tel que s(j)=k, j est > k, incohérence car j>k et s(j) < s(k) donc absurde, donc s est l'identité
    CQFD

    Voilà, j'espère que c'était clair
    Bon courage à tous et merci encore

    Remarque pour Universus : le raisonnement ne me parait pas bon, car pour appliquer la récurrence à c1,…cn, il faudrait qu'elle soit croissante, ce qui n'est pas forcément le cas

    Cordialement

Discussions similaires

  1. Exercice sur les suites
    Par Biduletrucmuche dans le forum Mathématiques du collège et du lycée
    Réponses: 16
    Dernier message: 02/11/2014, 16h41
  2. exercice sur les suites
    Par 369 dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 10/02/2011, 22h00
  3. Exercice sur les suites
    Par invite99dcb221 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 14/11/2008, 18h34
  4. exercice sur les suites
    Par invitedd9a88f5 dans le forum Mathématiques du collège et du lycée
    Réponses: 0
    Dernier message: 10/02/2008, 18h55
  5. exercice sur les suites
    Par invite56f88dc9 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 30/11/2006, 20h08