a. On peut construire une autre liste de longueur 8 et de score 3 en changeant l'ordre de certains éléments tout en gardant 3 inversions. Par exemple :
[4,2,6,7,1,5,3,8]
Ici on a inversé 2 et 5 par rapport à la liste initiale, ainsi que 6 et 7, tout en gardant le même nombre d'inversions (3).
b. Avec n=3, il y a 3! = 6 listes possibles. Les voici avec leur score :
- [1,2,3] : score 0 (liste triée dans l'ordre croissant)
- [1,3,2] : score 1 (une inversion 3-2)
- [2,1,3] : score 1 (une inversion 2-1)
- [2,3,1] : score 1 (une inversion 3-1)
- [3,1,2] : score 1 (une inversion 3-2)
- [3,2,1] : score 2 (deux inversions 3-2 et 3-1)
def score(L, n):
compteur = 0
for i in range(n-1):
if L[i] < L[i+1]:
compteur += 1
return compteur- Score minimum = 0. C'est le cas quand la liste est triée dans l'ordre croissant, il n'y a alors aucune inversion.
- Score maximum = n-1. C'est le cas quand la liste est triée dans l'ordre décroissant. Il y a alors une inversion entre chaque paire d'éléments successifs, soit n-1 inversions.
- Exemple de liste avec score 0 : [1, 2, 3, ..., n]
- Exemple de liste avec score n-1 : [n, n-1, n-2, ..., 1]
a. On peut construire une telle liste comme suit : on prend les k plus grands éléments dans l'ordre décroissant, puis on ajoute les n-k plus petits éléments dans l'ordre croissant. Cette liste aura alors exactement k inversions.
Par exemple avec n = 8 et k = 3 :
[7, 6, 5, 1, 2, 3, 4, 8]
b. Oui il existe plusieurs listes avec le même score k. Par exemple avec n = 5 et k = 2 :
[4, 5, 1, 2, 3]
[5, 4, 1, 2, 3]
Ces deux listes ont toutes les deux exactement 2 inversions (entre 4 et 1, et entre 5 et 1).
L_n(0) = 1 car il n'y a qu'une seule liste possible avec 0 inversion : la liste triée par ordre croissant.
L_n(n-1) = 1 car il n'y a qu'une seule liste possible avec n-1 inversions : la liste triée par ordre décroissant.
a. Avec n = 3 :
L_3(0) = 1 (liste [1,2,3])
L_3(1) = 3 (listes [2,1,3], [1,3,2] et [3,1,2])
L_3(2) = 1 (liste [3,2,1])
Pour insérer 4 et garder un score de 1, on peut insérer 4 entre 1 et 2 : [3,1,4,2]
b. Pour insérer 4 et garder un score nul, on insère 4 avant 3 : [4,3,2,1]
c. Avec n = 4, vérification de la formule L_4(1) = 2L_3(1) + 3L_3(0) = 23 + 31 = 6
d. Démonstration de la relation de récurrence générale :
- Pour compter les listes de longueur n+1 et de score k, on regarde la position d'insertion de n+1 :
- Si on insère n+1 à la fin, cela crée k nouvelles inversions et on avait une liste de longueur n et score k. Il y a L_n(k) listes possibles.
- Si on insère n+1 en iième position, cela crée k-i nouvelles inversions. On avait une liste de longueur n et score k-i. Il y a L_n(k-i) listes possibles pour chaque position d'insertion i.
- Il y a donc au total :
- (n+1-k)*L_n(k) listes avec insertion à la fin
- (k+1)*L_n(k-1) listes avec insertion en position intermédiaire
D'où la relation L_(n+1)(k) = (n+1-k)*L_n(k) + (k+1)*L_n(k-1)
e. Formule générale par récurrence : L_(n+1)(k) = (n+1-k) * L_n(k) + (k+1) * L_n(k-1)
f. Tableau des valeurs de L_n(k) :
| k \ n | 3 | 4 | 5 |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 1 | 3 | 6 | 10 |
| 2 | 1 | 15 | 35 |
| 3 | - | 20 | 56 |
| 4 | - | - | 70 |
-
b = -(r1 + r2)
c = r1*r2 -
Comme b ≤ 0 et c ≥ 0, les racines r1 et r2 sont de signes opposés. Voici une proposition pour continuer le développement des réponses :
- a. Soit (x1, x2, x3) une solution de (E). Alors : |x1|^2 + |x2|^2 + |x3|^2 = α|x1||x2||x3| par parité des fonctions carré et valeur absolue. Donc (|x1|, |x2|, |x3|) est aussi solution de (E).
b. S'il existe une solution (x1, x2, x3) dans Z^3 avec un xi non nul, alors (|x1|, |x2|, |x3|) est une solution dans N^3.
-
Si (x1, x2, x3) est solution de (E), alors en permutant x1 et x2, on obtient que (x2, x1, x3) est aussi solution de (E).
-
D'après les questions précédentes, s'il existe une solution dans Z^3 différente de (0,0,0), alors il existe aussi une solution (x1, x2, x3) dans N^3 avec x1 ≤ x2 ≤ x3.
-
Supposons x1 = 0. Alors d'après (E), on a x2^2 + x3^2 = 0, donc x2 = x3 = 0. Ce qui contredit le fait que (x1, x2, x3) est différent de (0,0,0). Donc nécessairement x1 > 0.
-
a. Montrons que y racine de Q <=> (x1, x2, y) solution de (E) :
- Si y racine de Q, alors Q(y) = 0, donc x1^2 + x2^2 + y^2 = αx1x2y, donc (x1, x2, y) solution de (E).
- Réciproquement, si (x1, x2, y) solution de (E), alors x1^2 + x2^2 + y^2 = αx1x2y, donc Q(y) = 0, donc y racine de Q.
b. x3 est racine de Q car (x1, x2, x3) solution de (E).
c. Q(x2) = (3 - αx1)x2^2 + (x1^2 - x2^2) < 0 car x1 > 0 et x2 > x1 d'après l'énoncé.
d. Q(0) = x1^2 + x2^2 > 0
e. Q a deux racines 0 < x2 < x3. De plus, Q(x2) < 0 et Q(0) > 0 donc il existe une racine y > x3 par le théorème des valeurs intermédiaires.
f. Comme y est racine de Q, d'après a., (x1, x2, y) est solution de (E) dans N^3.
-
On peut réappliquer le raisonnement précédent en remplaçant x3 par y, et trouver un nouveau triplet solution encore plus grand, et ainsi de suite. Cela conduit à une impossibilité car il n'y a pas de suite strictement croissante infinie d'entiers naturels.
-
On aboutit à une contradiction. Donc le seul triplet solution de (E) dans Z^3 est (0,0,0).
-
Généralisation au cas de n variables :
On procède par récurrence sur n. L'initialisation pour n=2 est immédiate. Supposons le résultat vrai jusqu'à l'ordre n-1, avec n ≥ 3. Raisonnons par l'absurde en supposant qu'il existe un n-uplet (x1, ..., xn) solution de l'équation avec un xi ≠ 0.
En appliquant un raisonnement similaire aux questions précédentes, on peut se ramener à un n-uplet (x1, ..., xn) dans N^n avec x1 ≤ ... ≤ xn.
On définit alors Q(y) = y^2 - αx1...xn-1y + (x1^2 + ... + xn-1^2). On montre comme précédemment que Q admet deux racines distinctes xn et y avec y > xn.
Donc (x1, ..., xn-1, y) est un (n-1)-uplet solution de l'équation analogue en dimension n-1. Ceci contredit l'hypothèse de récurrence.
D'où finalement le seul n-uplet solution est (0, ..., 0).