Scribd Logo
Importer

Bienvenue sur Scribd !

  • 211 vues

    Exercices - Ensembles Finis Et Denombrement 34

    Transféré par

    SCRIBD CONTACT

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Exercices - Ensembles Finis Et Denombrement 34

    Transféré par

    SCRIBD CONTACT
    211 vues2 pages

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    211 vues2 pages

    Exercices - Ensembles Finis Et Denombrement 34

    Transféré par

    SCRIBD CONTACT

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 2

    c Christophe Bertault - MPSI Ensembles finis et dnombrement

    Exercice 1
    On tire simultanment 6 cartes dun jeu de tarot 21 atouts, la carte quon appelle
    l excuse , et 14 cartes par couleur, sachant quil y a 4 couleurs, comme toujours. On
    ne cherchera pas valuer numriquement les rsultats obtenus dans cet exercice, sauf si
    on aime se compliquer la vie. Combien de tirages dirents peut-on obtenir contenant :
    1) deux atouts et quatre tres ?
    2) six carreaux, ou bien trois carreaux, deux piques et lexcuse ?
    3) exactement un atout et au moins trois as ?
    4) au plus un cur et au moins quatre atouts ?
    Exercice 2
    On appellera mot toute suite de lettres, quelle ait un sens ou non. On rappelle que
    la lettre y est une voyelle.
    1) Combien de mots de 5 lettres peut-on former avec les 26 lettres de lalphabet, dans
    lesquels toute consonne est suivie dune voyelle et toute voyelle dune consonne ?
    2) Dterminer le cardinal de lensemble E des mots de 5 lettres forms partir des
    26 lettres de lalphabet et tels que :
    (i) la lettre q est forcment suivie de la lettre u ,
    (ii) toute consonne est suivie dune voyelle,
    (iii) toute voyelle est suivie dune consonne, une exception prs : les u
    qui sont conscutifs dun q sont suivis dune voyelle autre que u ,
    (iv) les deux dernires lettres ne peuvent pas tre qu .
    Exercice 3
    Soient A1, A2, . . . , An des ensembles. Prouver la formule du crible (ou formule de Poin-
    car) :

    n
    _
    i=1
    Ai

    =
    n

    k=1
    (1)
    k+1

    1i
    1
    <i
    2
    <...<i
    k
    n

    Ai
    1
    Ai
    2
    . . . Ai
    k

    .
    Quel formule retrouve-t-on dans le cas o les Ai, i 1, n, sont deux deux disjoints ?
    Exercice 4
    Soient n, p N

    tels que p n. Montrer, par un raisonnement combinatoire, que :


    _
    n
    p
    _
    =
    _
    n
    n p
    _
    et
    _
    n
    p 1
    _
    +
    _
    n
    p
    _
    =
    _
    n + 1
    p
    _
    .
    Exercice 5
    Soient n, p N

    . Combien existe-t-il dapplications strictement croissantes de 1, n dans


    1, p ?
    Exercice 6
    1) Soient E un ensemble ni de cardinal n et p, k N tels que 0 k p n.
    Calculer de deux faons le nombre de couples (A, B) P(E)
    2
    tels que A B,
    |A| = k et |B| = p.
    En dduire que
    _
    n
    k
    __
    n k
    p k
    _
    =
    _
    n
    p
    __
    p
    k
    _
    , puis que
    _
    n
    k
    __
    n k
    n p
    _
    =
    _
    n
    p
    __
    p
    k
    _
    .
    2) On note S lapplication de R
    N
    dans lui-mme qui, toute suite relle (xn)
    nN
    ,
    associe la suite (yn)
    nN
    dnie par : n N, yn =
    n

    k=0
    _
    n
    k
    _
    x
    k
    et T lap-
    plication de R
    N
    dans lui-mme qui, toute suite relle (x

    n
    )
    nN
    , associe la suite
    (y

    n
    )
    nN
    dnie par : n N, y

    n
    =
    n

    k=0
    (1)
    nk
    _
    n
    k
    _
    x

    k
    .
    Montrer que S et T sont deux bijections de R
    N
    dans R
    N
    inverses lune de lautre.
    Exercice 7
    1) On considre un ensemble ni E dont les lments sont de deux types nots 1 et
    2. Prcisment, E contient n1 lments de type 1 et n2 lments de type 2. Soit
    k 0, n1 +n2. Exprimer de deux faons le nombre de parties k lments de E
    que lon peut former. En dduire une jolie une formule.
    2) Simplier
    n

    k=0
    _
    n
    k
    _
    2
    pour tout n N.
    Exercice 8
    Soient n, p N. Pour tout k 1, n+1, dterminer le nombre de parties de 1, n+p+1
    de cardinal p + 1 et de maximum p +k. Simplier ainsi
    n

    k=0
    _
    p +k
    p
    _
    et
    n

    k=0
    _
    p +k
    k
    _
    .
    Exercice 9
    1) Soient G un groupe ni et x G.
    a) Montrer que x
    n
    = 1G pour un certain n N

    .
    b) On appelle ordre de x et on note o(x) le plus petit lment de lensemble
    _
    n N

    / x
    n
    = 1G
    _
    . Justier lexistence de o(x).
    c) Montrer que lensemble
    _
    1G, x, x
    2
    , . . . , x
    o(x)1
    _
    est un sous-groupe de G. On
    note
    _
    x
    _
    ce sous-groupe et on lappelle le sous-groupe de G engendr par x.
    2) Soit E un magma associatif ni. Montrer que E possde un idempotent, i.e. un
    lment x E pour lequel x
    2
    = x.
    Exercice 10
    Soit E un ensemble. On associe, toute partie A de E, lapplication lindicatrice de A
    A : E
    _
    0, 1
    _
    dnie par : x E, A(x) =
    _
    1 si x A
    0 si x / A.
    Montrer que lapplication A A est bijective de P(E) sur
    _
    0, 1
    _
    E
    . Retrouver ainsi,
    dans le cas o E est ni, un rsultat du cours.
    1
    c Christophe Bertault - MPSI Ensembles finis et dnombrement
    Exercice 11
    1) Soit n N

    . On range n +1 chaussettes dans n tiroirs. Montrer quau moins un


    tiroir contient deux chaussettes. Ce rsultat simple et essentiel est connu sous le
    nom de principe des tiroirs.
    2) a) Calculer

    3


    4
    puis tan

    12
    .
    b) Montrer qutant donns 13 rels, on peut toujours en trouver deux x et y
    pour lesquels 0 <
    x y
    1 +xy
    < 2

    3.
    3) a) Soient x R et n N

    . Pour tout k 0, n, on pose


    k
    = kxkx, lment
    de [0, 1[. Appliquer le principe des tiroirs aux rels
    k
    , k dcrivant 0, n, pour
    montrer le thorme dapproximation de Dirichlet suivant :
    (p, q) Z N

    / q n et

    x
    p
    q

    <
    1
    nq
    .
    b) En dduire que pour tout x R, lensemble des couples (p, q) Z N

    pour
    lesquels

    x
    p
    q

    <
    1
    q
    2
    est inni.
    c) Dmontrer le thorme de Bzout partir de la question a) : pour tous a, b Z
    premiers entre eux, il existe u, v Z tels que au +bv = 1.
    d) On admet lirrationnalit de , de sorte que sin n = 0 pour tout n N

    . La
    suite
    _
    1
    nsin n
    _
    nN

    possde-t-elle une limite, et si oui laquelle ?


    Exercice 12
    Soient p et q deux irrationnels strictement positifs tels que
    1
    p
    +
    1
    q
    = 1. On souhaite
    prouver le thorme de Beatty selon lequel les ensembles
    _
    np
    _
    nN

    et
    _
    nq
    _
    nN

    forment une partition de N

    , i.e. sont disjoints de runion N

    tout entier.
    On pose P =
    _
    np
    _
    nN

    et Q =
    _
    nq
    _
    nN

    .
    1) Montrer que les ensembles P et Q sont disjoints.
    2) En dduire que (P Q) [1, N] est de cardinal N 1 pour tout N N

    .
    3) Conclure.
    Exercice 13
    Soit n N

    . On pose G =
    _
    Sn/ k 1, n + 1, (n k + 1) = n (k) + 1
    _
    .
    1) Montrer que G est un sous-groupe de Sn.
    2) Calculer le cardinal de G.
    Exercice 14
    On se donne n entiers relatifs quelconques. Montrer que lon peut toujours former par
    somme, en choisissant certains dentre eux, un multiple de n.
    2

    Vous aimerez peut-être aussi