PCSI2

N.Vron-LMB-jan 2014

Exercices-Chapitre 10: ensembles finis, dnombrement, sommes Elments de correction en ligne

Arithmtique et dnombrement:

1.1 Montrer que n, 23n+4 + 32n+1 est divisible par 19.

1.2 Calculer Sn = 3n

k 0

2k3

1.3 n dsigne un entier naturel. a. Dmontrer que les entiers ( n+5n+4) et (n+3n+2) sont divisible par (n+1). b. Dterminer les entiers naturels n tels que 3n+15n+19 est divisible par (n+1). c. Dterminer l'ensemble des entiers naturels n tels que (3n+15n+19) est divisible par (n+3n+2)

1.4 Soit n, n 2. On note n = im

ii 1

p la dcomposition de n en produits de facteurs premiers.

a. Soit d un diviseur de n, donner une criture de d en fonction des nombres premiers (pi)1im. b. Dterminer le nombre de diviseurs de n. c. Dmontrer que si un entier naturel non nul est un carr parfait alors le nombre de ses diviseurs positifs est impair. Etudier la rciproque

1.5 Rsoudre dans : a) x-y = 15 b) xy = 3x+2y c) x-y-4x-2y = 5.

1.6 Par combien de zros se termine lentier N = 2014 ! ?

1.7 Quel est le nombre dentiers naturels divisibles par 2,3,ou 5 compris entre 1 et 300 ?

1.8 Soit n, a. Montrer que le PGCD de 2n+4 et 3n+3 ne peut tre que 1, 2, 3 ou 6. b. Dterminer n tel que (2n+4)(3n+3) = 3

1.9 Rsoudre dans 2, lquation : PGCD(a, b) + PPCM(a, b) = a + b.

1.10 Soit a et b deux entiers avec b non nul. a. On note r le reste de la division euclidienne de a par b. Montrer que 2r 1 est le reste de la division euclidienne de 2a 1 par 2b 1. b. Montrer que : PGCD(2a 1, 2b 1) = 2PGCD(a, b) 1.

1.11 Soit p un nombre premier avec p 5. Montrer que p2 1 est divisible par 24.

1.12 Le petit thorme de Fermat Soit p un nombre premier.

a. Prouver que k1;p-1, p

k

est divisible par p.

b. Montrer par rcurrence sur n que n*, np - n est divisible par p.

c. Dterminer tous les entiers plP tels que p divise 2p+1.

1.13 Soit n*, on note a. Justifier laide dune proprit du cours le principe de Dirichlet ou principe des tiroirs : Si on range (n+1) paires chaussettes dans une commode contenant n tiroirs alors ou moins un tiroir contient deux paires de chaussettes. b. Montrer quil existe un multiple de 2014 qui ne scrit quavec les chiffres 0 et 1. On pourra utiliser la suite des repet-unit : un lentier qui scrit avec n chiffres 1. Par exemple u3 = 111.

PCSI2

N.Vron-LMB-jan 2014

Ensembles finis et dnombrement :

2.1 Soit E un ensemble fini de cardinal n, dmontrer que card(P(E)) = 2n par rcurrence sur n.

2.2 Soit E = 1,p et F = 1,n. a. Quel est le nombre dapplications de E dans F ? b. Quel est le nombre dapplications strictement croissantes de E dans F ? c. Soit f une application strictement croissante de E dans F. On dfinit g sur E par iE, g(i) = f(i) + i 1. Montrer que g est strictement croissante et prciser son ensemble darrive. d. Montrer que :f g met en bijection deux ensembles prciser. En dduire le nombre dapplications croissantes de E dans F.

2.3 Soit n*, F un ensemble fini de cardinal n+1 et E un ensemble fini de cardinal n. a. Dterminer le nombre de surjections de E sur {a,b}. b. Dterminer le nombre de surjections de F sur E. c. Quel est le nombre d'applications non surjectives de E dans E?

2.4 Soit E un ensemble et f une application de E dans E. f est idempotente si et seulement si ff = f. a. Donner un exemple d'application idempotente distincte de IdE. b. Montrer que si f est idempotente et si f est injective ou surjective alors f = IdE. c. Montrer l'quivalence: f est idempotente xf(E), f(x) = x d. On suppose E fini de cardinal n, dduire de ce qui prcde le nombre d'applications idempotentes de E dans E et calculer ce nombre pour n1,4.

2.5 Soit E un ensemble fini de cardinal n. a. Dnombrer les couples (A,B) de P(E) tels que AB. b. Dnombrer les couples (A,B) de P(E) tels que AB et BA.

2.6 Formule de Vandermonde. Soit k, n et m trois entiers naturels tels que k n+m. On considre A et B deux ensembles disjoints de cardinal respectif n et m, en dnombrant les parties de E = AB de cardinal k de

deux manires diffrentes, tablir que : k

i 0

n m n mi k i k

2.7 Obtenir par des mthodes combinatoires les rsultats suivants

a. n*, n

n 1

k 1

nk n2k

On pourra sintresser A ( E )

card(A)P

b. (p,q), q

k 0

p k p q 1p p 1

par une mthode combinatoire On pourra sintresser diffrentes faons de compter le nombre de parties (p+1) lments de 0, p+q

Savoir dnombrer

3.1 On dispose de six plaquettes portant les chiffres 1,2,3,6,8,9. a. On choisit 3 de ces six plaquettes et on fait la somme des nombres inscrits sur les plaquettes. Combien de sommes diffrentes peut-on obtenir ? b. On choisit successivement et sans remise 3 plaquettes que lon range de gauche droite pour former un nombre. Combien de nombres peut-on obtenir ? Combien dentre eux sont divisibles par 9 ? c. On recommence, cette fois-ci avec remise. Combien de nombres peut-on obtenir ? Combien dentre eux sont divisibles par 4 ?

3.2 Colle de math a. Combien existe-t-il danagrammes du mot MATH ?

PCSI2

N.Vron-LMB-jan 2014

b. Mme question avec le mot COLLOSCOPE. c. Dterminer le nombre de faon de former des groupes de colles dans une classe de 48. d. Dterminer le nombre de faon de subdiviser en n groupes p lments un ensemble np lments.

3.3 Le pouilleux : on rappelle quun jeu de 52 cartes contient 13 cartes de 4 couleurs diffrentes : pique, cur, carreaux et trfle, ainsi que 3 figures : roi, dame et valet chaque couleur. On appelle main une partie extraite du jeu. a. Dterminer le nombre de mains de 8 cartes. b. Combien de ces mains contiennent le valet de pique ? c. Combien de ces mains contiennent au moins un valet ? d. Combien de ces mains contiennent au moins un valet et un pique? e. Combien de ces mains contiennent exactement 3 piques dont le valet. f. Combien de ces mains contiennent exactement 3 piques et deux valets ?

3.4 Une urne contient des boules de deux couleurs : blanches et noires. On tire successivement 5 fois une boule, en remettant la boule tire aprs chaque tirage et on note les couleurs obtenues. a. Combien a-t-on de rsultats diffrents ? b. Combien de rsultats avec au moins deux boules de couleurs diffrentes ? c. Combien de rsultats avec deux boules blanches et 3 noires ? d. Combien de rsultats avec au plus deux boules noires ? e. Combien de rsultats avec une boule blanche en dernier ?

3.5 Nombre de solutions de x1+x2+...xp = n a. Dterminer le nombre de solution de l'quation x + y = n dans . b. Dterminer le nombre de solutions de lquation x + y +z = n dans 3. c. On dcide du codage suivant : le mot binaire 00100010 code lgalit 2+3+1 = 6 donnant une solution de x + y + z = 6 dans 3. Retrouver le rsultat de la question b. en utilisant cette reprsentation des solutions. d. Dterminer le nombre de solutions de x1+x2+...xp = n dans p e. Dterminer le nombre de solutions de x1+x2+...xp = n dans (*)p

3.6 Pour continuer avec des sommes a. Dterminer le nombre de solution de x1+x2+...xp = n dans Ep o E = {0,1} b. On note un le nombre de p-uplets de E = {1,2} de somme n avec p*. on a u4 = 5 car 1+1+1+1 = 4, 1+1+2 = 4, 1+2+1 = 4, 2+1+1 = 4 et 2+2 = 4 calculer u1, u2, u3 puis montrer que (un) est une SRL dordre 2 et expliciter un.

Exercices complmentaires

4.1 Dterminer le nombre de couples dentiers naturels (x, y), infrieurs ou gaux 30, tels que x + y soit un multiple de 3.

4.2 Montrer que, dans un ensemble fini on vide, il y a autant de parties de cardinal pair que de parties de cardinal impair.

4.3 Dans une classe de 30 lves, 12 tudient langlais, 15 tudient lallemand, 18 tudient lespagnol, 6 tudient langlais et lallemand, 7 lallemand et lespagnol, 8 lespagnol et langlais. Combien dlves tudient les trois langues ?

4.4 Soit E un ensemble fini n lments o n*. On considre A une partie de E p lments. a. Soit k * avec k n. Combien de parties de E k lments contiennent exactement un lment de A ? b. Soit k * avec k n. Combien de parties de E k lments contiennent au moins un lment de A ?

PCSI2

N.Vron-LMB-jan 2014

4.5 p-listes, p-arrangements ou p-combinaison ?

1. Quel est le nombre de codes possibles pour une carte bleue ? 2. Au loto, on tire au hasard 6 boules parmi 49. Combien de tirages diffrents peut-on obtenir ? 3. Au tierc, une course de chevaux comporte 20 partants. Combien peut-il y avoir de rsultats possibles de tiercs dans lordre ? 4. Un porte manteau comporte 5 patres. De combien de faons peut-on y accrocher 3 manteaux diffrents ? (avec au plus un manteau par patre). 5. Une urne contient 10 boules numrotes de 1 10. On en tire simultanment 3. Combien de tirages diffrents peut-on obtenir ? 6. Une urne contient 10 boules numrotes de 1 10. On en tire successivement 3 sans remise. Combien de tirages diffrents peut-on obtenir ? 7. Combien pices contient un jeu de dominos? 8.a. Quel est le nombre de faon de choisir 2 dlgus dans la classe de PCSI 3 ? 8.b. Quel est le nombre de faon de choisir 2 dlgus dans la classe de PCSI 3 si lon impose un garon et une fille ? 9. Quel est le nombre de plaques minralogiques possibles ? Une plaque minralogique est compose de 2 lettres 3 chiffres 2 lettres 10. Quel est le nombre de plaques minralogiques possibles dont tous les chiffres et les lettre sont deux deux distincts ? 11. Quel est le nombre danagrammes du mot PREPA ? 12. Combien de menus diffrents peut-on composer si on a le choix entre 3 entres, 2 plats et 4 desserts ? 13. Un QCM, autorisant une seule rponse par question, comprend 15 questions qui ont chacune 4 rponses possibles. De combien de faons peut-on rpondre ce questionnaire ?

4.6 Combien un village doit-il avoir dhabitants au minimum pour que deux personnes au moins aient les mmes initiales ? Rq. On ne prend pas en compte les noms ou les prnoms composs.

4.7 Soit n un entier naturel tel que n 3. Quel est le nombre de diagonales dun polygone convexe n cots ?

4.8 Soit E lensemble des nombres 6 chiffres ne comportant aucun 0 . a. Dterminer le cardinal de lensemble E. b. Soit E1 lensemble des nombres de E ayant six chiffres diffrents. Dterminer le cardinal de lensemble E1. c. Soit E2 lensemble des nombres pairs de E. Dterminer le cardinal de lensemble E2. d. Soit E3 lensemble des nombres de E dont les chiffres forment une suite strictement croissante (dans lordre o ils sont crits). Dterminer le cardinal de lensemble E3.

4.9 Combien y a t-il de dentiers dont lcriture dcimale comporte exactement n chiffres ( n 3) et comportant exactement deux chiffres 8 ?

4.10 On souhaite ranger sur une tagre 4 livres distincts de mathmatiques, 6 livres de physique et 3 de chimie. De combien de faons peut-on effectuer ce rangement : a. Si les livres doivent tre regroups par matire ? b. Si seuls les livres de maths doivent tre regroups ?

4.11 Quatre garons et deux filles sassoient sur un banc. a. Quel est le nombre de dispositions possibles ? b. Mme question si les garons sont dun ct et les filles de lautre. c. Mme question si chaque fille est intercale entre 2 garons. d. Mme question si les filles veulent rester lune ct de lautre.

4.12 On jette 51 miettes sur un table carre de 1m de ct. Montrer quil y a toujours au moins un triangle form par 3 miettes dont laire vaut au plus 200cm2.