Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils PDF Recherche PDF Aide Contact



ConcoursGmaths2015 .pdf


Nom original: ConcoursGmaths2015.pdf

Ce document au format PDF 1.4 a été généré par / dvipdfmx (20070518), et a été envoyé sur fichier-pdf.fr le 01/04/2015 à 18:33, depuis l'adresse IP 128.178.x.x. La présente page de téléchargement du fichier a été vue 453 fois.
Taille du document: 33 Ko (2 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Exercice 1
Voici ma solution du premier exercice :
On notera P(x1 , x2 , ..., xn ) le poids de la suite (x1 , x2 , ..., xn ), C l’algorithme de Clara et I celui d’Isabelle.
1) P=|3+5|=8
2) P=|1+2+...+2015|=|

∑2015
i=1

i |=2016x1008=2032128

3) Cas n=2. Soit (c1 , c2 ) la suite fournie par l’algorithme de Clara sur (x1 , x2 ). On a par la definition du poids
C=max(|c1 |, |c1 + c2 |). On a par C que |c1 | ≤ |c2 | et donc la suite fournie par I est (c1 , c2 ) car max(|c1 |, |c1 + c2 |) ≤
max(|c2 |, |c1 + c2 |) et l’algorithme I est optimum donc I va forcement prendre le poids de la permutation (c1 , c2 ). I
et C fournissent la meme suite, donc I=C.
4) On note (a,b,c) la suite fournie par C. On voit deja que C(a,b,c)=|a| ⇒ I(a,b,c)=C(a,b,c) car |a|=min(|a|,|b|,|c|).
De la meme facon, si C(a,b,c)=|a+b+c| alors I(a,b,c)=C. On s’interesse donc au cas ou C(a,b,c)=|a+b|. On peut
deja ecarter le cas ou I ne permute pas (a,b,c)⇔ I=C. De la definition de l’algorithme C on peut tirer :
|a| ≤ |b|
|a| ≤ |c|
|a + c| ≥ |a + b|
|a| ≤ |a + b|
et donc soit |a+b|=|a|+|b| (meme signe), soit 2|a| ≤ |b| et |a+b|=|b|-|a| (signes differents).
Des inegalites ci-dessus, on tire que :
- I ne peut pas permuter (a,b,c) en (b,a,c) car max(|b|,|a+b|,|a+b+c|)=I≥max(|a|,|a+b|,|a+b+c|)=C.
- I ne peut pas permuter (a,b,c) en (a,c,b) car max(|a|,|a+c|,|a+b+c|)=I≥max(|a|,|a+b|,|a+b+c|)=C.
- I ne peut pas permuter (a,b,c) en (c,a,b) car max(|c|,|a+c|,|a+b+c|)=I≥max(|a|,|a+b|,|a+b+c|)=C.
- I permute (a,b,c) en (b,c,a) ou (c,b,a)
a) On considere d’abord le cas ou |a+b|=|a|+|b| (meme signe). On a |a+b+c|≤|a+b| donc c est de signe oppose
a a et b. Cela nous donne |a|+|b|≤|c|-|a|⇔ |c| ≥ 2|a| + |b| ⇔ 2|a| ≤ |c| − |b|. I va donc forcement, par |c|≥|b|,
permuter (a,b,c) en (b,c,a). On a maintenant deux possibilites : I=|b|≥|c|-|b| ou I=|c|-|b|≥|b|.
Prenons I=|c|-|b|⇔ |b| ≤ |c| − |b| ⇔ |b| ≤ 2|a|. Alors CI = |a|+|b|
|c|−|b| . Pour maximiser cette expression, il faut minimiser
|c|-|b| avec b,a fixe. On a |c| − |b| ≥ 2|a| + |b| − |b| = 2|a| donc on prend |c|-|b|=2|a| ⇔
|a|+2|a|
2|a|

C
I

=

|a|+|b|
|c|−|b|

=

|a|+|b|
2|a|



= 3/2.

Prenons I=|b|. Alors

C
I

=

|a|+|b|
|b| .

Pour maximiser cette expression, il faut minimiser |b| pour |a| fixe. On a |b|≥|c|-|b|

donc 2|b|≥|c|≥2|a|+|b| donc |b| est minimum lorsque |b|=2|a|. D’ou

C
I



|a|+2|a|
2|a|

= 3/2.

b) On considere maintenant |a+b|=|b|-|a| avec |b|≥2|a|. Par |a+b|≥ |a+b+c| on a que c et a sont du signe oppose
a b. Cela nous donne |b|-|a|≤|c|+|a|⇔ |c|+2|a| ≥ |b| ≥ 2|a|. On va maintenant utiliser |a+b+c|=||a|-|b|+|c||≤|b|-|a|.
On distingue d’abord le cas ou |b|≥|c|+|a| : dans ce cas, I permute (a,b,c) en (c,b,a) car |b|≥|c|. On a aussi
|b|≥|c|+|a|⇔|b|-|a|=C≥|c| donc I=|c| implique I=C ou est impossible. On a donc forcement I=|b+c|=|b|-|c| or
|b|-|c|≤|b|-|a|=C donc I=|b+c| implique I=C ou est aussi impossible.
On considere maintenant le cas ou |c|+|a|≥|b| ⇔ |c| ≥ |b| − |a|. Si dans ce cas, I=|c|, on a

1

C
I

=

|b|−|a|
|c|

donc on minimise c avec a et b fixes : on prend |c|=|b|-|a| donc
I=C. Si I=|b|, alors il est evident que |a|=0 et I=C par

|b|−|a|
|b|

C
I

=

|b|−|a|
|c|



|b|−|a|
|b|−|a|

= 1 dont on deduit

≤ 1. On ne peut pas avoir I=|b+c| ⇔, soit

|c| ≤ |b| − |c| ⇔ 2|c| ≤ |b| ⇔ |c| + |a| ≥ |b| ≥ 2|c| ⇔ |a| ≥ |c| (contradiction) soit |b| ≤ |b| − |c| (contradiction).
Ainsi, on a toujours C ≤ 32 I.
5) a) On a I = max(|x1 |, |x1 + x2 |, ..., |x1 + x2 + ... + xn | = S) donc par la definition du maximum on a I≥S.
b) On pose I = |x1 + ... + xa | avec 1≤a≤n. Pour tout i on a donc I≥ |x1 + x2 + ... + xi | et I≥ |x1 + x2 + ... + xi + xi+1 |.
Si xi+1 est du meme signe que |x1 + x2 + ... + xi |, alors on a I ≥ |x1 + x2 + ... + xi + xi+1 | = |x1 + x2 + ... + xi | + |xi+1 |
donc 2I≥ I ≥ I − |x1 + x2 + ... + xi | = |xi+1 |.
Si xi+1 est du signe oppose a |x1 +x2 +...+xi |, alors on a I ≥ ||x1 +x2 +...+xi |−|xi+1 ||. Soit |x1 +x2 +...+xi | ≥ |xi+1 | :
rien a prouver car I≥ |x1 + x2 + ... + xi | ≥ |xi+1 |, soit ||x1 + x2 + ... + xi | − |xi+1 || = |xi+1 | − |x1 + x2 + ... + xi | et
on a 2I ≥ I + |x1 + x2 + ... + xi | ≥ |xi+1 |.
Comme ceci est valable pour tout xi+1 , on a bien l’inegalite demandee.
c) Nous demontrons par l’absurde. Tout d’abord, si C = |x1 + x2 + ... + xn |, alors C=S et donc C≤N. Sinon,
on pose C = |x1 + ... + xi | avec 4≤i≤n-1.
On suppose C≥M. Puisque |x1 + x2 + ... + xi−1 | ≤C, on a xi du meme signe que x1 + x2 + ... + xi−1 ou
|xi | ≥ 2|x1 + x2 + ... + xi−1 | avec xi de signe oppose. De la meme facon, C ≥ |x1 + x2 + ... + xi+1 | ⇔ xi+1 est du signe
oppose a C et |xi+1 | ≤ 2C. On a bien |xi+1 | ≤ M par la definition de M. Si |xi+1 | ≥ |x1 + x2 + ... + xi−1 |,
C prendrait xi+1 a la suite de xi−1 car |x1 + ... + xi−1 + xi+1 | = |xi+1 | − |x1 + ... + xi−1 | ≤ |xi+1 | ≤ M
donc on a forcement |xi+1 | ≤ |x1 + x2 + ... + xi−1 | or dans ce cas, C prendait xi+1 a la suite de xi−1 car
|x1 + ... + xi−1 + xi+1 | = |x1 + ... + xi−1 | − |xi+1 | ≤ |x1 + ... + xi−1 | ≤ C (contradiction) donc on a forcement C≤M.
d) Soit N=M et donc par c) et b) on a C≤2I. Sinon, N=S et donc par c) et a) on a C≤ S ≤ I ≤ 2I.
e) Si n est pair, la suite (1, 2, 4, ..., 2n/2 , −1, −2, −4, ..., −2n/2 ) convient. Si n est impair, on ajoute 0 a la suite.

Au final, ma solution de la question 4) me parait juste mais trop longue et non adequate. A voir si une demonstration par l’absurde ne serait pas beaucoup plus simple.

Arthur Parmentier

2


ConcoursGmaths2015.pdf - page 1/2
ConcoursGmaths2015.pdf - page 2/2

Documents similaires


Fichier PDF cgexo1arthurp
Fichier PDF concoursgmaths2015
Fichier PDF concoursgmaths2015 1
Fichier PDF courstribulle
Fichier PDF td1 2014 sm
Fichier PDF vdc


Sur le même sujet..