X/ENS Maths A MP 2016

ÉCOLE POLYTECHNIQUE -- ECOLES NORMALES SUPÉRIEURES

CONCOURS D'ADMISSION 2016 FILIÈRE MP

COMPOSITION DE MATHÉMATIQUES -- A -- (XLCR)

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

***

Toute afiirmation doit être clairement et complètement justifiée.

Soit n> 1 un entier. On appelle point entier de R" un point dont toutes les 
coordonnées
sont entières, c 'est-- a--dire un point de Z". Si IC est une partie de R", on 
note IC son intérieur.

On appelle points entiers de IC (resp. points entiers intérieurs) les points de 
IC fi Z" (resp.
les points de IC fi Z"). On note respectivement Card(IC @ Z") et Card(IC 0 Z"), 
le nombre
(éventuellement infini) de points entiers de IC et de son intérieur IC.

Soit h5 l'homothétie de rapport O E R (centrée en 0), on note BIC : h3(IC) 
l'image de IC par
h5. Si Tæ est la translation de vecteur &: E R'", on note IC --- a: : T_oe(IC) 
l'image de IC par T_oe.

Si M : (mig-) est une matrice de M...,(R), m,;j est le coefficient de la i--ème 
ligne et de la j--ème
colonne.

On note (æ1| -- - - la,) la matrice de M,,(R) dont les colonnes sont les 
vecteurs æ1, . . . ,oen E R".
On note I,, la matrice identité de M,,(R) et E,;j la matrice de M,, (R) dont 
tous les coefficients
sont nuls sauf celui de la 7Z--ème ligne et j--ème colonne qui vaut 1.

On note Mn (Z) l'ensemble des matrices de M,,(R) dont tous les coefficients 
sont entiers.

On note LaJ la partie entière d'un réel & : c'est le plus grand entier 
inférieur ou égal à a; et
{a} = a---- La) E [O, 1[ la partie fractionnaire de a.. On note )aL le plus 
grand entier strictement
inférieur à a.

On rappelle que des entiers al, . . . , ak, non tous nuls sont dits premiers 
entre eux dans leur
ensemble si pgcd(a1, . . . ,ak) = 1.

Première partie

1. Soit M EUR M,,(R) une matrice inversible et à coefficients entiers.
la. Montrer que M _1 est à coefficients rationnels.

1b. Montrer l'équivalence des pr0positions suivantes :

i) M "1 est à coefficients entiers.
ii) detM vaut 1 ou --1.

Dans la suite, on note GLn(Z) l'ensemble des matrices carrées de taille n à 
coefficients entiers
et de déterminant il. C'est un sous--groupe de GLn(R). On remarque que pour t' 
# j et e E Z,
la matrice I,, + CE,-j appartient a GLn (Z).

2. Soit M = (:... . . -- p.,) EUR GL,,(R).

2a. Montrer que M EUR GLn(Z) si et seulement si M (Zn) : Z".

2b. Montrer l'équivalence des propositions suivantes :
i) M & GLn(Z).

'ÏL
ii) Les points entiers du parallélépipède ? = {thoez ! Vi EUR {1,. . . ,n}, t.; 
E [0,1]} sont
73=1

TL
exactement les 2" points Eat-wi, où ei EUR {0,1} pour tout i E {1,. . . ,n}.
i=1
3. Pour tout oz dans R et pour tous entiers i et j distincts compris entre 1 et 
n, décrire

l'effet sur une matrice carrée M de taille n de la multiplication a gauche par 
In +Oinj. Même
question pour la multiplication à droite.

4. Soient al, . . . ,an des entiers non tous nuls. Le but de cette question est 
de montrer qu'il
existe une matrice de Mn (Z) dont la première colonne est (al, . . . ,a") et de 
déterminant
pgcd(a1, . . . ,un). Pour cela on raisonne par récurrence sur n.

Soit N E Mn_1(Z) une matrice dont la première colonne est (dg, . . . ,on). 
Étant donnés
u, U EUR @, on considère la matrice

4a. Exprimer det M en fonction de det N , u et @.

4b. On suppose que les @, . . . ,an sont non tous nuls et que detN = pgcd(a2, . 
. . ,on).
Montrer que l'on peut choisir u, v de sorte que M réponde à. la question. 
Oonclure.

5. Soit M EUR Mn(Z), de déterminant non nul. On souhaite montrer qu'il existe 
une matrice
A dans GLn(Z) telle que MA soit triangulaire supérieure et en notant MA = 
(cz-j), on ait
l'inégalité 0 < cij < Cii pour tous z',j EUR {1, . . . ,n} tels que i < j. 5a. On note M : (oe1| -- - - |oen). Soient oe'1, . . . ,oeÇ. les éléments de Z"_1 obtenus en prenant les (n ---- 1) dernières coordonnées de 331, . . . ,a:n. n Montrer qu'il existe a1, . . . ,an dans @, non tous nuls, tels que E ai 332 = 0. Montrer que l'on i=1 peut choisir les 0..- entiers et premiers entre eux dans leur ensemble. 5.,b' Montrer qu'il existe une matrice A1 dans GLñ(Z) telle que la première colonne de C = M A1 ait tout ses coefficients êi1 nuls sauf le premier 611 que l'on peut prendre strictement positif. 5c. En considérant pour tout j = 2, . . . ,n la division euclidienne 61j = qj511 +73, 0 < 73 < 611, montrer que l'on peut supposer 611 > E1j, quitte à changer A1.

5d. Oonclure par récurrence.

6. Soit M EUR Mn(Z), de déterminant non nul. Montrer qu'il existe une matrice A 
dans
GLn(Z) telle que AM soit triangulaire inférieure et en notant AM = (cz-j), on 
ait l'inégalité
0 < cij < 011 pour tous i,j EUR {1,...,n} tels quej < 75. Deuxième partie Soient 30,31, . . . 7sn des points de R" tels que les vecteurs 31 -- sg, 52 -- so, . . . ,sn -- so soient linéairement indépendants. On appelle simpleæe de sommets 30,31, . . . ,sn l'ensemble : 'ÏL TL S= {thslei=1,....,n, t. 20, Zt.=} i=0 i=0 'n n ={SO+ZÉz(Sz--SO)IVZ= , ,n,tz>O,th<1} i=1 Z=1 Si de plus les si sont tous des points entiers, on dit que S est un simplexe entier. On définit le volume du simplexe 8 de sommets 80,81, . . . , sn par 1 Vol(8) := 7--1--'| det(31 -- so, 32 -- so, . . . ,sn ---- S())l. 7. Soit 8 le simplexe de sommets 30,31, . . . ,sn. 7 a. Montrer S est un compact convexe de R'". . " n 71). Montrer que 8 = {ztfit |Vi = 1,...,n, tz-- > O, Zti = 1}.
i=0 i=0

En déduire que si 0 E 8, alors, pour tout À E [0,1[, ÀS C 8 .

7c. Pour i = O, . . . ,n, on note 5. = (1,si) le point de Rn+1 dont les 
coordonnées sont 1
suivi des coordonnées de si. Exprimer | det(â07 sl, . . . ,à")! en fonction de 
Vol(8 )
En déduire que le volume d'un simplexe ne dépend pas de l'ordre des sommets.

8. Soit V > 0 un réel.

8a. Donner un exemple de simplexe entier de R2, de volume supérieur ou égal à. 
V, et
n'ayant aucun point intérieur entier.

8b. Donner un exemple de simplexe entier de R3, de volume supérieur ou égal à 
V, et dont
les seuls points entiers sont les sommets.

9. Soit IC un compact convexe de R" tel que 0 EUR IC.

9a. Montrer que l'ensemble des À 2 0 tels que --ÀIC C IC est un intervalle.

On note
a(IC) = sup{À ; OI ---- ÀIC C IC}.

9b. Montrer que a(IC) < 00 et que a(IC) = max{À > O] --ÀIC C IC}.

9c. _ Montrer que 0 < a(IC) < 1. En déduire que a(IC) = 1 si et seulement si IC est symétrique par rapport a 0. On admettra le résultat suivant que l'on pourra utiliser sans démonstration pour la suite du problème. Théorème 1. Soit 8 un simpleæe de R" et le un entier. Si Vol(S) ; k, il eæiste Ic + 1 points distincts oO, . . . ,vk de 8 tels que o.; -- Uj EUR Z" quels que soient i et j entre 0 et k. 10. Dans toute cette question, 8 est un simplexe de R" tel que 0 EUR 8 . On veut montrer c...@...Zn).2J...(Æpÿp. On pose alors a = a(S), et k = JVOI(S) (@ î 1)n { 103. Exprimer, pour fl E R et oe E R'", Vol(fi5) et Vol(S -- 33). Montrer que pour A E [0,1] suffisamment proche de 1, Vol ( Au 8) > le.

a + 1
. . . . Àa , .
10b. Soeent u0, . . . ,uk les le + 1 pomts d1stmcts dans + 18 ver1fiant ui -- 
uj EUR Z" pour
a
. . , - ; / \ ' ('Ui _ vj)a
tous i, 3, dont lex1stence est assuree par le Theoreme 1. Montrer que les pomts 
----+--1--
@
Àa ..
sont dans + 18 . En déduire que les v.- ---- uj sont dans S .
a.

10EUR. Montrer qu'il existe un indice j E {O, . . . ,le} tels que les (27EUR + 
1) points 0, i(ui -- uj),
pour i E {O, . . . ,k} \ {j} soient distincts. En déduire l'énoncé de la 
question 10, puis que

2

Troisième partie

Oard(Ë o Z") ; v01(5) ("(S) ) n .

On dit que deux simplexes 8 et S' de R" sont équivalents s'il existe un ordre 
d'énumération
des sommets 30,31, . . . , sn de S, et 36, s'1, . . . ,s.'n de S', et une 
matrice A de GLn(Z) tels que
A(si -- so) = 3,2- -- 56 pour tout i = 1,...,n.

11. Montrer que deux simplexes entiers S et S' sont équivalents si et seulement 
s'il existe
une matrice A E GLn(Z) et un vecteur I) E Z" tels que S' = A(8 ) -- b.

12. Montrer que le volume, le nombre de points entiers et le nombre de points 
intérieurs
entiers sont les mêmes pour deux simplexes entiers équivalents.

13. Soit 8 un simplexe entier. Montrer qu'il existe des entiers ci > 0 pour i = 
1, . . . ,n, et
un simplexe S' équivalent à 8, tels que 5' C HÎ=1[O,C1] et que

TL

H c.-- = n! Vol(S).

i=1

On pourra utiliser la. question 6 pour une matrice M bien choisie.

14. Montrer qu'un simplexe entier 8 est équivalent à. un simplexe contenu dans 
le cube

[O, n! Vol(S)]".

On admet le résultat suivant que l'on pourra utiliser sans démonstration.

Théorème 2. Pour tout entier strictement positif le, il existe une constante 
strictement

positive C(n, le) telle que pour tout simpleoee entier 8 de R" possédant 
eæactement le points
intérieurs entiers, Vol(S) < C(n, k:). 15. Déduire du Théorème 2 que pour tout entier strictement positif le, il n'existe a équiva-- lence près qu'un nombre fini de simplexes entiers de R." ayant exactement le points intérieurs. * >I< *