Retrouver aussi cette fiche sur www maths-france Quelle est la probabilité pn pour que dans un groupe de n personnes choisies au hasard, deux personnes
| Previous PDF | Next PDF |
[PDF] Probabilité et dénombrement - Exo7 - Exercices de mathématiques
Exo7 Probabilité et dénombrement ; indépendance Exercice 1 Une entreprise décide de classer 20 personnes susceptibles d'être embauchées; leurs CV
[PDF] Dénombrement - Exo7 - Exercices de mathématiques
Exercice 5 On considère les mains de 5 cartes que l'on peut extraire d'un jeu de 52 cartes 1 Combien y a-t-il de mains différentes? 2 Combien y a-t-il de
[PDF] Dénombrements - Exo7 - Exercices de mathématiques
Retrouver aussi cette fiche sur www maths-france Quelle est la probabilité pn pour que dans un groupe de n personnes choisies au hasard, deux personnes
[PDF] Dénombrement et (équi)-probabilité
TD Probabilités feuille n◦ 3 Dénombrement et (équi)-probabilité Exercice 1 Pour accéder `a un service sur Internet, vous devez taper un mot de passe de 4
[PDF] Dénombrement
A = Ω est l'événement certain A = { 7 } est un événement impossible Page 10 STAT03 : probabilités COURS Décembre 2000 Cycles Préparatoires du Service
[PDF] Cours de probabilités et statistiques
A Cardinaux et dénombrement 57 pour que l'OL soit championne de France? Un rappel des techniques de dénombrement est disponible `a l'annexe A
[PDF] PROBABILITES – EXERCICES CORRIGES - Math2Cool
M CUAZ, http://mathscyr free Page 1/16 3) Déterminer la probabilité de l' événement D "La carte choisie n'est ni un pique ni une figure" Exercice n°5 On jette Le tableau suivant permet de dénombrer les différentes catégories : Cravate
[PDF] Analyse combinatoire et probabilités - Exercices et corrigés - Free
2 jan 2016 · 2 1 Analyse combinatoire (dénombrement) 2 2 32 Exercice M-Dans une autre classe, la probabilité que l'on reçoive 2 Fr pour chaque boule noire tirée et que l'on perde 1 Fr pour chaque boule blanche tirée
[PDF] Cours dIntroduction au Calcul des Probabilités
probabilités : la loi des grands nombres et la convergence vers une loi gaussi- http://math univ-lille1 fr/~suquet/ vii Dénombrement de sommes d'entiers
[PDF] Chapitre 1 Définition et méthodologie de l 'analyse comparative
[PDF] Bouchard, Durkheim et la méthode comparative positive - Érudit
[PDF] Analyse complexe - Département de mathématiques et de statistique
[PDF] Analyse complexe - Département de mathématiques et de statistique
[PDF] Analyse complexe - Département de mathématiques et de statistique
[PDF] Analyse Complexe 2005-2006 - Exo7
[PDF] Analyse complexe Cours de L3, ENS Lyon, automne 2014
[PDF] Analyse Complexe S´eries de Fourier
[PDF] Analyse Complexe - Institut de Recherche Mathématique Avancée
[PDF] ANALYSE COMPLEXE 3M266
[PDF] L 'Analyse appliquée du comportement
[PDF] L 'Analyse appliquée du comportement
[PDF] l 'analyse concurrentielle - cloudfrontnet
[PDF] CONVAINCRE OU LA CONQUETE DE LA LIBERTE
Exo7
Dénombrements
* très facile ** facile *** difficulté moyenne **** difficile ***** très difficile I : Incontournable T : pour travailler et mémoriser le cours Exercice 1IT1.(***) Trouverunedémonstrationcombinatoiredel"identitéqu"un ensemble ànéléments contient autant de parties de cardinal pair que de parties de cardinal impair.
2. (****) T rouverune démonstration combinatoire de l"identité kCkn=nCk1n1. 3. (****) T rouverune démonstration combinatoire de l"identité Cn2n=ånk=0(Ckn)2.ensemble àpqéléments et siA1,...,Apsontpparties deE,A1,...,Apforment une partition deEsi et seulement
si tout élément deEest dans une et une seule des partiesAi. Il revient au même de dire que la réunion desAi
estEet que lesAisont deux à deux disjoints.) x1+x2+:::+xn=k(kentier naturel donné) estCkn+k1. (Noteran;kle nombre de solutions et procéder par
récurrence.)aient le même anniversaire (on considèrera que l"année a toujours 365 jours, tous équiprobables). Montrer que
pourn>23, on apn>12On part du point de coordonnées(0;0)pour rejoindre le point de coordonnées(p;q)(petqentiers naturels
donnés) en se déplaçant à chaque étape d"une unité vers la droite ou vers le haut. Combien y a-t-il de chemins
possibles ?Montrer la formule du crible :
card(A1[:::[An) =nå i=1card(Ai)å16i1 +:::+(1)k1å 16i1 +:::+(1)n1card(A1\:::\An): 2. Combien ya-t-ildepermutationssdef1;:::;ngvérifiant8i2f1;:::;ng;s(i)6=i?(Cespermutationssont appelées dérangements (permutations sans point fixe)). Indication : noterAil"ensemble des permutations
qui fixentiet utiliser 1). On peut alors résoudre un célèbre problème de probabilité, le problème des chapeaux.npersonnes
laissent leur chapeau à un vestiaire. En repartant, chaque personne reprend un chapeau au hasard. Montrer que la probabilité qu"aucune de ces personnes n"ait repris son propre chapeau est environ 1e quandnest grand. distincts des sommets se coupent-elles au maximum ? concourantes. Déterminer le nombreP(n)de régions délimitées par ces droites. 2. On donne nplans de l"espace. On suppose qu"il n"en existe pas deux qui soient parallèles, ni trois qui
soient concourants en une droite, ni quatre qui soient concourants en un point. Déterminer le nombre
Q(n)de régions délimitées par ces plans.
2 SoitPknle nombre de partitions d"un ensemble ànéléments enkclasses. Montrer quePkn=Pk1n1+kPkn1pour 26k6n1.
Dresser un tableau pour 16k;n65.
Calculer en fonction dePknle nombre de surjections d"un ensemble ànéléments sur un ensemble àpéléments.
Indication pourl"exer cice7 NCoder un chemin par un mot :Dpour droite,Hpour haut.4 Correction del"exer cice1 N1.Soit Eunensembleànéléments,n>1, etaunélémentfixédeE. Soitf:P(E)!P(E)
A7!Anfagsia2A
A[fagsia=2A.
Montrons quefest involutive (et donc bijective). SoitAun élément deP(E). Sia=2A,f(A) =A[faget donc, puisquea2A[fag,f(f(A)) = (A[fag)nfag=A. Sia2A,f(A) =Anfagetf(f(A)) = (Anfag)[fag=A.
Ainsi,8A2P(E);ff(A) =Aou encore,ff=IdP(E).
Maintenant clairement, en notantPp(E)(resp.Pi(E)) l"ensemble des parties deEde cardinal pair (resp. impair),f(Pp(E))Pi(E)etf(Pi(E))Pp(E). Donc, puisquefest bijective card(Pp(E)) =card(f(Pp(E))6cardPi(E) et de même card(Pi(E))6cardPp(E). Finalement, card(Pi(E)) =cardPp(E). 2. Soient E=fa1;:::;angun ensemble ànéléments etaun élément fixé deE. Soitk2 f1;:::;n1g.
Il y aCk1n1parties àkéléments qui contiennenta. Donc,nCk1n1(=Ck1n1+:::+Ck1n1)est donc la somme
du nombre de parties àkéléments qui contiennenta1et du nombre de parties àkéléments qui contiennent
a 2... et du nombre de parties àkéléments qui contiennentan.
Dans cette dernière somme, chaque partie àkéléments deEa été comptée plusieurs fois et toutes les
parties àkéléments (en nombre égal àCkn) ont été comptés un même nombre de fois. Combien de fois a
été comptéefa1;a2:::akg? Cette partie a été comptée une fois en tant que partie contenanta1, une fois
en tant que partie contenanta2... et une fois comme partie contenantaket donc a été comptéekfois.
Conclusion :kCkn=nCk1n1.
3. Soit E=fa1;:::;an;b1;:::;bngun ensemble à 2néléments. Il y aCn2nparties ànéléments deE. Une telle
partie akéléments dansfa1;:::;angetnkdansfb1;:::;bngpour un certainkdef0;:::;ng. Il y aCknchoix possibles dekéléments dansfa1;:::;angetCnknchoix possibles denkéléments dansfb1;:::;bng
pourkdonné dansf0;:::;nget quandkvarie de 0 àn, on obtient : C n2n=nå k=0CknCnkn=nå k=0(Ckn)2:Correction del"exer cice2 NIlyaCqpqchoixpossiblesd"unepremièreclasse. Cettepremièreclasseétantchoisie, ilyaCq
pqq=Cq (p1)qchoix possibles de la deuxième classe... etCqqchoix possibles de lap-ième classe. Au total, il y aCqpqCq
(p1)q:::Cqq choix possibles d"une première classe, puis d"une deuxième ...puis d"unep-ième. Maintenant dans le nombreCqpqCq
(p1)q:::Cqq, on a compté plusieurs fois chaque partition, chacune ayant été compté un nombre égal de fois. On a compté chaque partition autant de fois qu"il y a de permutations despclasses à savoirp!. Le nombre
cherché est donc : 1p!CqpqCq
(p1)q:::Cqq=1p!(pq)!q!((p1)q)!((p1)q)!q!((p2)q)!:::(2q)!q!q!q!q!0!=(pq)!p!(q!)p:Correction del"exer cice3 NClairement,8n2N;an;0=1 (unique solution : 0+0+:::+0=0) et8k2N;a1;k=1 (unique solution :k=k).
5 Soientn>1 etk>0 fixés.an+1;kest le nombre de solutions en nombre entiers positifsxide l"équation
x 1+:::+xn+xn+1=k. Il y aan;ksolutions telles quexn+1=0 puisan;k1solutions telles quexn+1=1 ... puis
a n;0solutions telles quexn+1=k. Donc,8n2N;8k2N;an+1;k=an;k+an;k1+:::+an;0(et on rappellean;0=a1;k=1). Montrons alors par récurrence surn, entier naturel non nul, que :8n2N;8k2N;an;k=Ckn+k1. Pourn=1, on a pour tout naturelk,a1;k=1=Ck1+k1.
Soitn>1, supposons que8k2N;an;k=Ckn+k1. Soitk>1.
a n+1;k=kå i=0a n;i=kå i=0Cin+i1=1+kå i=1(Ci+1n+iCin+i) =1+Ck+1n+k1=Ck+1n+k; ce qui reste clair pourk=0. On a montré par récurrence que8n2N;8k2N;an;k=Ckn+k1.Correction del"exer cice4 NOn place le 0 soit au chiffre des unités, soit au chiffre des dizaines, soit au chiffre des centaines, soit au chiffre
des milliers (mais pas au chiffre des dizaines de milliers) et le 0 étant placé, on n"y a plus droit.
Réponse : 4:9:9:9:9=4:94=4:(80+1)2=4:6561=26244.Correction del"exer cice5 NSin>366, on a clairementpn=1 (Principe des tiroirs : si 366 personnes sont à associer à 365 dates
d"anniversaire, alors 2 personnes au moins sont à associer à la même date d"anniversaire). Si 26n6365, on apn=1qnoùqnest la probabilité que les dates d"anniversaire soient deux à deux
distinctes. Il y a(365)nrépartitions possibles des dates d"anniversaires (cas possibles) et parmi ces répartitions,
ilyena365:364:363::::(365n+1)tellesquelesdatesd"anniversairesoientdeuxàdeuxdistinctes. Finalement p n=11(365)n365:364:363::::(365n+1) =1n1Õ k=1365k365 =1n1Õ k=1(1k365 Ensuite,
p n>12 ,n1Õ k=1(1k365 )612 ,n1å k=1ln(1k365 )6ln12 ,n1å k=1ln(1k365 )>ln2: Maintenant, soitx2[0;1[. On a
ln(1x) =Z x 011tdt>Z
x 0110dt=x:
Pourkélément def1;:::;n1g( f1;:::;364g),k365 est un réel élément de[0;1[. En appliquant l"inégalité précédente, on obtient n1å k=1ln(1k365 )>n1å k=1k365 =n(n1)730 Ainsi,
p n>12 (n(n1)730 >ln2,n2n730ln2>0,n>1+p1+2920ln22 =22;99:::,n>23: Finalement, dans un groupe d"au moins 23 personnes, il y a plus d"une chance sur deux que deux personnes au
moins aient la même date d"anniversaire.Correction del"exer cice6 N1.Notre calendrier est 400 ans périodique (et presque 4 :7=28 ans périodique). En effet,
6 (a)la répartition des années biss extilesest 400 ans périodique (1600 et 2000 sont bisse xtilesmais
1700, 1800 et 1900 ne le sont pas (entre autre pour regagner 3 jours tous les 400 ans et coller le plus
possible au rythme du soleil)) (b) il y a un nombre entier de semaines dans une période de 400 ans. En ef fet,sur 400 ans, le quart des
années, soit 100 ans, moins 3 années sont bissextiles et donc sur toute période de 400 ans il y a 97
années bissextiles et 303 années non bissextiles. Une année non bissextile de 365 jours est constituée de 52:7+1 jours ou encore d"un nombre entier
de semaines plus un jour et une année bissextile est constituée d"un nombre entier de semaine plus
deux jours. Une période de 400 ans est donc constituée d"un nombre entier de semaines plus : 97:2+303:1= 194+303=497=7:71 jours qui fournit encore un nombre entier de semaines.
2. Deux périodes consécuti vesde 28 a nsne cont enantpas d"e xception(siècles non bisse xtiles)reproduisent
le même calendrier. En effet, les 7 années bissextiles fournissent un nombre entiers de semaines plus 2:7
jours=2 semaines et les 21 années non bissextiles fournissent un nombre entier de semaines plus 21:1
jours=3 semaines. 3. D"après ce qui précède, il suf fitde compter les 1ers de l"an qui tombe un dimanche ou un samedi sur une
période de 400 ans donnée, par exemple de 1900 à 2299 (inclus). On décompose cette période comme suit :
2097!2100;2101!2128;2129!2156;2157!2184;2185!2200;2201!2228 2229!2256;
2257!2284;2285!2299:
4. On montre ensuite que sur toute période de 28 ans sans siècle non bisse xtile,le premier de l"an tombe
un même nombre de fois chaque jour de la semaine (Lundi, mardi,..). (La connaissance des congruences
modulo 4 et 7 seraient bien utile). Quand on passe d"une année non bissextile à l"année suivante, comme
une telle année contient un nombre entier de semaines plus un jour, le 1er de l"an tombe un jour plus tard
l"année qui suit et deux jours plus tard si l"année est bissextile. Par exemple, 1er janvier 1998 : jeudi 1999 : vendredi 2000 : samedi 2001 : Lundi 2002 : Mardi 2003 : Mercredi
2004 : Jeudi 2005 : samedi...
Notons A,B,C,D,E,F,G les jours de la semaine. Sur une période de 28 ans sans siècle non bissextile
finissant par exemple une année bissextile, on trouve la séquence suivante : ABCD FGAB DEFG BCDE GABC EFGA CDEF (puis çà redémarre ABCD...) soit 4A, 4B, 4C, 4D, 4E, 4F, et 4G.
5. Il reste à étudier les périodes à e xception(soulignées dans le 3)). Détermination du 1er janvier 1900. Le 1er janvier 1998 était un jeudi . Il en est donc de même du 1er
janvier 1998-28 = 1970 et des premiers janvier 1942 et 1914 puis on remonte : 1914 Jeudi 1913 Mercredi 1912 Lundi 1911 Dimanche 1910 Samedi 1909 Vendredi 1908 Mercredi 1907
Mardi 1906 Lundi 1905 Dimanche 1904 Vendredi 1903 Jeudi 1902 Mercredi 1901 Mardi 1900 Lundi (1900 n"est pas bissextile) Les premiers de l"an 2000, 2028 , 2056 et 2084 sont des samedis, 2088 un jeudi, 2092 un mardi, 2096 un
dimanche et donc 2097 mardi 2098 mercredi 2099 jeudi 2100 vendredi. 2101 est un samedi de même que 2129, 2157, 2185 ce qui donne de 2185 à 2200 inclus la séquence :
S D L Ma J V S D Ma Me J V D L Ma Me
2201 est un jeudi de même que 2285 ce qui donne de 2285 à 2299 inclus la séquence :
J V S D Ma Me J V D L Ma Me V S D
7 Le décompte des Lundis , mardis ... soulignés est : 6D 4L 6Ma 5Me 5J 6V 4S. Dans toute période de 400 ans,
le 1er de l"an tombe 2 fois de plus le dimanche que le samedi et donc plus souvent le dimanche que le samedi.Correction del"exer cice7 NOn poseH="vers le haut" etD="vers la droite". Un exemple de chemin de(0;0)à(p;q)est le mot
DD:::DHH:::HoùDest écritpfois etHest écritqfois. Le nombre de chemins cherché est clairement le
nombre d"anagrammes du mot précédent. Le nombre de choix de l"emplacement duHestCq
p+q. Une fois que les lettresHsont placées il n"y a plus de choix pour les lettresD. Il y a doncCq p+qchemins possibles. Remarque : si on place d"abord les lettresDalors on aCp p+qchoix possibles. Mais on trouve bien sûr le même nombre de chemins carCp p+q=C(p+q)p p+q=Cq p+q.Correction del"exer cice8 NOn note respectivementx,yetzle nombre de pièces de 10, 20 et 50 centimes. Il s"agit de résoudre dansN3
l"équation 10x+20y+50z=10000 ou encorex+2y+5z=1000. Soitk2N.x+2y=k,x=k2yet le nombre de solutions de cette équation est : E(k=2)å
k=01=E(k2 )+1: Pour 06z6200 donné, le nombre de solutions de l"équationx+2y=10005zest doncE(10005z2 )+1. Le nombre de solutions en nombres entiers de l"équationx+2y+5z=1000 est donc 200å
z=0(E(10005z2 )+1) =200å z=0(E(5z2 )+501) =201:501+200å z=0E(5z2 ) =100701+200å z=0E(5z2 Maintenant
200
z=0E(5z2 )=100å k=1(E(5(2k1)2 )+E(5(2k)2 ))=100å k=1(E(5k+52 )5k)=100å k=1(10k+2)=20010100:1012 Le nombre de solutions cherchés est donc 10070150300=50401. Il y a 50401 façons de payer 100 euros
avec des pièces de 10, 20 et 50 centimes.Correction del"exer cice9 N1. c A1[:::[An=1cA
1[:::[An=1cA
1\:::\A
n=1cA 1:::cA
n =1(1cA1):::(1cAn) =1(nå k=1(1)k1(å 16i1<::: Ai1:::cAik))
et en sommant sur l"ensemble desxdeE, on obtient le résultat. 2.quotesdbs_dbs22.pdfusesText_28
16i1 +:::+(1)n1card(A1\:::\An): 2. Combien ya-t-ildepermutationssdef1;:::;ngvérifiant8i2f1;:::;ng;s(i)6=i?(Cespermutationssont appelées dérangements (permutations sans point fixe)). Indication : noterAil"ensemble des permutations
qui fixentiet utiliser 1). On peut alors résoudre un célèbre problème de probabilité, le problème des chapeaux.npersonnes
laissent leur chapeau à un vestiaire. En repartant, chaque personne reprend un chapeau au hasard. Montrer que la probabilité qu"aucune de ces personnes n"ait repris son propre chapeau est environ 1e quandnest grand. distincts des sommets se coupent-elles au maximum ? concourantes. Déterminer le nombreP(n)de régions délimitées par ces droites. 2. On donne nplans de l"espace. On suppose qu"il n"en existe pas deux qui soient parallèles, ni trois qui
soient concourants en une droite, ni quatre qui soient concourants en un point. Déterminer le nombre
Q(n)de régions délimitées par ces plans.
2 SoitPknle nombre de partitions d"un ensemble ànéléments enkclasses. Montrer quePkn=Pk1n1+kPkn1pour 26k6n1.
Dresser un tableau pour 16k;n65.
Calculer en fonction dePknle nombre de surjections d"un ensemble ànéléments sur un ensemble àpéléments.
Indication pourl"exer cice7 NCoder un chemin par un mot :Dpour droite,Hpour haut.4 Correction del"exer cice1 N1.Soit Eunensembleànéléments,n>1, etaunélémentfixédeE. Soitf:P(E)!P(E)
A7!Anfagsia2A
A[fagsia=2A.
Montrons quefest involutive (et donc bijective). SoitAun élément deP(E). Sia=2A,f(A) =A[faget donc, puisquea2A[fag,f(f(A)) = (A[fag)nfag=A. Sia2A,f(A) =Anfagetf(f(A)) = (Anfag)[fag=A.
Ainsi,8A2P(E);ff(A) =Aou encore,ff=IdP(E).
Maintenant clairement, en notantPp(E)(resp.Pi(E)) l"ensemble des parties deEde cardinal pair (resp. impair),f(Pp(E))Pi(E)etf(Pi(E))Pp(E). Donc, puisquefest bijective card(Pp(E)) =card(f(Pp(E))6cardPi(E) et de même card(Pi(E))6cardPp(E). Finalement, card(Pi(E)) =cardPp(E). 2. Soient E=fa1;:::;angun ensemble ànéléments etaun élément fixé deE. Soitk2 f1;:::;n1g.
Il y aCk1n1parties àkéléments qui contiennenta. Donc,nCk1n1(=Ck1n1+:::+Ck1n1)est donc la somme
du nombre de parties àkéléments qui contiennenta1et du nombre de parties àkéléments qui contiennent
a 2... et du nombre de parties àkéléments qui contiennentan.
Dans cette dernière somme, chaque partie àkéléments deEa été comptée plusieurs fois et toutes les
parties àkéléments (en nombre égal àCkn) ont été comptés un même nombre de fois. Combien de fois a
été comptéefa1;a2:::akg? Cette partie a été comptée une fois en tant que partie contenanta1, une fois
en tant que partie contenanta2... et une fois comme partie contenantaket donc a été comptéekfois.
Conclusion :kCkn=nCk1n1.
3. Soit E=fa1;:::;an;b1;:::;bngun ensemble à 2néléments. Il y aCn2nparties ànéléments deE. Une telle
partie akéléments dansfa1;:::;angetnkdansfb1;:::;bngpour un certainkdef0;:::;ng. Il y aCknchoix possibles dekéléments dansfa1;:::;angetCnknchoix possibles denkéléments dansfb1;:::;bng
pourkdonné dansf0;:::;nget quandkvarie de 0 àn, on obtient : C n2n=nå k=0CknCnkn=nå k=0(Ckn)2:Correction del"exer cice2 NIlyaCqpqchoixpossiblesd"unepremièreclasse. Cettepremièreclasseétantchoisie, ilyaCq
pqq=Cq (p1)qchoix possibles de la deuxième classe... etCqqchoix possibles de lap-ième classe. Au total, il y aCqpqCq
(p1)q:::Cqq choix possibles d"une première classe, puis d"une deuxième ...puis d"unep-ième. Maintenant dans le nombreCqpqCq
(p1)q:::Cqq, on a compté plusieurs fois chaque partition, chacune ayant été compté un nombre égal de fois. On a compté chaque partition autant de fois qu"il y a de permutations despclasses à savoirp!. Le nombre
cherché est donc : 1p!CqpqCq
(p1)q:::Cqq=1p!(pq)!q!((p1)q)!((p1)q)!q!((p2)q)!:::(2q)!q!q!q!q!0!=(pq)!p!(q!)p:Correction del"exer cice3 NClairement,8n2N;an;0=1 (unique solution : 0+0+:::+0=0) et8k2N;a1;k=1 (unique solution :k=k).
5 Soientn>1 etk>0 fixés.an+1;kest le nombre de solutions en nombre entiers positifsxide l"équation
x 1+:::+xn+xn+1=k. Il y aan;ksolutions telles quexn+1=0 puisan;k1solutions telles quexn+1=1 ... puis
a n;0solutions telles quexn+1=k. Donc,8n2N;8k2N;an+1;k=an;k+an;k1+:::+an;0(et on rappellean;0=a1;k=1). Montrons alors par récurrence surn, entier naturel non nul, que :8n2N;8k2N;an;k=Ckn+k1. Pourn=1, on a pour tout naturelk,a1;k=1=Ck1+k1.
Soitn>1, supposons que8k2N;an;k=Ckn+k1. Soitk>1.
a n+1;k=kå i=0a n;i=kå i=0Cin+i1=1+kå i=1(Ci+1n+iCin+i) =1+Ck+1n+k1=Ck+1n+k; ce qui reste clair pourk=0. On a montré par récurrence que8n2N;8k2N;an;k=Ckn+k1.Correction del"exer cice4 NOn place le 0 soit au chiffre des unités, soit au chiffre des dizaines, soit au chiffre des centaines, soit au chiffre
des milliers (mais pas au chiffre des dizaines de milliers) et le 0 étant placé, on n"y a plus droit.
Réponse : 4:9:9:9:9=4:94=4:(80+1)2=4:6561=26244.Correction del"exer cice5 NSin>366, on a clairementpn=1 (Principe des tiroirs : si 366 personnes sont à associer à 365 dates
d"anniversaire, alors 2 personnes au moins sont à associer à la même date d"anniversaire). Si 26n6365, on apn=1qnoùqnest la probabilité que les dates d"anniversaire soient deux à deux
distinctes. Il y a(365)nrépartitions possibles des dates d"anniversaires (cas possibles) et parmi ces répartitions,
ilyena365:364:363::::(365n+1)tellesquelesdatesd"anniversairesoientdeuxàdeuxdistinctes. Finalement p n=11(365)n365:364:363::::(365n+1) =1n1Õ k=1365k365 =1n1Õ k=1(1k365 Ensuite,
p n>12 ,n1Õ k=1(1k365 )612 ,n1å k=1ln(1k365 )6ln12 ,n1å k=1ln(1k365 )>ln2: Maintenant, soitx2[0;1[. On a
ln(1x) =Z x 011tdt>Z
x 0110dt=x:
Pourkélément def1;:::;n1g( f1;:::;364g),k365 est un réel élément de[0;1[. En appliquant l"inégalité précédente, on obtient n1å k=1ln(1k365 )>n1å k=1k365 =n(n1)730 Ainsi,
p n>12 (n(n1)730 >ln2,n2n730ln2>0,n>1+p1+2920ln22 =22;99:::,n>23: Finalement, dans un groupe d"au moins 23 personnes, il y a plus d"une chance sur deux que deux personnes au
moins aient la même date d"anniversaire.Correction del"exer cice6 N1.Notre calendrier est 400 ans périodique (et presque 4 :7=28 ans périodique). En effet,
6 (a)la répartition des années biss extilesest 400 ans périodique (1600 et 2000 sont bisse xtilesmais
1700, 1800 et 1900 ne le sont pas (entre autre pour regagner 3 jours tous les 400 ans et coller le plus
possible au rythme du soleil)) (b) il y a un nombre entier de semaines dans une période de 400 ans. En ef fet,sur 400 ans, le quart des
années, soit 100 ans, moins 3 années sont bissextiles et donc sur toute période de 400 ans il y a 97
années bissextiles et 303 années non bissextiles. Une année non bissextile de 365 jours est constituée de 52:7+1 jours ou encore d"un nombre entier
de semaines plus un jour et une année bissextile est constituée d"un nombre entier de semaine plus
deux jours. Une période de 400 ans est donc constituée d"un nombre entier de semaines plus : 97:2+303:1= 194+303=497=7:71 jours qui fournit encore un nombre entier de semaines.
2. Deux périodes consécuti vesde 28 a nsne cont enantpas d"e xception(siècles non bisse xtiles)reproduisent
le même calendrier. En effet, les 7 années bissextiles fournissent un nombre entiers de semaines plus 2:7
jours=2 semaines et les 21 années non bissextiles fournissent un nombre entier de semaines plus 21:1
jours=3 semaines. 3. D"après ce qui précède, il suf fitde compter les 1ers de l"an qui tombe un dimanche ou un samedi sur une
période de 400 ans donnée, par exemple de 1900 à 2299 (inclus). On décompose cette période comme suit :
2097!2100;2101!2128;2129!2156;2157!2184;2185!2200;2201!2228 2229!2256;
2257!2284;2285!2299:
4. On montre ensuite que sur toute période de 28 ans sans siècle non bisse xtile,le premier de l"an tombe
un même nombre de fois chaque jour de la semaine (Lundi, mardi,..). (La connaissance des congruences
modulo 4 et 7 seraient bien utile). Quand on passe d"une année non bissextile à l"année suivante, comme
une telle année contient un nombre entier de semaines plus un jour, le 1er de l"an tombe un jour plus tard
l"année qui suit et deux jours plus tard si l"année est bissextile. Par exemple, 1er janvier 1998 : jeudi 1999 : vendredi 2000 : samedi 2001 : Lundi 2002 : Mardi 2003 : Mercredi
2004 : Jeudi 2005 : samedi...
Notons A,B,C,D,E,F,G les jours de la semaine. Sur une période de 28 ans sans siècle non bissextile
finissant par exemple une année bissextile, on trouve la séquence suivante : ABCD FGAB DEFG BCDE GABC EFGA CDEF (puis çà redémarre ABCD...) soit 4A, 4B, 4C, 4D, 4E, 4F, et 4G.
5. Il reste à étudier les périodes à e xception(soulignées dans le 3)). Détermination du 1er janvier 1900. Le 1er janvier 1998 était un jeudi . Il en est donc de même du 1er
janvier 1998-28 = 1970 et des premiers janvier 1942 et 1914 puis on remonte : 1914 Jeudi 1913 Mercredi 1912 Lundi 1911 Dimanche 1910 Samedi 1909 Vendredi 1908 Mercredi 1907
Mardi 1906 Lundi 1905 Dimanche 1904 Vendredi 1903 Jeudi 1902 Mercredi 1901 Mardi 1900 Lundi (1900 n"est pas bissextile) Les premiers de l"an 2000, 2028 , 2056 et 2084 sont des samedis, 2088 un jeudi, 2092 un mardi, 2096 un
dimanche et donc 2097 mardi 2098 mercredi 2099 jeudi 2100 vendredi. 2101 est un samedi de même que 2129, 2157, 2185 ce qui donne de 2185 à 2200 inclus la séquence :
S D L Ma J V S D Ma Me J V D L Ma Me
2201 est un jeudi de même que 2285 ce qui donne de 2285 à 2299 inclus la séquence :
J V S D Ma Me J V D L Ma Me V S D
7 Le décompte des Lundis , mardis ... soulignés est : 6D 4L 6Ma 5Me 5J 6V 4S. Dans toute période de 400 ans,
le 1er de l"an tombe 2 fois de plus le dimanche que le samedi et donc plus souvent le dimanche que le samedi.Correction del"exer cice7 NOn poseH="vers le haut" etD="vers la droite". Un exemple de chemin de(0;0)à(p;q)est le mot
DD:::DHH:::HoùDest écritpfois etHest écritqfois. Le nombre de chemins cherché est clairement le
nombre d"anagrammes du mot précédent. Le nombre de choix de l"emplacement duHestCq
p+q. Une fois que les lettresHsont placées il n"y a plus de choix pour les lettresD. Il y a doncCq p+qchemins possibles. Remarque : si on place d"abord les lettresDalors on aCp p+qchoix possibles. Mais on trouve bien sûr le même nombre de chemins carCp p+q=C(p+q)p p+q=Cq p+q.Correction del"exer cice8 NOn note respectivementx,yetzle nombre de pièces de 10, 20 et 50 centimes. Il s"agit de résoudre dansN3
l"équation 10x+20y+50z=10000 ou encorex+2y+5z=1000. Soitk2N.x+2y=k,x=k2yet le nombre de solutions de cette équation est : E(k=2)å
k=01=E(k2 )+1: Pour 06z6200 donné, le nombre de solutions de l"équationx+2y=10005zest doncE(10005z2 )+1. Le nombre de solutions en nombres entiers de l"équationx+2y+5z=1000 est donc 200å
z=0(E(10005z2 )+1) =200å z=0(E(5z2 )+501) =201:501+200å z=0E(5z2 ) =100701+200å z=0E(5z2 Maintenant
200
z=0E(5z2 )=100å k=1(E(5(2k1)2 )+E(5(2k)2 ))=100å k=1(E(5k+52 )5k)=100å k=1(10k+2)=20010100:1012 Le nombre de solutions cherchés est donc 10070150300=50401. Il y a 50401 façons de payer 100 euros
avec des pièces de 10, 20 et 50 centimes.Correction del"exer cice9 N1. c A1[:::[An=1cA
1[:::[An=1cA
1\:::\A
n=1cA 1:::cA
n =1(1cA1):::(1cAn) =1(nå k=1(1)k1(å 16i1<::: Ai1:::cAik))
et en sommant sur l"ensemble desxdeE, on obtient le résultat. 2.quotesdbs_dbs22.pdfusesText_28
appelées dérangements (permutations sans point fixe)). Indication : noterAil"ensemble des permutations
qui fixentiet utiliser 1).On peut alors résoudre un célèbre problème de probabilité, le problème des chapeaux.npersonnes
laissent leur chapeau à un vestiaire. En repartant, chaque personne reprend un chapeau au hasard. Montrer que la probabilité qu"aucune de ces personnes n"ait repris son propre chapeau est environ 1e quandnest grand. distincts des sommets se coupent-elles au maximum ? concourantes. Déterminer le nombreP(n)de régions délimitées par ces droites. 2.On donne nplans de l"espace. On suppose qu"il n"en existe pas deux qui soient parallèles, ni trois qui
soient concourants en une droite, ni quatre qui soient concourants en un point. Déterminer le nombre
Q(n)de régions délimitées par ces plans.
2 SoitPknle nombre de partitions d"un ensemble ànéléments enkclasses.Montrer quePkn=Pk1n1+kPkn1pour 26k6n1.
Dresser un tableau pour 16k;n65.
Calculer en fonction dePknle nombre de surjections d"un ensemble ànéléments sur un ensemble àpéléments.
Indication pourl"exer cice7 NCoder un chemin par un mot :Dpour droite,Hpour haut.4Correction del"exer cice1 N1.Soit Eunensembleànéléments,n>1, etaunélémentfixédeE. Soitf:P(E)!P(E)
A7!Anfagsia2A
A[fagsia=2A.
Montrons quefest involutive (et donc bijective). SoitAun élément deP(E). Sia=2A,f(A) =A[faget donc, puisquea2A[fag,f(f(A)) = (A[fag)nfag=A.Sia2A,f(A) =Anfagetf(f(A)) = (Anfag)[fag=A.
Ainsi,8A2P(E);ff(A) =Aou encore,ff=IdP(E).
Maintenant clairement, en notantPp(E)(resp.Pi(E)) l"ensemble des parties deEde cardinal pair (resp. impair),f(Pp(E))Pi(E)etf(Pi(E))Pp(E). Donc, puisquefest bijective card(Pp(E)) =card(f(Pp(E))6cardPi(E) et de même card(Pi(E))6cardPp(E). Finalement, card(Pi(E)) =cardPp(E). 2.Soient E=fa1;:::;angun ensemble ànéléments etaun élément fixé deE. Soitk2 f1;:::;n1g.
Il y aCk1n1parties àkéléments qui contiennenta. Donc,nCk1n1(=Ck1n1+:::+Ck1n1)est donc la somme
du nombre de parties àkéléments qui contiennenta1et du nombre de parties àkéléments qui contiennent
a2... et du nombre de parties àkéléments qui contiennentan.
Dans cette dernière somme, chaque partie àkéléments deEa été comptée plusieurs fois et toutes les
parties àkéléments (en nombre égal àCkn) ont été comptés un même nombre de fois. Combien de fois a
été comptéefa1;a2:::akg? Cette partie a été comptée une fois en tant que partie contenanta1, une fois
en tant que partie contenanta2... et une fois comme partie contenantaket donc a été comptéekfois.
Conclusion :kCkn=nCk1n1.
3.Soit E=fa1;:::;an;b1;:::;bngun ensemble à 2néléments. Il y aCn2nparties ànéléments deE. Une telle
partie akéléments dansfa1;:::;angetnkdansfb1;:::;bngpour un certainkdef0;:::;ng. Il y aCknchoix possibles dekéléments dansfa1;:::;angetCnknchoix possibles denkéléments dansfb1;:::;bng
pourkdonné dansf0;:::;nget quandkvarie de 0 àn, on obtient : C n2n=nå k=0CknCnkn=nåk=0(Ckn)2:Correction del"exer cice2 NIlyaCqpqchoixpossiblesd"unepremièreclasse. Cettepremièreclasseétantchoisie, ilyaCq
pqq=Cq (p1)qchoixpossibles de la deuxième classe... etCqqchoix possibles de lap-ième classe. Au total, il y aCqpqCq
(p1)q:::Cqq choix possibles d"une première classe, puis d"une deuxième ...puis d"unep-ième.Maintenant dans le nombreCqpqCq
(p1)q:::Cqq, on a compté plusieurs fois chaque partition, chacune ayant été compté un nombre égal de fois.On a compté chaque partition autant de fois qu"il y a de permutations despclasses à savoirp!. Le nombre
cherché est donc :1p!CqpqCq
(p1)q:::Cqq=1p!(pq)!q!((p1)q)!((p1)q)!q!((p2)q)!:::(2q)!q!q!q!q!0!=(pq)!p!(q!)p:Correction del"exer cice3 NClairement,8n2N;an;0=1 (unique solution : 0+0+:::+0=0) et8k2N;a1;k=1 (unique solution :k=k).
5Soientn>1 etk>0 fixés.an+1;kest le nombre de solutions en nombre entiers positifsxide l"équation
x1+:::+xn+xn+1=k. Il y aan;ksolutions telles quexn+1=0 puisan;k1solutions telles quexn+1=1 ... puis
a n;0solutions telles quexn+1=k. Donc,8n2N;8k2N;an+1;k=an;k+an;k1+:::+an;0(et on rappellean;0=a1;k=1). Montrons alors par récurrence surn, entier naturel non nul, que :8n2N;8k2N;an;k=Ckn+k1.Pourn=1, on a pour tout naturelk,a1;k=1=Ck1+k1.
Soitn>1, supposons que8k2N;an;k=Ckn+k1. Soitk>1.
a n+1;k=kå i=0a n;i=kå i=0Cin+i1=1+kå i=1(Ci+1n+iCin+i) =1+Ck+1n+k1=Ck+1n+k; ce qui reste clair pourk=0.On a montré par récurrence que8n2N;8k2N;an;k=Ckn+k1.Correction del"exer cice4 NOn place le 0 soit au chiffre des unités, soit au chiffre des dizaines, soit au chiffre des centaines, soit au chiffre
des milliers (mais pas au chiffre des dizaines de milliers) et le 0 étant placé, on n"y a plus droit.
Réponse : 4:9:9:9:9=4:94=4:(80+1)2=4:6561=26244.Correction del"exer cice5 NSin>366, on a clairementpn=1 (Principe des tiroirs : si 366 personnes sont à associer à 365 dates
d"anniversaire, alors 2 personnes au moins sont à associer à la même date d"anniversaire).Si 26n6365, on apn=1qnoùqnest la probabilité que les dates d"anniversaire soient deux à deux
distinctes. Il y a(365)nrépartitions possibles des dates d"anniversaires (cas possibles) et parmi ces répartitions,
ilyena365:364:363::::(365n+1)tellesquelesdatesd"anniversairesoientdeuxàdeuxdistinctes. Finalement p n=11(365)n365:364:363::::(365n+1) =1n1Õ k=1365k365 =1n1Õ k=1(1k365Ensuite,
p n>12 ,n1Õ k=1(1k365 )612 ,n1å k=1ln(1k365 )6ln12 ,n1å k=1ln(1k365 )>ln2:Maintenant, soitx2[0;1[. On a
ln(1x) =Z x011tdt>Z
x0110dt=x:
Pourkélément def1;:::;n1g( f1;:::;364g),k365 est un réel élément de[0;1[. En appliquant l"inégalité précédente, on obtient n1å k=1ln(1k365 )>n1å k=1k365 =n(n1)730Ainsi,
p n>12 (n(n1)730 >ln2,n2n730ln2>0,n>1+p1+2920ln22 =22;99:::,n>23:Finalement, dans un groupe d"au moins 23 personnes, il y a plus d"une chance sur deux que deux personnes au
moins aient la même date d"anniversaire.Correction del"exer cice6 N1.Notre calendrier est 400 ans périodique (et presque 4 :7=28 ans périodique). En effet,
6(a)la répartition des années biss extilesest 400 ans périodique (1600 et 2000 sont bisse xtilesmais
1700, 1800 et 1900 ne le sont pas (entre autre pour regagner 3 jours tous les 400 ans et coller le plus
possible au rythme du soleil)) (b)il y a un nombre entier de semaines dans une période de 400 ans. En ef fet,sur 400 ans, le quart des
années, soit 100 ans, moins 3 années sont bissextiles et donc sur toute période de 400 ans il y a 97
années bissextiles et 303 années non bissextiles.Une année non bissextile de 365 jours est constituée de 52:7+1 jours ou encore d"un nombre entier
de semaines plus un jour et une année bissextile est constituée d"un nombre entier de semaine plus
deux jours. Une période de 400 ans est donc constituée d"un nombre entier de semaines plus : 97:2+303:1=194+303=497=7:71 jours qui fournit encore un nombre entier de semaines.
2.Deux périodes consécuti vesde 28 a nsne cont enantpas d"e xception(siècles non bisse xtiles)reproduisent
le même calendrier. En effet, les 7 années bissextiles fournissent un nombre entiers de semaines plus 2:7
jours=2 semaines et les 21 années non bissextiles fournissent un nombre entier de semaines plus 21:1
jours=3 semaines. 3.D"après ce qui précède, il suf fitde compter les 1ers de l"an qui tombe un dimanche ou un samedi sur une
période de 400 ans donnée, par exemple de 1900 à 2299 (inclus).On décompose cette période comme suit :
2097!2100;2101!2128;2129!2156;2157!2184;2185!2200;2201!2228 2229!2256;
2257!2284;2285!2299:
4.On montre ensuite que sur toute période de 28 ans sans siècle non bisse xtile,le premier de l"an tombe
un même nombre de fois chaque jour de la semaine (Lundi, mardi,..). (La connaissance des congruences
modulo 4 et 7 seraient bien utile). Quand on passe d"une année non bissextile à l"année suivante, comme
une telle année contient un nombre entier de semaines plus un jour, le 1er de l"an tombe un jour plus tard
l"année qui suit et deux jours plus tard si l"année est bissextile. Par exemple,1er janvier 1998 : jeudi 1999 : vendredi 2000 : samedi 2001 : Lundi 2002 : Mardi 2003 : Mercredi
2004 : Jeudi 2005 : samedi...
Notons A,B,C,D,E,F,G les jours de la semaine. Sur une période de 28 ans sans siècle non bissextile
finissant par exemple une année bissextile, on trouve la séquence suivante : ABCD FGAB DEFG BCDE GABC EFGA CDEF (puis çà redémarre ABCD...) soit 4A, 4B, 4C, 4D,4E, 4F, et 4G.
5. Il reste à étudier les périodes à e xception(soulignées dans le 3)).Détermination du 1er janvier 1900. Le 1er janvier 1998 était un jeudi . Il en est donc de même du 1er
janvier 1998-28 = 1970 et des premiers janvier 1942 et 1914 puis on remonte :1914 Jeudi 1913 Mercredi 1912 Lundi 1911 Dimanche 1910 Samedi 1909 Vendredi 1908 Mercredi 1907
Mardi 1906 Lundi 1905 Dimanche 1904 Vendredi 1903 Jeudi 1902 Mercredi 1901 Mardi 1900 Lundi (1900 n"est pas bissextile)Les premiers de l"an 2000, 2028 , 2056 et 2084 sont des samedis, 2088 un jeudi, 2092 un mardi, 2096 un
dimanche et donc 2097 mardi 2098 mercredi 2099 jeudi 2100 vendredi.2101 est un samedi de même que 2129, 2157, 2185 ce qui donne de 2185 à 2200 inclus la séquence :
S D L Ma J V S D Ma Me J V D L Ma Me
2201 est un jeudi de même que 2285 ce qui donne de 2285 à 2299 inclus la séquence :
J V S D Ma Me J V D L Ma Me V S D
7Le décompte des Lundis , mardis ... soulignés est : 6D 4L 6Ma 5Me 5J 6V 4S. Dans toute période de 400 ans,
le 1er de l"an tombe 2 fois de plus le dimanche que le samedi et donc plus souvent le dimanche que le samedi.Correction del"exer cice7 NOn poseH="vers le haut" etD="vers la droite". Un exemple de chemin de(0;0)à(p;q)est le mot
DD:::DHH:::HoùDest écritpfois etHest écritqfois. Le nombre de chemins cherché est clairement le
nombre d"anagrammes du mot précédent.Le nombre de choix de l"emplacement duHestCq
p+q. Une fois que les lettresHsont placées il n"y a plus de choix pour les lettresD. Il y a doncCq p+qchemins possibles. Remarque : si on place d"abord les lettresDalors on aCp p+qchoix possibles. Mais on trouve bien sûr le même nombre de chemins carCp p+q=C(p+q)p p+q=Cqp+q.Correction del"exer cice8 NOn note respectivementx,yetzle nombre de pièces de 10, 20 et 50 centimes. Il s"agit de résoudre dansN3
l"équation 10x+20y+50z=10000 ou encorex+2y+5z=1000. Soitk2N.x+2y=k,x=k2yet le nombre de solutions de cette équation est :E(k=2)å
k=01=E(k2 )+1: Pour 06z6200 donné, le nombre de solutions de l"équationx+2y=10005zest doncE(10005z2 )+1. Le nombre de solutions en nombres entiers de l"équationx+2y+5z=1000 est donc200å
z=0(E(10005z2 )+1) =200å z=0(E(5z2 )+501) =201:501+200å z=0E(5z2 ) =100701+200å z=0E(5z2Maintenant
200z=0E(5z2 )=100å k=1(E(5(2k1)2 )+E(5(2k)2 ))=100å k=1(E(5k+52 )5k)=100å k=1(10k+2)=20010100:1012
Le nombre de solutions cherchés est donc 10070150300=50401. Il y a 50401 façons de payer 100 euros
avec des pièces de 10, 20 et 50 centimes.Correction del"exer cice9 N1. c