e3a Maths 1 PSI 2015

@
E 3 a
CONCOURS ARTS ET MÉTIERS ParisTech -- EST? - POLYTECH

Épreuve de Mathématiques [ PSI

Durée 4 h

Si, au cnurs de l'épreuve, un candidat repère ce qui lui semble être une erreur 
d'énnncé.

d'une part Il le signale au chef de salle. d'autre mm il le signale sur sa 
copie et poursuit sn
composition en indiquant les raisons des initiatives qu'il est amené à prendre.

L'usage de calculatrices est interdit.

AVERTISSEMENT

La présentation, la lisibilité. l'orthographe, la qualité de la rédaction, la 
clarté et la
précision des raisonnements entreront pour une part importante dans
l'appréciation des copies. En particulier. les résultats non justifiés ne 
seront pas pris
en compte. Les candidats sont invités à encadrer les résultats de leurs calculs.

Tournez la page S.V.P

Il est Interdit aux cnnriiduls de signer leur cnmpnsltlun ou d'y mettre un 
signe quelconque pouvant Indiquer un pravennnce.

Le sujet est constitué de quatre exercices qui testent plusieurs compétences 
complémentaires des
programmes de mathématiques et d'« informatique pour tous » de le fiiiére PSI.

Il est donc demandé au candidat de répartir équitablement son troveil sur les 
quatre exercices
proposés. Il en sera tenu compte dans l'évaluation de l'épreuve.

EXERCICE 1-

But de l'exercice

i.ejeu d'euheo se joue sur un échlqulsr, c'est s dire sur un pleteeu de 8 x & 
cesse. Ces nues
sont referencées de el A li8 (of. figure),

Une piece, appelée le enveller. se déplace suivant un "L" imegineire d'une 
longueur de doux
cesse et d'une largeur d'une esse.

Exemple : un cavalier situe sur le esse de atteint, en un seul déplmment. une 
des huit
cases hu. c6. sli. l'E. IS. e2. c! et ba (Voir figure cl-contre).

Deus toute le suite de l'exercice. ou appellera else permise toute pose que le 
cevsller
peut atteindre en un «pincement A partir de se position.

Le but de est exercice est d'écrire un progremme faisent percourir l'ensemble 
de l'échiquier
A un csvnlier en ne pensent sur cheque esse qu'une et une seule fel-.
Motivation et methode retenue

Une premiere idee est de foire poreourlr toutes les cases possibles A un 
cevsller en listent A
cheque deplecement les cases parcourues. Lorsque celui--ci ne peut plus evmcer 
on consulte
le nombre de cases parcourues.

- si ce nombre est égal A 04 = 8 x 8. alors le problème est rAsolu.

- Sinon, il (eut revenir en arriére et tester d'entres chemins.

0. Exemple : on considère le parcouru suivent d'un cevoiier démursnt en el 
(figure
ci contre) :

el.bB,c1.e2,cG.hñ,e3.c4.d2.
Avec ce début de parcours. nu «placement suivent :
e. le csv-lier va en bl. Peut--ll sommplir se mission?
b. le cavalier ne va pes en bl. Peut-ll ecoompllr se mission?

il convient donc dans le résolution du problème proposé d'éviter de se 
retrouver dans la
situation repérée :) la question 0.

Dune tout ce qui suit. nous nommerons coordonnées d'une case le liste d'entlers 
[i,j] ou
{ représente le numéro de ligne et j le numero de colonne (tous deux compris 
entre 0 et T).
Per exemple. le case le:} e pour coordonnées [2. l].

D'autre part. les cases sont numérotées de 0 "33 en percent du coin gauche 
comme indique
per la figure (zi--contre.

Nous appellerons indlce d'une case le numéro 11 compris entre 0 et 68 Mini 
déterminé.
Ainsi la case M e pour Indice ".

Les questions

1. Écrire une fonction Indice qui aux coordonnees |r'.j] d'une esse renvoie son 
indice.
Ainsi| Indien appliquée s [2, il doit renvoyer ".

2. Ecrire une fonction Coord qui, A l'indice VI d'une CME renvoie la liste 
[l.j] de ses coordonnées.
Ainsi Coord appliquée a 17 doit renvoyer (2. 1].

:. On con»idtru la fonction P thon CuA suivante :
clef CaeA(n):
Deplacementc : [[i, -2], [2, --l], [L l], [i, 2]. [-1, il. [--2. 1]. 14. -i]. 
[--1, --2|]
L = []
i. ] : Coord(n)
l'or d in Dapluccmonts:

\: i +d[0l
v ] +d[11
ll' u >=O and u (8 and v >=!) and v < 8: L.sppend(lndice(lu, VI)) return L 3.1 Que renvoient CasA(0) et CalA(39) 7 a.: Expliquer en une phrase ce que fait cette fonction. 4. Ecrire une fonction 1niz ne prenant aucun argument et qui modifie deux variables globales LletecA et List-Coupe. List-Ceupa recevra la liste vide []. Lu «CA recevra une liste de ce elements. Chaque element Luc-CA [n] (pour 0 < 1: < 63) devra contenir la lista des lndicu dau cessa qu'un cavalier peut Atteindre en un coup a partir du la case d'indice n. 5. Après exécution de la fonction Inlt(), la commande >>> List-CHO] renvoie :

u-- [5]
b- [10.11]
c- [10.11,0]
d-- [17.o,10]
«' il

f- Elle renvoie une autre valeur.

0. Au cours de le recherche. lorsqu'on dûplacc le cavalier vers la case 
d'indice n. cet indice " doit etre retire de la liste dee
caler permises a partir de la punition n.

Example :

Aprte execution de la fonction Iait(). la liste dau cures permi-ua depuis bl 
est [n3,c3,d2], et List-CAD] vaut [re, le, H].
La lllte des cases permises depuis eZ est [bb.cd,c2,bli et LilteCAC16] vaut 
[33,26,10.1].

Puis on choisit de commencer le parcours en posent le cavalier en bl: Cette 
case doit donc être retir0e de la liste des cases
permises de a3. ca et d2.

En particulier pour all, la Hate Mat-CAEN] devient : [33.26. 10].

Cette méthode nous permet de detecter le: blocage» :

Le cavalier arrive sur la case d'indice » : n est clore retiré de toutes les 
listes L1eteCA[k] pour toute case d'indice !: permiwe
pour n.

Si des lors l'une de ces listes devient vide. nous dirons alors que nous sommes 
dans une lituatlou critique. cela aigniflera
que la cane d'indice !: ne peut plus être atteinte que depuis la case d'indice 
n. Par conséquent :

. si le cavalier ae deplace sur une autre case que celle d'indice k, slors 
cette dernière ne pourra plus jamais être atteinte;
. ni le cavalier se deplace sur la casa d'indice lc, le cavalier est bloque 
pour le coup suivant. Et :

-- soit la miusion eat accomplie,

-- lait la cavalier n'n pas parcouru toutes les ouen...

Le programme va réaliser la recherche en malntenant a jour la variable globale 
Liu-Coups afin qu'elle contienne en
permanence la liste des positions succeuivea occupées par le cavalier au cours 
de ses tentatives de déplacement.

Nous avons alors beeoin d'ecrire trois fonctions :

6.1 Ecrire une fonction D::upoPolition qui :
. prend comme Argument un entier n (indice d'une case). l'aloute e la fin de la 
vulnble globale Li-uCoupa,
. puis enleve n de tonton les lintou Line-CA [k] pour toutes les cases d'indice 
le permise: depui! la cale d'indice n.
- renvoie enfin la valeur True. si nous sommes dans une situation critique et 
Fai-e sinon.

On pourvu ulliieer la méthode remove qui permet de retirer d'une lim: le 
premier dément (gai & l'argument fourni. Si
l'a _ "ie de la Hate une erreur rem mtuumde.

L=[i. 2. 3. 4. 2. il]

L.remeve(2)
L

Le: commanch chddenta renvoient in line [1.3.4.2.5].

L: 11, a, a, 4, 2, &]
L.mmove(6)

La commande: pMc£dentcu provoquent une emur.

0.2 Ecrire une fonction LibarePo-icten qui ne prend pas d' ugument et qui
. récupère la dernier GIàment u de la variable globale Lil:nCoupa (i e. n est. 
l'indice de la derniere cane jouée il l'aide
de la fonction DccupePo-ltlon(n) ),
- puis i'enleve de Liu-Coupe.
. et enfin. qui ajoute " A toutes la lime Luc-CAM pour toutes lee ouen d'indice 
le permises depuis la eue d'indice
n.

A le fin de cette fonction les listes Luc-Coup et Line-CA seront donc dans le 
même otut qu'evont l'exécution de la
fonction uecupoPoeitlon(n).

071 oum utiliser in méthode -0' ui pouvais le dernier dément d'une liste et le 
au rime de cette même iiatc.
[l . 2. 8 d 2. 5. 2]

L P°P ()
Leu communch précédente: affectent la valeur 2 a la variable ». le (ici: L 
étant cnruitc .- [1.2.3.4.2.5].

e.a Écrire une fonction TueuPe-ieion d'argument un entier n (indice d'une case) 
qui :
. occupe la position d'indice n.
. verifie si la situation est critique.
Si tel est le aux
-- le fonction vtrlfloru si 63 cases vont oceuptoe et dans ce ou renverre True 
pour indiquer que le recherche ont
terminbo,
-- Si les us eue: ne ront pas occupéee. le fonction libèrera la case d'indice n 
et renverre Fai-e.
Dans le ou contraire
-- la fonction vérifient. A l'aide de le fonction Tueul>euieien(k). touten lon 
ouen d'indice ): ]ouebloa après la cam
d'indice n. On prendra garde li a.fl'ecter une variable locale avec le. liste 
Liu-CA En] puisque celle--ci risque d'etre
modifiée lors dee appele suivante.
-- La fonction retournera Tru- d6e qu'un nppol e ToceePoütion(k) retourne Tru- 
ou liban-ere la une d'indice n
«t retournera Pal-e si tout; les appele A TutePo-uien(k) retournent Fol-e.

1. Afin de reduire notnblement la complexité temporelle du programme on part du 
principe qu'il faut tenter en priorité lee
ouen n.yent le moine du canon permi... possible. On appellera valuatlon d'une 
cave d'indice n le nombre de cases permlaeu
pour cette cm.

1.1 Ecrire une fonction vein-tion qui prend comme argument un indice n de une 
en entree et renvoie le valuetion de
cette case.

1.2 Ecrire une fonction l'union qui prend comme argument deux listes A et ! 
constituâefi checune d'entieru neturele entre
0 et 83 (A et B nout donc des lieter d'indice de cases) ; on suppose que ces 
listes. A et B eont triéen par ordre croleeent
de veiuation du leurs Mémento; la fonction Fusion(A.B) retourne dion comme 
valeur la liste fusionnée de tous les
elements de A et B triee par ordre orale-ent de vnluntlon de son elements.

1.8 Écrire une fonction TziFn-ion qui prend comme argument une iiete [. 
d'entiere compris entre 0 et 63, A priori non
lupposêfl triés par vainntion croioeante de sen elements. et qui retourne comme 
valeur le line de tone les éléments de
!. triés par velnetion croiumtn de lu Mémentu.

1.4 Modifier la fonction TeenPention pour qu'elle agisse ainsi que l'on a. 
decide en début de queuion.

Exllfllcl 2-

0
l.SoitA-(
1/--4

!
21) E flæ(R)4

Déterminer une condition necessaire et suffisante pour que la murine A soit. 
diagonniisebie dans /1(IR).

!. On note E; - (u & R+, u" ; N) et Eq son complementaire dans R+.

Pronver que Eq est un ensemble dénombrabla,
3. Soient (mu) un espace probabilisuble et ! l'implication de R+ dans R définie 
par :
0 si n' ; N
Vu E R+, f(fl) = ,\

2--uf sinon

D0tnrminer A e R pour qu'il existe une probabilitA ? wi que ] noir la loi de 
probabilité d'une vnriehle aleatoire X définie
sur n et A valeurs dans R+.

Precieer X(n).
4. DMerminer x'(n) et la loi de probabilité de x".
iL Déterminer l'espérance E(X") de la variable aléatoire X 7.

«. Déterminer ln fonction génératrice de la variable nieatoira X ".

Retrouver alor: la valeur de E(X') obtenue ». la question précédente.

1. Soit Y une variable aleatoire définie sur n, lndàpondmte de la variable 
aleatoire X et suivant la loi :

0 n uÇN
VuER... iP(Y-u)- 1
WT einen

Soi: clore Z le vuinble a.lùntoim définie sur il par : Z - X ' + Y.

Déterminer la fonction gènêrurice de 2, En dAduire nn loi de probabilité.

!
!. Déterminer enfin le probabilltb pour que la matrice A - ( ) E .I;(R) ID". 
diagonalieubie.

Y--4 2X

+oe dt
Exulwlcn :. 0 l i t "ai , -/ .
n pore, oreque ce a en pose e [(m) | m

!. Determiner i'enoembie de définition ! de ].

+eo di
2. En jurtifimt son existence. ceiculer /v e" + °__.

:. Ce.icuier ](1). (On pourra utiliser l'applicetion @ : u EUR Il; >--u p(u) - 
ch(u)).

4. Calculer f(2). (On pourra remarquer que 1. derivee de x .... % ... egeie A x 
_, EFI--(;))

5. Vorifler que /' est positive eur ! .
0. Montrer que ] ent décroissante sur I.

1. Prouver que [ eut de cleeee C' eur ! et préciser i'exprueeion de f'(z).

Retrouver e.iere le reeuitet de le question précédente.

8. Suit :: E !. Démontmr le reietion : 1
m + :) - m [(«-')

On pourra effectuer. en le justifiant. une intégretion pu partie:.
0. Soit 1: EUR N'. Donner i'expreeeion de f(2p) A l'aide de tutorieiie».

m. Pour tout réel 1- etrictoment positif. on pces :
æ(.w) - "(l')/(= +1)
Prouver que u>(z +1) - d:(w).

Calculer t(") pour tout entier naturel " non nul.

11. En utiiinent le question precedente. d6tflrminer un Aquiveient eimpie de 
f(r) ioreque : tend vers 0 par valeurs supérieures.

n. Vérifier que : Vu 5 N'. fin)/(..... 1) - 21"

En déduire que Vn & N'. !(u) --« IQ".

u--u+m

vr

la. En utiiiuunt dee putiee entières. prouver que : [(x) .. :

l-v+w

14. Déduire due quentiene precedenth le tableau du vn:iutionn de ! eur ] et 
trmer en courbe mpmentntive dann un repère
orthonorm0.

u. Prouver que le fonction @ eut constante sur R1.

EXIRCKCI 4.

Dons tout l'exercice. pour tout entier nnturel k, on identifie polynôme de IR;, 
[X ] et fonction polynomiole uneclae pour la structure
d'eau... vectoriel norme.

1. Soit P un element de R[X] unitaire (le terme de plus haut degre du P est ew 
& l).

1.1 Soit a E IR.

Montrer que : Vz & C. |: -- al > |Im(z)|.

1.2 On uuppose dann cette question que P est ucinde sur lit.

En utilisant une futorluatlon de P. montrer que :
V: e @. |P(=)| > llm<:)l"""" ou deg(P) désigne le degré du polynôme P. 1.3 On prend dens cette question P(X) - X' +1. (a) Donner une fmtorisntion de I' dans C[X). (b) "cuve: tn & C toi que : lP(z«)i ( |lm(zu)|""(P) 1.4 On suppose dans cette question que : V: 6 C, |P(z)| > llm(z)l'"'...

Montrer que toutes lee ruines de F sont molles. En déduire que P est scindé eur 
III.
1.5 Enonccr clnlrement le résultat obtenu.

2. Soient (; un entier naturel non nul et (A..)..EN une suite de matrices 
trlgouullnnbles de .fl,(lR) qui converge vers une matrice
A.

On appelle pour tout entier naturel n, P,, le polynôme caractéristique de A,. 
et P celui de la matrice A.
2.1 Donner le degré et lo coefficient dominent de P...

2.2 quver que : Vu: E R. "HT.--= B.(w) - P(w).

2.8 En d6duiru que Il est trlgonulieuhlo.

2.4 Qu'en conclut--on pour l'ensemble des matrices trigouellsebles de Æ,,(R) '!

i _ _i_ i _ slnn
a. On prend dans cette question q - 2 et A.. - " :
o 1 + ;

5.1 Déterminer A - lim A...
...--+...

8.2 Etudier le diegondisabilitd des matrices A,. et A dans M,(R).

3.9 Conciure.