J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

Mines Mathématiques 1 PC 2018

Théorème de Komlos

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Algèbre linéaireProbabilités finies, discrètes et dénombrement
Logo mines
🔗 Explorer
Banque
Mines
Année
2018
Filière
PC
Matière
Maths
Mines PCMines 2018PC MathsMaths 2018
2025_08_29_7ef4f0eb1314053dd319g

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH, MINES SAINT-ÉTIENNE, MINES NANCY, IMT Atlantique, ENSAE PARISTECH.

Concours Centrale-Supélec (Cycle International), Concours Mines-Télécom, Concours Commun TPE/EIVP.

CONCOURS 2018

PREMIÈRE ÉPREUVE DE MATHÉMATIQUES

Durée de l'épreuve : heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :

MATHÉMATIQUES I - PC

L'énoncé de cette épreuve comporte 6 pages de texte.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.
Notations :
  • Si est un nombre réel on note sa partie entière, c'est-à-dire le plus grand entier relatif qui est inférieur ou égal à .
  • On appelle cardinal de l'ensemble fini le nombre de ses éléments, que l'on note .
  • On note l'ensemble des parties de l'ensemble .
  • Dans tout le problème on identifiera à l'espace des matrices lignes et on notera le produit scalaire canonique des deux vecteurs, soit
les étant les composantes de respectivement.
  • Si est un sous-ensemble de on note l'espace vectoriel engendré par . On note l'orthogonal de , c'est-à-dire l'ensemble des vecteurs tels que .
  • Si est une matrice carrée de nombres réels, on note son déterminant.
Dans tout le problème on pourra utiliser librement la formule de Stirling que l'on rappelle :
Définition 1 (Espace de Rademacher) Si n, , on note
Pour tout et , on introduit la variable aléatoire telle que
On munit de la probabilité uniforme . Cela signifie que les variables aléatoires ( ) sont indépendantes et de même loi:
Si , on note la matrice aléatoire
On note les vecteurs lignes de . Par construction, ce sont des vecteurs aléatoires indépendants et de même loi.
Le but du problème est de démontrer, qu'ainsi construite, une matrice aléatoire est inversible avec forte probabilité quand est grand:
Théorème 1 (Komlós) .

A Coefficients binomiaux

  1. Soit : montrer que l'application
est croissante sur . En déduire que pour tout ,
  1. Trouver un équivalent de quand tend vers l'infini. En déduire qu'il existe un entier tel que pour ,
  1. Montrer que pour tout entier non nul et tout ,
On note ( ) la base canonique de et . On identifie et le sous-ensemble de
  1. Pour tout , exprimer en fonction de et . En déduire que .

B Dimension 2

  1. Déterminer l'espérance de .
  2. Montrer que la variance de est égale à 2 .
  3. Calculer .

C Quelques bornes

On suppose dorénavant .
8. Quelle est la probabilité que les deux premières lignes de soit égales ou opposées?
En déduire que si .
9. Soient des vecteurs non nuls de . Montrer que ces vecteurs sont liés si et seulement si, il existe tel que
En déduire que
Soit un sous-espace vectoriel de de dimension . On rappelle que est un sous-espace vectoriel de dimension et que .
10. Montrer alors qu'il existe des réels ( ) tels que
  1. En utilisant le pivot de Gauss, montrer qu'il existe tel que pour tout il existe un unique tel que pour .
  2. En déduire que
puis que pour tout ,
Indication : on pourra utiliser la conséquence suivante de la formule des probabilités totales
et l'indépendance des vecteurs lignes.
Soit et . On note ses vecteurs lignes.
13. Montrer que l'on peut trouver un vecteur non nul orthogonal à qui soit à coordonnées dans .

D Théorème de Erdös-Littlewood-Offord

Définition 2 Soit un entier non nul. Soit un sous-ensemble de . On dit que est une anti-chaîne si deux éléments distincts quelconques de sont incomparables, c'est-à-dire tels que n'est pas inclus dans et n'est pas inclus dans .
Commençons par un exemple. Soit et l'ensemble des parties de de cardinal .
14. Montrer que est une anti-chaîne et que
la deuxième inégalité ayant lieu pour assez grand.
Définition 3 Soit une anti-chaîne et , de cardinal noté . On note , l'ensemble des bijections de dans lui-même telles que la restriction de à soit une bijection de dans .
15. Quel est le cardinal de ?
16. Soit avec . Montrer que .
17. En déduire que si désigne, pour , le nombre d'éléments de de cardinal , alors
  1. Montrer que
Soit tel que , pour tout . Si on pose
où est le complémentaire de dans .
19. Montrer que si , alors
  1. Soit un intervalle ouvert de de longueur 2 : montrer que si est assez grand alors
Montrer que cette propriété reste vraie si l'on suppose seulement que pour tout .
Indication : construire une bijection entre et l'ensemble des parties de . Construire une anti-chaîne intéressante.

E Universalité

Dans tout ce qui suit, est un entier inférieur à .
Définition 4 Soit . L'ensemble est dit -universel si pour tous les -uplets et tout , il existe tel que
  1. Soit . Montrer l'inclusion
(On rappelle que ).
22. Montrer que la probabilité que ne soit pas -universel est majorée par
  1. En déduire que si et , alors, pour assez grand,
  1. Soit un ensemble -universel tel qu'il existe : montrer que a au moins coordonnées non nulles.
En vertu de la question 13, on peut supposer que les coordonnées de sont des entiers relatifs.
25. Montrer que si est assez grand
Soit ( ) une suite croissante d'entiers telle que .
26. Montrer que si est assez grand alors et
Indication : on distinguera les cas selon que est -universel ou pas et l'on prendra .

F Théorème de Komlós

  1. En déduire le théorème de Komlós.
Indication : on pourra partir de (2) et choisir convenablement une suite ( ).

Fin du problème

Mines Mathématiques 1 PC 2018 - Version Web LaTeX | WikiPrépa | WikiPrépa