[PDF] [PDF] TD2 Mercredi 26 septembre Mathématiques discrètes Exercice 0 : 1

View - Download [PDF] TD2 Mercredi 26 septembre Mathématiques discrètes Exercice 0 : 1

Previous PDF

Next PDF

L3 - 2018/2019 - TD2 Mercredi 26 septembre Mathématiques discrètes

Exercice 0:

1. Soit EetFdeux ensembles dénombrables. Démontrer queE[Fest dénombrable.Solution: Soitf(resp.g) une injection deE(resp.F) dansN. La fonction suivante est injective :

E[F7!N

x!2f(x)six2E

2g(x) + 1six2FnE

2. Soit E1;:::;Endes ensembles dénombrables. Démontrer queQn i=1Eiest dénombrable.Solution: Soitfil"injection deEidansN. La fonctionfsuivante est injective : Q n i=1Ei7!Nn x!(fi(x))1in

EtNnest dénombrable.Raisonnement combinatoire

Exercice 1:

Démontrer par des arguments combinatoires l"identité :

8n2N;3n

3 = 3n 3 + 6nn 2 +n3Solution: On compte le nombre de parties à trois éléments dans un ensemble contenant3néléments, dontnsont coloriés en rouge,nsont coloriés en bleu etnsont coloriés en vert.

On distingue alors les cas : les trois éléments sont de la même couleur, deux éléments sont

de la même couleur et le troisième d"une couleur différente, et les trois éléments sont de

couleurs différentes.Des applications du lemme des tiroirs

Exercice 2:

On a coloré des arcs sur un cercle de diamètre1. La somme des longueurs des arcs colorés est< =2. Démontrer qu"il existe un diamètre du cercle dont les deux extrémités ne sont pas colorées.Solution: On colore aussi les arcs symétriques des arcs colorés sur le cercle. La longueur des arcs

colorés est alors2fois la longueur initialement colorée, donc< . Le diamètre d"extrémité

un point non coloré convient.

Exercice 3:

Soitn+ 1nombresm1;:::;mn+1choisis parmi les nombres entiers naturels1;2;:::;2n. Montrer qu"il existei;j,1i6=jn+ 1tels quemidivisemj.S. Le Roux, A. Lick, A. Mansutti 1 E.N.S. Cachan L3 - 2018/2019 - TD2 Mercredi 26 septembre Mathématiques discrètes

Solution:

On décompose chaque entiermisous la forme2kiqi, avecqiun entier impair compris entre

1et2n1. Il y anentiers impairs entre1et2n, donc par le principe des tiroirs, il existe

i6=jtels queqi=qj. Alorsmidivisemjoumiest un multiple demj.Dénombrabilité (ou non).

Exercice 4:

Montrer que l"ensemble des parties finies deNest dénombrable.Solution: C"est une union dénombrable d"ensembles finis (réunion croissante desP(f0;:::;ng)).

Exercice 5:

Montrer que l"ensemble des nombres décimaux est dénombrable.Solution: C"est une union dénombrable d"ensembles finis (partitionner selon la partie entière, puis le nombre de décimales).

Exercice 6:

Soitun alphabet fini.

1. Démon trerque l"ensem bledes arbres finis sur est dénombrable.Solution: C"est une union dénombrable d"ensembles finis (partitionner selon la taille des arbres). 2. Démon trerque 1n"est pas dénombrable (sauf siest un singleton).Solution: Argument diagonal : Par l"absurde, Soita;bdeux lettres différentes dans. Si on a énuméré les motswi; i2N, avecwi= (wi(j))j2N, le motvdéfini parv(i) =a, si w i(i) =b,v(i) =bsinon, n"est pas dans l"énumération.

Exercice 7:

Démontrer que l"ensemble des suites à valeurs dansf0;1gn"est pas dénombrable.Solution: Argument diagonal : Par l"absurde, si on a énuméré les suites à valeurs dansf0;1g: U i; i2N, avecUi= (Ui(j))j2N, alors la suiteVdéfinie parV(i) = 1Ui(i), pour tout entier natureli, n"est pas dans l"énumération.

Exercice 8:

Donner un exemple d"une famille non dénombrable de parties deNdont les intersections2 à2sont finies.S. Le Roux, A. Lick, A. Mansutti 2 E.N.S. Cachan L3 - 2018/2019 - TD2 Mercredi 26 septembre Mathématiques discrètes

Solution:

D"après l"exercice précédent, l"ensemble des suites à valeurs dansf1;2gn"est pas dénom-

brable. À une telle suiteu= (ui)i2N, on associe l"ensembleIu=funun1u0jn2Ng (unun1u0désigne l"entier naturel dont l"écriture en base10estunun1u0). Alors la familleIu,uparcourant l"ensemble des suites à valeurs dansf1;2gconvient.

Exercice 9:

En utilisant le théorème de Cantor Bernstein, démontrer queNNetRsont équipotents.Solution:

Par double inclusion. On inclutNNdansRen envoyant la suite(ui)i2Nsur le nombre réel :

0;011|{z}

u

0011|{z}

u

1011|{z}

u 20 On inclutRdansNNen envoyant le nombre réelxde développement décimal sg(x)(bjxjc;x1x2x3)sur la suite : (sg(x) + 1;bjxjc;x1;x2;x3;)

Exercice 10 (L"arbre de Stern-Brocot) :

On cherche à représenter les nombres rationnels strictement positifs en les introduisant sous la forme d"un arbre de façon récursive. On part de deux motifs0=1(qui représente0) et1=0(qui représente l"infini). A chaque étape, on insère entre deux fractions consécutivesm=netm0=n0la fraction (m+m0)=(n+n0).

Ainsi, on on obtient après quatre étapes :

1) initialisati on: [01 ;10 2)[01 ;11 ;10 3)[01 ;12 ;11 ;21 ;10 4)[01 ;13 ;12 ;23 ;11 ;32 ;21 ;31 ;10 5)[01 ;14 ;13 ;25 12 ;35 ;23 ;34 ;11 ;43 ;32 ;53 ;21 ;52 ;31 ;41 ;10 1. Vérifier que p ourm=n < m0=n0, on am=n <(m+m0)=(n+n0)< m0=n0.Solution: (m+m0)=(n+n0)m=n= (m0nmn0)=n(n+n0) =n0(m0=n0m=n)=(n+n0)>0 et un calcul similaire pour l"autre inégalité. 2. Démon trerque à c haqueétap ep ourdeux fractions consécutiv esm=n < m0=n0, on a n

0mm0n=1.Solution:

Par récurrence : C"est vrai à la première étape etn(m+m0)(n+n0)m= (nm0mn0) etn0(m+m0)(n+n0)m0= (n0mm0n). 3.

En déd uireque les fractions con struitespar c epro cédéson tsous forme irréductible (i.e.

le numérateur et le dénominateur sont premiers entre eux).S. Le Roux, A. Lick, A. Mansutti 3 E.N.S. Cachan

L3 - 2018/2019 - TD2 Mercredi 26 septembre Mathématiques discrètes

Solution:

On obtient ainsi une relation de Bezout entre le numérateur et le dénominateur, ils sont donc premiers entre eux. 4. Soit p=qun rationnel strictement positif représenté par une fraction irréductible. On suppose que mn 0. Démontrer quem+m0+n+n0p+q.Solution:

On a :pnqm1etm0qn0p1(entiers>0). Donc

m+m0+n+n0(m+n)(m0qn0p) + (m0+n0)(pnqm) =p(n(m0+n0)n0(m+n)) +q(m0(m+n)m(m0+n0)) =p(nm0n0m)|{z}

1+q(m0nmn0)|{z}

1 =p+q 5. Soit p=qun rationnel strictement positif représenté par une fraction irréductible. Dé- montrer qu"elle apparait de façon unique dans la construction.Solution:

On fait une récurrence surp+q.

Sip+q= 2,p= 1etq= 1et1=1est apparu à la première étape.

Au début,

01 0, alors il y a trois possibilités : mn 0, mais alorsm+m0+n+n0< m+m0+m0+n+n0+n0p+q.

Sinon,m+m0n+n0=pq

La suite des encadrements stricts produit une suite strictement croissantep+q, donc le processus s"arrête sur un cas d"égalité. De plus, ceci ne peut se produire qu"une seule fois car la suite produite à chaque étape est strictement croissante. 6.

En déduire que Q+est dénombrable.Solution:

On obtient ainsiQ+comme une réunion surNd"ensembles finis.

Exercice 11 :

Une autre méthode pour démontrer que[0;1]est non dénombrable. Soitfxngn2Nune suite de nombre réels dans[0;1]. 1. Construire par r écurrenceune suite d" intervallesfermés Inde mesure>0tels que :

I0[0;1],

InIn1,

Inest un intervalle fermé de mesure>0qui ne contient pasxn.S. Le Roux, A. Lick, A. Mansutti 4 E.N.S. Cachan

L3 - 2018/2019 - TD2 Mercredi 26 septembre Mathématiques discrètes

Solution:

On construit la suite d"intervalles par récurrence de la façon suivante :

I1= [0;1].

Pourn0avecIn1= [an1;bn1],

I n=8 :I n1sixn=2In1 [xn+bn12 ;bn1]sixn2[an1;bn1[ [an1;an1+bn12 ]sixn=bn1 2. En déduire que [0;1]n"est pas dénombrable.Solution: On a ainsi construit une suite d"intervalles emboités. Par le théorème des segments emboités,\nInest un fermé non vide dans[0;1]. Par construction,\nInne contient aucun des éléments de la suitefxngn2N. Il n"est donc pas possible d"énumérer[0;1].

Exercice 12 (Ensemble de Cantor) :

SoitI= [a;b]un intervalle de mesure=ba. On définit(I) = [a;a+3 ][[b3 ;b]. L"applicationdécoupe l"intervalleIen trois intervalles fermés de mesures égales et retire celui du milieu. On étendaux réunions finies d"intervalles fermés disjoints en faisant agir sur chacun des intervalles. On définit l"ensemble de Cantor commeC=\nFn, oùFnest défini par récurrence surn comme : F

0= [0;1]etFn=(Fn1)

1. Démon trerque Cest un fermé non vide de mesure nulle.Solution: ChaqueFnest par construction un fermé contenu dansFn1. Par le théorème des fermés emboités,Cest un fermé non vide. De plus, par construction, on a(Fn) = 23
(Fn1), donc(C)(23 )npour toutn2N. Donc par passage à la limite,(C) = 0. 2. Soit n2N. Démontrer queFnest la réunion de2nintervalles[2n i=1[ai;bi], la suite a

0;a1;:::;a2nreprésente la suite ordonnée des éléments de la formeP

n i=1xi3i3 n, avec x i2 f0;2g(éléments de[0;1]dont le développement en base3a au plusnchiffres et ne comporte que des0et des2) etbi=ai+13 n.Solution:

On le démontre par récurrence surn.

C"est vrai pourF0= [0;1]en posanta0= 0etb0= 1 =a0+13 0.

Supposons queFn=t2n

i=1[ai;bi]aveca0;a1;:::;a2nune suite ordonnée des éléments de la formeP n j=1xj3j3 netbi=ai+13 n, pour touti. AlorsFn+1=(Fn) =t2n i=1([ai;bi]).

Par définition,([ai;bi]) = [ai;ai+13

n+1][[bi13 n+1;bi].

Posonsc2i=ai,d2i=ai+13

n+1,c2i+1=bi13 n+1,d2i+1=bi, de façon à avoir F n+1= [c2i;d2i][[c2i+1;d2i+1]avecc2i< d2i< c2i+1< d2i+1.

De plus :

c2i=ai=P n j=1xj3j3 n=P n j=1xj3j+13 n+1, d2i=ai+13 n+1=c2i+13 n+1,S. Le Roux, A. Lick, A. Mansutti 5 E.N.S. Cachan L3 - 2018/2019 - TD2 Mercredi 26 septembre Mathématiques discrètes c2i+1=bi13 n+1=ai+13 n13 n+1=c2i+23 n+1=2+Pn j=1xj3j+13 n+1, d2i+1=bi=c2i+1+13 n+1. 3. En déduire que Cest l"ensemble des éléments de[0;1]dont le développement en base

3ne comporte que des0et des2.Solution:

Les éléments de l"intervalle[ai;bi]avecai=P

n j=1xj3j3 netbi=ai+13 nsont exactement les éléments dont le développement triadiqueP1 j=1y j3 jvérifiey1=x1;:::;yn=xn. 4. Décrire une biject ionde Csur[0;1], en utilisant la description précédente.Solution:

La bijection est :

C7![0;1]

1X j=1y j3 j!1X j=1y j=22 j Autrement dit, à un nombre dont un développement triadique ne comporte que des0 et des2on fait correspondre un nombre défini par "son" développement dyadique en gardant les0et en remplaçant les2du développement triadique par des1. 5. En déduire que Cn"est pas dénombrable.Solution: Cest en bijection avec[0;1].S. Le Roux, A. Lick, A. Mansutti 6 E.N.S. Cachanquotesdbs_dbs28.pdfusesText_34

[PDF] comment savoir si une fonction est bijective

[PDF] montrer qu'une fonction est injective

[PDF] bijection réciproque exercices corrigés

[PDF] montrer que f réalise une bijection

[PDF] baguier virtuel sans imprimer

[PDF] baguier gratuit

[PDF] controle francais 4eme poesie lyrique

[PDF] évaluation français entrée 4ème collège

[PDF] bilan exemple

[PDF] bilan définition

[PDF] le bilan comptable cours

[PDF] bilan ulis

[PDF] rapport d'activité ulis

[PDF] comment rédiger un bilan pédagogique

[PDF] rapport d'activité ulis collège