Math.umons.ac.be

Exercices : Analyse combinatoire et probabilit´e a retrouver l’assassin du Dr. Lenoir, l’arme et le lieu du crime. Sachant qu’il y a six armes, neuf lieux et six suspects, de combien de mani` e des sciences se compose de sept professeurs d’infor- matique, quinze professeurs de chimie, douze professeurs de physique, huit professeursde math´ ematique et cinq professeurs de biologie, combien de choix d’un repr´ 3. Les plaques d’immatriculation belges sont constitu´ chiffres (exemple : ABC-123). Combien de plaques diff´ 4. A l’aide des six chiffres : 2, 3, 5, 6, 7, 9 : (a) combien de nombres de trois chiffres peut-on former ? (e) combien de ces nombres sont impairs ? (f) combien de ces nombres sont des multiples de cinq ? 5. Soit n ∈ N. Ecrire un algorithme (en pseudo-code) qui calcule la factorielle de n.
Prouver la correction et la terminaison de votre algorithme.
6. Prouver que toute suite de n2 + 1 nombres r´ eels distincts contient une sous-suite de longueur (n + 1) qui est soit strictement croissante ou strictement d´ 7. Soit une course de quatorze chevaux.
son dauphin. Sachant qu’il y a 25 candidats, combien de choix sont possibles.
9. Lors du conseil d’institut d’informatique, un pr´ mais seul un professeur peut devenir pr´ 10. De combien de fa¸cons peut-on choisir cinq repr´ 11. Prouver que le nombre de permutations de n objets est ´ 12. La serrure d’un cadenas se compose de trois anneaux portant chacun tous les chiffres a 9. De combien de fa¸cons peut-on tenter un essai pour ouvrir le cadenas ? 13. Une firme a dix vendeurs, de combien de mani` (a) deux groupes de six et quatre vendeurs, (b) deux groupes de sept et trois vendeurs.
14. De combien de fa¸cons peut-on former un jury de trois hommes et deux femmes parmi 15. Combien existe-t-il de mots dans chacun des cas suivants : (b) Mots de quatres lettres distinctes.
(c) Mots de quatres lettres distinctes commen¸cant par une voyelle.
(d) Mots de quatres lettres distinctes commen¸cant par une voyelle et se terminant par (b) Prouver (par induction sur n) que Cp = enombrable), A, B ⊆ Ω et P : 2Ω → [0, 1] une mesure de P(∅) = 0 ; P(Ac) = 1 − P(A) ; A ⊆ B ⇒ P(A) ≤ P(B) ; P(A \ B) = P(A) − P(B) ; P(A ∪ B) = P(A) + P(B) − P(A ∩ B).
eces de monnaie et on compte le nombre de “face”. Quel est l’univers Ω 20. Trois chevaux A, B et C s’affrontent lors d’une course. On sait que le cheval A a deux fois plus de chance de gagner que le cheval B et que le cheval B a deux fois plus dechance de gagner que le cheval C. Calculer (i) la probabilit´ e que le cheval C ne gagne pas la course.
21. Trois hommes et deux femmes prennent part ` e de gagner, mais une femme a deux fois plus de chance de gagner qu’un homme. Trouver la probabilit´ e (i) qu’une femme remporte le tournoi, (ii) qu’un homme remporte le tournoi.
(b) Si quatre personnes sont choisies al´ e ne soit parmi ces quatre personnes.
es. Sachant que les deux nombres apparus sont diff´ (b) qu’un 1 apparaisse sur l’un des deux d´ Calculer (i) P(A|B), (ii) P(B|A), (iii) P(A ∪ B), (iv) P(Ac|Bc) et (v) P(Bc|Ac).
25. Soit Ω l’univers, A, B ⊆ Ω et P : 2Ω → [0, 1] une mesure de probabilit´e. Prouver que si eme des anniversaires Combien de personnes (au minimum) doivent se trouver esirables (spam), certaines boˆıtes mails utilisent des filtres Baysiens.
a spam Baysien utilise les informations sur les mails pr´ “deviner” si un message entrant est (ou non) un spam. En particulier, il se focalise surl’occurence de certains mots apparaissant dans le mail (i.e. “viagra”, “rolex”,.) e les messages re¸cus d’une boˆıte mail donn´ messages qui sont des spams (on note B cet ensemble) et les messages qui ne sont pasdes spams (on note G cet ensemble). Soit ω un mot, on note nB(ω) (resp. nG(ω)) lenombre de messages de l’ensemble B (resp. G) contenant le mot ω.
Supposons que l’on re¸coive un nouveau message contenant le mot ω. On voudraitd´ e que ce message soit un spam. On note S (resp. Sc) l’´ “est un spam” (resp. “n’est pas un spam”) et Eω l’´ev´enement “contient le mot ω’. Par e qu’un message est un spam, sachant qu’il contient evaluer cette expression, on a besoin d’estimer les diff´ – P(S) (resp. P(Sc)) la probabilit´e qu’un message envoy´e soit (resp. ne soit pas) un ementaire, on peut supposer que P(S) = 1 (resp.
ees empiriques sur le pourcentage des spams – P(Eω|S) la probabilit´e qu’un message contienne le mot ω sachant que c’est un spam.
ees, en estimant P(Eω|S) par nB(ω), not´e p(ω).
– P(Eω|Sc) la probabilit´e qu’un message contienne le mot ω sachant que ce n’est pas eme fa¸con, on estime P(Eω|Sc) par nG(ω), not´e q(ω).
eter qu’un message est un spam si P(S|Eω) est au-del`a d’un certain seuil (0.9 par exemple).
Soit une boˆıte mail contenant 3000 messages, on consid` sont des spams. On suppose que le mot “lottery” apparaˆıt dans 250 des 2000 spamset seulement dans 5 des messages qui ne sont pas des spams. Quelle est la probabilit´ qu’un mail contenant le mot “lottery” soit un spam ? ece deux fois. Il gagne deux euros s’il obtient deux face, un euro s’il obtient une fois face et il perd trois euros s’il ne voit pas face. Calculer l’esp´ ees en l’air, on note Ω l’univers de cette exp´ Ω = {F, P }3. Soit ω ∈ Ω, on note nf (resp. np) le nombre de face (resp. de pile) pr´esentdans ω. Calculer l’esp´ 30. Soit un examen qui consiste en une s´ erie de dix Vrai ou Faux (dans lequel les ´ eponses). Dans chacun des cas suivants, calculer (i) la a cinq sur dix) ; (ii) la note moyenne obtenue par un tel enement “Un nombre pair apparaˆıt sur la face sup´ enements suivants : A ; A et B ; A ou B ; A sachant 32. Soit Ω l’univers (fini) d’une exp´ eatoire, P une mesure de probabilit´e sur Ω et X ⊆ Ω. Prouver que P(Xc) = 1 − P(X). (Examen juin 2009) ece de monnaie. Il gagne cinq euros s’il obtient au moins deux fois face, un euro s’il n’obtient qu’une seule fois face et il perd dix euros s’ilne voit pas face. Calculer l’esp´ erance de gain du joueur dans ce jeu (en pr´ est l’univers, la fonction de probabilit´ ecider si l’affirmation suivante est vraie ou fausse. Justifier votre r´ Soit Ω l’univers (fini) d’une exp´ eatoire, P une mesure de probabilit´e sur Ω et X ⊆ Ω. Si P(X) = 1, alors X = Ω.
(Examen juin 2009) a la roulette. Pour simplifier les choses, a 36 et que le joueur pariera sur le fait que la bille stoppe sur un nombre pair ou impair de telle sorte que s’il gagne, il re¸coitle double de ce qu’il a mis´ e. Ce joueur va jouer de la fa¸con suivante : (i) il mise toujours sur pair, (ii) chaque fois qu’il perd, il rejoue en doublant la mise qu’il vient de perdre,(iii) il arrˆ ete de jouer s’il gagne ou s’il a perdu cinq fois de suite. Sa mise initiale est (c) Prouver que s’il gagne, le joueur gagnera toujours exactement un euro.
(e) Quelle somme d’argent ce joueur doit-il avoir en poche en entrant dans le casino etre certain de pouvoir appliquer sa strat´ 36. Un homme se trouve dans un bar, et toutes les cinq minutes, il se demande s’il va com- etes). A chaque fois qu’il se pose la question, il prend la d´ e 2 et il rentre donc chez lui avec probabilit´ e que ce brave homme rentre chez lui apr` e que ce brave homme ne rentre jamais chez lui ? a cette situation et prouvez qu’il s’agit 37. On tire successivement deux cartes dans un jeu de cartes complet (la premi` n’est pas remise dans le tas avant de tirer la seconde). Soient A l’´ ee est une figure (valet, dame ou roi) rouge” et B l’´ 38. Dans la rue, Mister Proba vous propose de participer au jeu suivant pour la modique somme de dix euros. Votre objectif est de lancer deux d´ exactement 9, Mister Proba vous rend vingt euros (i.e. vous gagnez dix euros). Si vousobtenez un total strictement sup´ a 9, Mister Proba ne vous rend rien (i.e. vous perdez dix euros). Si vous obtenez un total ´ a n, avec 2 ≤ n ≤ 8, Mister Proba vous es, donnez l’univers Ω, la probabilit´ Imaginons maintenant que vous avez lanc´ un 4 totalisant une somme de 7. Mister Proba vous propose de relancer l’un des deuxd´ es contre un paiement de cinq euros suppl´ (c) Parmi les trois situations suivantes, laquelle est la plus int´ (i) Refuser l’offre de Mister Proba, (ii) Relancer le d´ enements “Obtenir une somme de 9” et “Obtenir une somme de 9 sachant etudie le comportement d’une souris lorsqu’elle est plac´ labyrinthes triangulaires. Un tel labyrinthe de type 3 est repr´ ee dans l’unique case du niveau 0 et ´ Les trappes ne permettent que de passer d’un niveau i vers un niveau i + 1 (notresouris ne peut donc jamais retourner en arri` ere). Hormis au dernier niveau, la souris ne Supposons que chaque fois que notre souris doit faire un choix, elle va ` (a) Dans le labyrinthe de type 3, quelle est la probabilit´ ere maintenant un labyrinthe de type 4. A l’aide de la question pr´ (c) Dans un labyrinthe de type n, calculer la probabilit´ (d) Dans un labyrinthe de type n, calculer la probabilit´ 40. Soit n ∈ N0. On consid`ere une exp´erience al´eatoire o`u une pi`ece de monnaie (non ee sur pile (resp. face) au cours des n lancers.
On note (Ωn, Pn) l’espace de probabilit´e associ´e `a cette exp´erience.
D´ eterminez si les affirmations suivantes sont vraies ou fausses.
(a) L’univers Ω3 contient 3 ´el´ements.
(d) Quel que soit n ∈ N0, Pn((0, n)) = Pn((n, 0)) = 1 .
(e) Quel que soit n ≥ 2, quel que soit p ∈ {1, . . . , n − 1}, Pn((p, n − p)) = Pn−1((p − 1, n − p)) + Pn−1((p, n − p − 1)).
(f) Quel que soit n ∈ N0, quel que soit p ∈ {0, . . . , n},

Source: http://math.umons.ac.be/maef/fr/enseignement/md/combiproba.pdf