Raisonnement et ensembles — ENS

Exercices corrigés des ENS sur le thème « raisonnement et ensembles », regroupés par filière.

MP–MPI

Exercice 1. (★★★★) Injections et surjections ; Inégalité arithmético-géométrique ; Dénombrement double

Pour

{n\geq m}

, soient

{A}

l’ensemble des injections de

{\left\{1,\ldots,m\right\}}

dans

{\left\{1,\ldots,n\right\}}

{B}

l’ensemble des surjections dans le sens inverse.

Comparer ${|A|/n^m}$ et ${|B|/m^n}$ . On pourra compter les couples formés d’une partition ordonnée en ${m}$ blocs non vides et d’une partie à ${m}$ éléments rencontrant chaque bloc.

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Exercice 2. (★★) Cauchy-Schwarz ; Cardinal ; Applications

Soient

{S,T}

des ensembles finis non vides et

{f:S\to T}

. On pose

{X=\left\{(x,y)\in S^2:f(x)=f(y)\right\}}

Montrer que ${|X|\ge\max\left(\frac{|S|^2}{|T|}, \left\lfloor\frac{|S|}{|T|}\right\rfloor^2+|S| -\left\lfloor\frac{|S|}{|T|}\right\rfloor\right).}$

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Exercice 3. (★★★★) Cardinal ; Applications injectives ; Sommes et produits

Pour un alphabet fini

{X}

, on note

{X^\star}

l’ensemble des mots,

{c}

la concaténation et

{\ell}

la longueur. Soient

{\varphi:A^\star\to B^\star}

avec

{\varphi(c(a,a'))=c(\varphi(a),\varphi(a'))}

Question a) Pour

{A=\left\{a,b,c,d\right\}}

{B=\left\{0,1\right\}}

, étudier les codes

{(0,01,10,10011)}

{(01,10,11,00)}

, étendus par concaténation.

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Question b) Si

{\varphi}

est injective, montrer que

{\sum\limits_{a\in A}|B|^{-\ell(\varphi(a))}\le1}

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Exercice 4. (★★) Cauchy-Schwarz ; Cardinal ; Applications

Soient

{A}

un anneau et

{B\subset A}

fini non vide.

Poser ${E(B)=\#\left\{(a,b,c,d)\in B^4:ab=cd\right\}}$ et ${BB=\left\{ab:a,b\in B\right\}}$ .

Montrer que ${E(B)\ge|B|^4/|BB|}$ .

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Exercice 5. (★★★) Parties d'un ensemble ; Cardinal ; Extremums finis

Soit

{n\ge1}

{\mathcal E}

l’ensemble des pavés

{[a_1,b_1]\times\cdots\times[a_n,b_n]}

{\mathbb{R}^n}

. Pour une partie finie

{G}

, on pose

{f(G)=\left\{F\cap G:F\in\mathcal E\right\}}

Déterminer ${\sup\left\{k\in\mathbb{N}:\exists G,\ |G|=k,\ f(G)=\mathcal P(G)\right\}}$ .

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Exercice 6. (★★★★★) Récurrences linéaires ; Applications injectives ; Comparaison de croissances

Soit

{n\in\mathbb{N}^\star}

. Un chemin auto-évitant de longueur

{n}

{\mathbb{Z}^2}

est une suite injective de points

{a_0,\ldots,a_n}

{\mathbb{Z}^2}

telle que

{a_0=(0,0)}

et, pour tout

{i}

{\lVert a_{i+1}-a_i\rVert=1}

pour la norme euclidienne canonique de

{\mathbb{R}^2}

. On note

{A_n}

le nombre de ces chemins.

Question a) Montrer que

{A_{m+n}\le A_mA_n}

pour tous

{m,n\in\mathbb{N}^\star}

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Question b) Montrer qu’il existe

{\varepsilon>0}

tel que, pour

{n}

assez grand,

{(2+\varepsilon)^n\le A_n\le(3-\varepsilon)^n}

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Exercice 7. (★★★★★) Cardinal ; Récurrence ; Applications injectives

Un sous-ensemble non vide

{S}

{\mathbb{Z}}

est dit direct si, pour

{x,y,s,t\in S}

{x+y=s+t}

implique

{\left\{x,y\right\}=\left\{s,t\right\}}

Question a) Les ensembles

{\left\{1,3,6\right\}}

{\left\{1,3,6,10,15\right\}}

sont-ils directs ?

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Question b) Trouver un ensemble infini direct.

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Question c) Montrer qu’il existe

{A,B>0}

tels que pour tout

{n\ge1}

, tout ensemble direct

{S\subset[[0,n]]}

vérifie

{|S|\le Bn^{1/2}}

et qu’il existe un tel ensemble avec

{An^{1/3}\le|S|}

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Question d) Existe-t-il un ensemble direct

{S\subset\mathbb{N}}

tel que

{S+S=\mathbb{N}}

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Question e) Existe-t-il un ensemble direct

{S\subset\mathbb{Z}}

tel que

{\mathbb{N}\subset S+S}

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

Question f) Existe-t-il un ensemble direct

{S\subset\mathbb{Z}}

tel que

{S+S=\mathbb{Z}}

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

PC

Exercice 1. (★★★) Cardinal ; Récurrence ; Combinaisons

Soit

{A}

une partie de cardinal

{n}

{\mathbb{R}}

. On pose

{B=A+A=\left\{a+a':a,a'\in A\right\}}

Montrer que ${2n-1\le|B|\le n(n+1)/2}$ .

Généraliser à ${kA=A+\cdots+A}$ ( ${k}$ fois).

Cliquer ici pour voir (ou cacher) la réponse

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres

MP–MPI

PC

Retour aux planches par thème