Mathématiques 1999 Classe Prepa B/L Concours Ecole Normale Supérieure
5 pages
Français

Mathématiques 1999 Classe Prepa B/L Concours Ecole Normale Supérieure

Cet ouvrage peut être téléchargé gratuitement
5 pages
Français
Cet ouvrage peut être téléchargé gratuitement

Description

Concours du Supérieur Concours Ecole Normale Supérieure. Sujet de Mathématiques 1999. Retrouvez le corrigé Mathématiques 1999 sur Bankexam.fr.

Sujets

Informations

Publié par
Publié le 18 mars 2007
Nombre de lectures 66
Langue Français

Extrait

ENS
SESSION DE 1999
COMPOSITIONDEMATHEMATIQUES
Sujet commun :ENS Ulm-Cachan-Fontenay
Durée :4 heures
Lénoncé comporte 5 pages
Calculatrice autorisée
1/5
PROBLEME I Les trois parties peuvent être traitées indépendamment.
NOTATIONS ET DEFINITIONS On dénit un graphe niGcomme la donnée dun couple(S; A)Sest un ensemble ni appelé ensemble des sommetsdu graphe, etAune partie de lensemble (2) S=f(s; t)= s2S; t2S; s6=tg des paires de sommets deS:LensembleAest appelé ensemble desarêtesdu grapheG: Par exemple, siG= (S; A)S=fa; b; c; d; egetA=ffa; bg;fb; cg;fc; dg;fd; ag;fc; egg;alors G est le graphe dont les sommets sonta; b; c; d; eet pour lequel il existe une arête entreaetb; betc; cetd; deta; ceteà lexclusion de toute autre.On pourra représenter ce graphe par le schéma :LorsqueA=;;on dit que le graphe
Figure 1:Représentation du grapheG
(2) na pas darêtes et lorsqueA=S ;on dit queGest un graphe complet. On appellecoloriagedeGàkcouleurs,k2N;toute applicationc:S7! f1; ::; kg(on suppose que lon dispose dekcouleurs di¤érentes numérotées de1àkpour colorier les sommets du graphe et quec(s)donne le numéro de la couleur du sommets):On dit quecest un coloriage propre si deux sommets reliés par une arête nont pas la même couleur, cest-à-dire si pour toussettdansS; c(s)6=c(t)lorsquefs; tg 2A: On noteraPG(k)le nombre de coloriage propres distincts àkcouleurs deGet lon appeleranombre chromatique deG;noté(G)la plus petite valeur dekpour laquelle il existe un coloriage propre deGayant ce nombre de couleurs (G) = inffk2N= PG(k)6= 0g
PARTIE I 1. OnposeS=fa; b; cgexiste-t-il de graphes distincts dont les sommets sont donnés par. CombienS?
2. OnconsidèreS=fa; b; cg; A=ffa; bg;fb; cg;fc; aggetG= (S; A)
(a) Calculerle nombre chromatique(G)deG: (b) CalculerPG(k)pourk2N:
3. OnposeS=fa; b; c; dg,A=ffa; bg;fb; cg;fc; dg;fd; agget on considère le grapheG= (S; A)que lon peut représenter par le schéma
(a) Calculerle nombre chromatique(G): (b) CalculerPG(k)pourk2N:
(2) 4. Onsuppose maintenant queScontientpéléments avecp6= 0:Calculer le cardinal deS ;ensemble des paires de sommets.Combien existe-t-il de graphes distincts dont les sommets sont donnés parS?
5. SoitGun graphe ni quelconque ayantpsommets,p2N:
2/5
Figure 2:Représentation du grapheG
p(a) MontrerquePG(k)6kk ;2N: p (b) Montrer,en cherchant une minoration dePG(k)pourkassez grand, quePG(k)ka une limite quand ktend vers+1et calculer cette limite.
PARTIE II Soitp2N; p>3etSp=fs1; ::; spgun ensemble depsommets distincts.On appelle graphe linéaire dordrep, le grapheGp= (Sp; Ap)Ap=ffsi; si+1)= i2 f1; ::; p1gg: f ff On appelle graphe cyclique dordreple grapheGp= (Sp; Ap)Ap=Ap[ fsp; s1g:
e Figure 3:Représentation du grapheG5etG4
(krk2N: 1. CalculerPGp)pou 2. OnnoteP(k)le nombre de coloriages propres deGpàkcouleurs pour lesquelsc(s1) =c(sp): Gp  (a) MontrerqueP(k) =PG(k)P(k)pour toutk2N: Gp+1Gp p   (b) Calculerla valeur deP(k)pour toutk2N: Gp 3. Trouverune relation très simple qui lieP(k)etP(k)= f G Gp p+1 queP(kxpression polynôm 4. Onveut montrer dans cette questionGp)est une eiale enkpour tout graphe ni G:On suppose ici queG= (S; A)est un graphe quelconque ayantpsommets(p2N)etmarêtes(m2N) (a) Sim= 0;calculer(G)etPG(k)pourk2N 0 00 On se place maintenant dans le casm >0:Il existe alors une arêtefs; sg 2A:On noteG= (S; A) 0 00 le graphe obtenu en retirant àGlarêtefs; sg;cest-à-dire pour lequelA=Anffs; sgg:On notera  00 P0(k)le nombre de coloriages proprescdeGàkcouleurs tels quec(s) =c(s): G   (b) MontrerquePG(k) =PG(k)P0(k)pour toutk2N: 0 G 00 0000  (c) Montrerquil existe un grapheGayantp1sommets etmarêtes avecm6mtel queP0(k) = G PG(k): 00 (d) Endéduire par récurrence sur la valeur dep+mque, pourp>2; PG(k)est un polynôme de degrép pour lequel p p1 PG(k) =kmk+QG(k) QGest un polynôme de degré inférieur ou égal àp2:
3/5
PARTIE III SoitG= (S; A)un graphe ayantpsommets (p>3)etmarêtes. Pourchaques2S;on considère une variable aléatoireCsà valeurs dansf1; ::; kgaveck2N:On suppose que les variables aléatoires sont indépendantes et 1 identiquement distribuées de loi uniforme surf1; ::; kg;cest-à-direP(Cs=j) =pour toutk2 f1; ::; kgets2S: k 1. Onsuppose ques; tetusont3sommets distincts deS:CalculerP(Cs6=Ct)etP(Cs6=CtetCt6=Cu) P 2. OnnoteN= 11 s6=Ctla variable aléatoire qui vaut1lorsqueCs6=Ctet0sinon. G Cs6=CtCest fs;tg2A CalculerE(NG), espérance deNG;en fonction deketm: 3. Montrerque la variance deNGvaut k1 V(NG) =m : 2 k 4. Montrerque pour toutk>m; " #   2 k1km 2 P(NG6m1)6P NG( )m>( ) k k
puis montrer que pour tout" >0;il existek2Ntel que pour toutk>k, on a 0 0 1 +" P(NG6m1)6( )m k (on pourra utilisant sans démonstration linégalité suivante :siXest une variable aléatoire telle queE(jXj) E(jXj) existe, alorsP(jXj>M)6;pour tout réelMstrictement positif). M p p1p1 5. Endéduire, sans utiliser les parties précédentes, quePG(k)>kmk+f(k)k ;fest une fonction telle quelimf(k) = 0:Comparer ce résultat avec celui de la dernière question de la partie précédente. k!+1
PROBLEME II Dans ce problème, on considère une fonctionf: [0;1]!Rcontinue que lon supposera dérivable sur]0;1[et de dérivée bornée sur]0;1[:Soientp2[0;1],nun entier strictement positif et(Xi)16i6nune famille de variables aléatoires indépendantes et identiquement distribuées de loiBp, cest-à-dire queP(Xi= 1) = 1p(Xi= 0) =p: On pose dans la suite, n X 1 Sn=Xi n i=1 1. (a)Montrer quil existe un réel positifM0tel que 2 8(x; y)2[0;1];jf(x)f(y)j6M0 (b) Montrerquil existe un réel positifM1tel que 2 8(x; y)2[0;1];jf(x)f(y)j6M1jxyj 2 (c) Endéduire que, pour toutréel strictement positif et tout(x; y)2[0;1];on a 2 (xy) jf(x)f(y)j6M0+M12 2. OnnoteV(X1)la variance deX1:Montrer que   SnM0V(X1) E ff(p)6+M1 2 n n
4/5
A 3. On noteg:]0;+1[!Rla fonction dénie parg(x+) =Bx, oùAetBsont deux constantes réelles 2 x strictement positives.Montrer quegatteint son minimum en un pointxque lon calculera, puis donner la valeur de ce minimum.
4. Déduireque
  1=3 2 M SnM1 0p(1p) E ff(p)63   n4n
Sn 5. MontrerqueE(f=( ))Qn(p)Qnest un polynôme de degré inférieur ou égal àn: n 6. Montrerlexistence, pour tout" >0;dun polynômeRtel que pour toutp2[0;1];jf(p)R(p)j6"et montrer que lon peut supposer 2 27 M0M1 degR <+ 1 2 16"
5/5
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents