Bonjour
Les données sont les couples (ak, bk), k€{1,…,9} ; ak , bk 0 ;
Le problème consiste à calculer le minimum de l'ensemble E des nombres (ar(bs)) obtenus en permutant les couples (ak, bk) de toutes les façons possibles (9! ).r de 1 à 9 et s de r à 9.
Quelles sont les permutations qui donnent le minimum de E?
Bonjour,
Tels que les éléments de E sont présentés, ils sont de valeurs constantes.
S'agit-il plutôt de avec P
P:ensemble des permutations de {1,2,...,9} ?
Intuitivement, un rangement dans un ordre des et le rangement dans l'ordre contraire des puis la somme des produits des ainsi appariés semble donner la valeur minimum.
Supposons en renumérotant éventuellement les ai et bj que et
cette somme sera minimale si chaque facteur entre parenthèses est négatif ou nul.
Bonjour
Dans le cas de 3 couples (a1,b1) etc...une permutation, par exemple
(a1,b1);(a2,b2);(a3,b3) donne comme somme a1(b1+b2+b3)+ a2(b2+ b3)+ a3b3.
vous prenez une autre des 3! permutations des 3 couples et vous calculez le nouveau nombre obtenu.
Est-ce plus clair?
A+
Bonjour,
mes yeux m'ont joué un tour, je n'avais pas perçu le "r" pour somme de r à 9
Je vais donc revoir ma copie.
bonjour,
Toute permutation est la composée d'inversions et toute inversion est la composée d'invertions d'indices consécutifs.
Il suffit donc d'onbserver l'effet sur la somme d'une inversion de type(i,i+1)
Or le résultat est simple.
Soit la permutation de départ (1,2,...,9) et la somme associée, alors la différence entre la somme obtenue pour la permutation est
Ce résultat peut s'interpréter comme or ce déterminant est positif si (avec
Le fait d'avoir un résultat positif montre que l'on obtient une somme inférieure avec cette inversion.
En conclusion il faut ranger les par ordre d'argument décroissant
et la permutation qui donne la somme minimale est celle-ci.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :