Exercice de SUP sur suites et permutation

[invitebb518896]

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
-----

[JPL]

Je t'invite à lire http://forums.futura-sciences.com/ma...ces-forum.html.

[invitebb518896]

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

[invite93e0873f]

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 .

[A voir en vidéo sur Futura]

[invite51d17075]

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.

[invite51d17075]

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.

[invite51d17075]

en fait il y a même encore plus simple en changeant aj par ak avec j<k

[Médiat]

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.

[invite51d17075]

je vais essayer de reformuler plus proprement tout à l'heure.

[invite51d17075]

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

[Médiat]

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 ))

[invite2ec994dc]

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.

[Médiat]

Ce que j'ai développé dans le message #11 permet de faire la démonstration pour les cycles de façon plus simple.

[invite51d17075]

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

[Médiat]

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.

[invite51d17075]

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.

[Médiat]

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)

[invite51d17075]

oui, c'est plus clair. ( pour moi j'entend )

[invitebb518896]

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