CCENS 1999 mathematiques classe prepa b/l

Publié par

ENSSESSION DE 1999COMPOSITION DE MATHEMATIQUESSujet commun : ENS Ulm-Cachan-FontenayDurØe : 4 heuresL ØnoncØ comporte 5 pagesCalculatrice autorisØe1/56666PROBLEMEILes trois parties peuvent Œtre traitØes indØpendamment.NOTATIONSETDEFINITIONSOn dØ…nit un graphe …ni G comme la donnØe d un couple (S;A) oø S est un ensemble …ni appelØ ensemble dessommets du graphe, et A une partie de l ensemble(2)S =f(s;t) = s2S; t2S; s =tgdes paires de sommets de S: L ensemble A est appelØ ensemble des arŒtes du graphe G:Par exemple, si G = (S;A) oø S = fa;b;c;d;eg et A = ffa;bg;fb;cg;fc;dg;fd;ag;fc;egg; alors G est le graphedont les sommets sont a;b;c;d;e et pour lequel il existe une arŒte entre a et b; b et c; c et d; d et a; c et e àl exclusion de toute autre. On pourra reprØsenter ce graphe par le schØma :Lorsque A = ;; on dit que le grapheFigure 1: ReprØsentation du graphe G(2)n a pas d’arŒtes et lorsque A =S ; on dit que G est un graphe complet.On appelle coloriage de G à k couleurs, k 2N ; toute application c : S 7!f1;::;kg (on suppose que l on disposede k couleurs di⁄Ørentes numØrotØes de 1 à k pour colorier les sommets du graphe et que c(s) donne le numØro dela couleur du sommet s): On dit que c est un coloriage propre si deux sommets reliØs par une arŒte n ont pas lamŒme couleur, c est- -dire si pour tous s et t dans S; c(s) =c(t) lorsque fs;tg2A:On notera P (k) le nombre de coloriage propres distincts à k couleurs de G et l’on appelera nombre ...
Publié le : jeudi 21 juillet 2011
Lecture(s) : 151
Nombre de pages : 5
Voir plus Voir moins
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
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.