Exercice N°113: Entiers naturels, dénombrement

MPSILyc´eeRabelias

Pr´et´opri,N´rseedercncerue

Entiersnaturels,de´nombrements

Exercice 1 :neitremo´eDeuqzertntuotruopn≥1,n(2n+ 1)(7n est divisible+ 1)
par 6.

Exercice 2 :Montrez que pour tout entiern≥2,

1+212+  +n12>2n3+n1
Exercice 3 :Montrez que∀n∈N⋆1! 3!  (2n+ 1)!≥(n+ 1)!n+1

Exercice 4 :uotruoettneirD´emontrezquepn≥tseetnav:eiarvriopprlauiest´´e1
Pour tout n-uplet(a1     an)x`aua1osruge´u´puseireeesled´r,

2n−1(a1×    ×an+ 1)≥(a1+ 1)×    ×(an+ 1)

Exercice 5 :te´eedtdescecierxe’ledtubeLbmelneesre’lmrniEdes applications
f:N→Nv´ent:rifia

pour tout entiern∈N f◦f(n)< f(n+ 1)

1. Soitf∈Etnome´D.rezquepourtoutenitrep∈N, lademi-droiteDp={k∈
N|k≥p}est stable parfuqeider`--ae’tsc,f(Dp)⊂ Dp.
2.De´duisez-enquefest strictement croissante et que pour tout entiern∈N,
f(n)< n+ 1.
3. Concluez.

Exercice 6 :
1D´montrezenutilisantunere´currencefortequetoutentiern∈N⋆e´rc’stied
. e
mani`ereuniquesouslaformen= 2p(2qo`u(,)1+p q)∈N2.
2.End´eduirequeN≃N2.
3.Conside´rezlaprojectionp:N2→N ? ! ? Injective. Est-elle surjective

Dtnemone´erbm

Exercice 7 :SoientEun ensemble de cardinaln,A B∈P(E) deux parties deE.
1.Decombiendefa¸consdiffe´rentespeut-onchoisirlecouple(A B) ?
2. Combien existe-t-il de couples (A B) tels queA∩B=∅?
3. Combien existe-t-il de couples (A B) tels queA∪B=E?

1

Semainedu12aoˆut2011

4. Combien existe-t-il de couples (A B) tels queA∩B=∅etA∪B=E?

Exercice 8 :Soit (n p)∈N⋆×N⋆. On noteSnple nombre de surjections deFn
surFp.
1.D´eterminezSnplorsque
–n≤p
– lorsquep= 1 etn∈N⋆
2. Pourk∈Fp, on noteAk={f:Fn→Fp|fest surjective, etf(1) =k}.
De´montrezqueCard(Ak) =Sn−1p+Sn−1p−1enquete´ddeiues-z

Snp=p[Sn−1p+Sn−1p−1]

3.De´duisez-enfinalementlaformule:
p
p=X(−k
Skn=0−1)ppkkn

Exercice 9 :Soit (n p)∈N⋆×N
1. Quel est le nombre de suites depentiers compris entre 1 etn?
2. Quel est le nombre de suites strictement croissantes depentiers compris entre
1 etn?
3. Quel est le nombre de suites croissantes depentiers compris entre 1 etn?

Exercice 10 :Soit (n p)∈N2nc.Osionoenrtdi`u’a´eeql

x1+x2+  +xn=p

De´terminezlenombredesolutionsdecettee´quation,
1. dans{0; 1}n
,
2. dans (N⋆)n
Indication :drelssloendza’obd´eterminioatedsnoituuqe´ni’lx1+x2+  +
xn≤protcsaisedntn-’eiusetsettcirnemeuesochaqonunlutianssetna`coai
tiers entre 1 etp.
3. dansNn.

icffieocseibudstneeomnˆPropri´et´esd
Exercice 11 :Soit (n p)∈N2E.atsez`blisa
de´nombrement,lesformulessuivantes:
1.pn=n−pn
2.np+1+1=np+pn+ 1
3.nkX=0nk= 2n.

l’aide

d’un

raisonnement

de

Exercice 12 : Formule de Van der Monde
Soientn n1 n2nemorbmene,tneonisrad´dentme’lA.slernu’dediasentdenatuiers
e´tablissezlaformulesuivante:
X
n1n+n2=nk=0kn1nn−2k

Exercice 13 :Soientp k ntrois entiers naturels tels que 0≤p≤k≤n´Dme.tronez
que
nkp=npnn−−pk
k
End´eduire
kX nn−pnnk
X

S1=0p−k; etS2=k=p(−1)n−kk p 
n
p=

Calcul de sommes
Exercice 14 :SoitEun ensemble fini de cardinaln∈N⋆. Notons
•S1=XCardX
X∈P(E)
•S2=XCard(X∩Y)
(XY)∈P(E)2
•S3=XCard(X∪Y)
(XY)∈P(E)2
1. Montrez queS1=n2n−1.
2. Montrez queS2=n22n−2.
3. Etablissez la relationS2+S3= 2n+1S1´D.z-seuiedequenS3= 3n22n−2.
Exercice 15 :enortzeuq´DmeX Xi= 2n−2n(n+ 1)
A⊂Fni∈A

2

Analyse combinatoire
Exercice 16 :Le Poker se joue avec un jeu de 32 cartes, on distribue a chaque
`
joueur unemainde cinq cartes.
1.D´enombrezlenombredemainspossibles.
2.De´nombrezlenombredemainsquicontiennent:
(a)uncarr´ed’as(4as).
(b)uncarre´(4cartesdemeˆmehauteur).
(c)unfull(3cartesdemˆemehauteuret2autrescartesdemeˆmehauteur).
(d)unbrelan(3cartesdemeˆmehauteursansfullnicarr´e)
(e)unequinteflush(5cartesdehauteurconse´cutivesetdemeˆmecouleur).
(f)unecouleur(5cartesdelameˆmecouleursansquinteflush).
(g) exactement deux rois et trois coeurs.

Exercice 17 :eLhecsejoujeud’´echcqiiureserunue´t8seloco8ldeneigsennseL.
tourspeuventprendretoutepi`ecesitu´eedansleurligneouleurcolonne.
1.Decombiendefa¸conspeut-onplacer8toursidentiques,desortequ’aucune
d’entreellesnesoitmenace´eparlesautres.
2.Decombiendefac¸onspeut-onplacerktours identiques,k∈ {1    8}de
sortequ’aucuned’entreellesnesoitmenac´eeparlesautres?

Correction des exercices

Exercice 1 .—onfavaeuirr´neercnceru.e..
•isattialionIineuorsqLn= 1, on a 1×3×8 = 4×6 est divisible par 6.
•´edit´eH´ersoitn≥0 tel queun=n(2n+ 1)(7n est divisible par 6. Il+ 1)
existe doncN∈Ntel queun= 6N. Montrons queun+1est divisible par 6 :

un+1= (n+ 1)(2n+ 3)(7n+ 8) = [n+ 1][(2n+ 1) + 2][(7n+ 1) + 7]
=n(2n+ 1)(7n+ 1) + 42n2+ 60n+ 24
= 6×[N+ 7n2+ 10n+ 4]

⋆
•clonCniousruer´rcenomacn,e´equontrrtouepountteriearpn∈N,
n(2n+ 1)(7n est divisible par 6.+ 1)N

Exercice 2 .—rpueevesaLceenrrcu´errpara:
•noitasilaitinIlorsquen= 2, on a 1 +41=45Or45>56⇐⇒
lapropri´et´tv´erifi´eepourn= 2.
e es
•´ited´re´Hitn≥2 tel que
eso
1+212+  +n123n
>2n+ 1

•

25>24. Donc

On a alors
1 12+  +n12 3 1+ (n1
+2n+ 1)2>2n+1(+n+ 1)2
3n3+ 6n2+ 5n+ 1
>(2n+ 1)2(n+ 1)2
Onve´rifiealorsque3(n23n1+6+n)22+(n5+n+1)21≥32nn,+3+.3nEffete

3n3+ 6n2+ 5n 3+ 1n+ 3
−
(2n+ 1)2(n+ 1)22n+ 3

6n4+ 21n3+ 28n2+ 17n+ 3
=
(2n+ 1)(2n+ 3)(n+ 1)2
6n4+ 21n3+ 27n2+ 15n+ 3
−
(2n+ 1)(2n+ 3)(n+ 1)2
n(n+ 2)
=
(2n+ 1)(2n+ 3)(n+ 1)2
≥0

Partransitivit´edelarelationd’ordre,ils’ensuitque

Conclusion
1

1 1 1 + (n+1)12>23nn3++3
+22+  +n2

parr´ntr´equetoutentiern
ecurrence, on a mo pour
1 3n

≥

2,

3

Exercice 3 .—Pra´rceruercn.e

•Init.pourn= 1, on a 1!3! = 64 =≥22.

•

He´r.Soitn∈N⋆tel que 1! 3!  (2n+ 1)!≥(n+ 1)!n+1. Alors

1! 3!  (2n+ 1)! (2n+ 3)!≥(n+ 1)!n+1×(2n+ 3)!
≥(nn+2)!+2n+1(2n+ 3)!
×
2n+3
n+2Yk
n+k=n+3
≥(n+ 2)!1×k=Y1k×(n+ 2)n+1
2n+3
Y(n+ 2)
k=n+3
≥(n+ 2)!n+2×(n+ 2)n+1
≥(n+ 2)!n+2

•Ccl.Pruce´rranomae´rtcnerno,e∀n∈N⋆1! 3!  (2n+ 1)!≥(n+ 1)!n+1
N

Exercice 4 .—srqe´olOncfiire´vrapecnemmoeti´prroepttceern= 2. Il s’agit de
montrer que pour tout couple (a b)∈R2erieursou´egauxa`,1noaredlee´puss
´

2(ab+ 1)≥(a+ 1)(b+ 1)

.Raisonnonspar´equivalences,ona:

2(ab+ 1)≥(a+ 1)(b+ 1)⇐⇒ab−a−b+ 1≥0⇐⇒(a−1)(b−1)≥0

Commeaetbte.satisfaieetsibnee´agil´tsoinre`enieredttce1a`srueire´pustn

Apr´esentmontronslapropri´ete´parre´currence.

•Hr´´e.edSoitn≥un entier tel que pour tout1 nles´r´erbseenomletd-up
(a1    