Exercices de MPSI

[wallissen]

Indications données pour les deux derniers exos

Pour les polygones

SPOILER:

le nombre à trouver est $ \frac{n}{k}\binom{n-k-1}{k-1} = \frac{n(n-k-1)!}{k!(n-2k)!} $

Pour les allumettes

SPOILER:

a ) Le resultat à démontrer est $ \frac{\binom{2n-k}{n}}{2^{2n-k}} $

b) $ 2^{2n} $

Par contre l'exo sur les tickets de cinéma est difficile, mais pas hors programme et il y a plusieurs méthodes pour faire chaque question .

[mathophilie]

n + m personnes font la queue à l'entrée d'un cinéma; n d'entre eux ont des billets de cinq francs et les m autres n'ont rien de plus petit que des billets de dix francs.
Les tickets au cinéma coûtent 5 francs chacun. Au moment où le cinéma ouvre ses portes, il n'y a pas d'argent dans la caisse.
a) Si chaque client achète un seul ticket, quelle est la probabilité qu'aucun d'entre eux n'ait à attendre pour la monnaie?

b. Résoudre le même problème sous l'hypothèse qu'il y avait initialement p billets de cinq francs dans la caisse.

c) On suppose qu'il existe des billets de trois francs en circulation. n + m font personnes font la queue à l'entrée d'un cinéma; n d'entre eux n'ont qu'un seul franc
et les m autres ont seulement des billets de trois francs. Les tickets au cinéma coûtent 1 franc chacun et chaque personne veut un ticket. Lorsque le cinéma ouvre il n'y a pas d'argent dans la caisse. quelle est la probabilité qu'aucun d'entre eux n'ait à attendre pour la monnaie ?

Super intéressant.
J'étais sûre que j'avais traité un truc semblable, je l'ai finalement retrouvé : (proposé par kakille il y a un bail)

On se place dans un repère orthonormé. Une souris, placée initialement en $ (0;0) $ , cherche à atteindre un fromage, placé en $ (a;b) $ avec a et b dans N. Elle ne peut que se déplacer, à chaque étape de son chemin, d'une unité vers la droite, ou vers le haut.
Combien de chemins peut-elle emprunter ?

Si $ a,b $ sont tels que $ a\geq b $, combien de chemins restant intégralement dans l'ensemble $ x\geq y $ mènent de $ (0,0) $ à $ (a,b) $ ?

Je changerai pas de méthode de résolution, en fait c'est la même situation avec un peu d'imagination
Précision : la première question nécessite que $ n\ge m $... la troisième nécessite que $ n \ge 2m $. Sinon ils vont forcément attendre !

SPOILER:

a) Modélisons la situation par une courbe ne passant que par des points de coordonnées entières : M représente les personnes ayant des billets de 10, N les personnes ayant des billets de 5. Quand on rencontre un N dans la série, la courbe d'étude passe de la case (a;b) à la case (a+1;b+1), quand on rencontre un M, elle passe de (a;b) à (a+1;b-1). Ainsi, la courbe part de (0;0), c'est le début de la file, a une longueur égale à m+n le nombre de personnes (une diagonale du carré d'unité du repère orthonormé dans lequel on se place équivalent à 1 unité de segment ici (et non à $ \sqrt{2} $, j'espère me faire comprendre ), monte n fois, descend m fois et de ce fait, s'arrête au point (m+n; n-m). La contrainte imposée dans l'exercice se résume au fait que le nombre total de M rencontré entre le début de la file et une personne déterminée ne doit jamais être supérieur au nombre de N rencontré dans cette même portion de file. Pour notre graphe, cela se traduit pas le fait que la courbe ne doit jamais passer par des points d'ordonnée (entière donc) strictement négative. Combien peut-on dénombrer de courbes passant un moment ou à un autre par des points d'ordonnées strictement négative ? Ce nombre est en fait égal au nombre de courbes allant de (1;-1) à (m+n;m-n). On peut en effet penser une telle association par un principe de réflexion (géométriquement c'est plus facile à comprendre). On a donc m-1 mouvements vers le bas à placer dans m+n "pas" de la courbe, soit $ \binom{m+n}{m-1} $ chemins passant par au moins un point d'ordonnée strictement négative. De plus, le nombre total de manières d'agencer des personnes dans la queue est de placer tous les M dans les M+N espaces, puis de remplir les trous restants avec des N, soit $ \binom{m+n}{m} $ manières.
En ce sens, il y a $ \binom{m+n}{m} - \binom{m+n}{m-1} $ manières de placer les gens dans la queue pour qu'il n'y ait pas d'attente, soit une probabilité de $ p=1- \frac{\binom{m+n}{m-1}}{\binom{m+n}{m}} $ de ne pas avoir d'attente.

b) Même modélisation, sauf que la courbe part du point (0;p). Même contrainte, même principe de réflexion : il ne faut pas que cette courbe passe par des points d'ordonnée strictement négative. Or le nombre de courbes partant de (0;p) et passant par des points d'ordonnée négative est égal au nombre de courbes partant de (p+1;-1-p) et arrivant à (m+n;n-m) : m-p-1 mouvements vers le haut à placer dans m+n mouvements soit $ \binom{m+n}{m-p-1} $ chemins inadéquats d'où $ \binom{m+n}{n} - \binom{m+n}{m-p-1} $ manières d'arranger la file sans attente, d'où $ p=1-\frac{\binom{m+n}{m-p-1}}{\binom{m+n}{m}} $.

c) Même modélisation, sauf qu'il ne faut pas que le nombre de personnes M rencontrées soit supérieur strictement au double du nombre de N rencontré. Donc le nombre d'arrangements de la file inadéquats ici est égal au double du nombre d'arrangements inadéquats en a) : donc $ 2\binom{m+n}{m-1} $ arrangements inadéquats ici, soit $ \binom{m+n}{m}-2\binom{m+n}{m-1} $ arrangements adéquats.
Donc une probabilité $ p=1-2\frac{\binom{m+n}{m-1}}{\binom{m+n}{n}} $ qu'il n'y ait pas d'attente.

[mathophilie]

Wallissen, pas d'indications au bout de deux heures stp... J'ai même pas eu le temps de regarder les exos en question...
Au moins 1 jour d'attente pour indications, sauf demande particulière !
Surtout qu'ils ont pas l'air inaccessibles.

Bon allez tchouss, je vais regarder une série !

[wallissen]

Bah j'ai juste donné des resultats heureusement
Il faut les démontrer Essaie de resister aussi à l'envie de cliquer sur l'indication avant un jour

Je vais essayer de lire ta résolution pour les tickets de cinéma plus tard (surement demain ) Je mate une série aussi

[mathophilie]

Problème de Cayley
Combien y a-t-il de polygones convexes de k cotés dont les sommets coïncident avec des sommets et les cotés avec des diagonales d'un polygone convexe donné de n cotés ?

Une proposition :

SPOILER:

On considère un polygone convexe à n côtés et on se fixe un sommet de départ D. Nous reste à choisir $ (k-1) $ autres sommets permettant de former un polygone à k côtés avec des diagonales d'un polygone convexe donné de n cotés. Cette dernière contrainte nous indique que deux sommets choisis pour former le petit polygone ne peuvent être consécutifs (autrement ce n'est plus une diagonale mais un côté du grand polygone). Il faut donc laisser au moins 1 point entre deux sommets choisis, c'est à dire k sommets qu'on ne peut pas choisir : en soustrayant également le point de départ D, on a donc $ \binom{n-k-1}{k-1} $ manières de choisir les sommets différents de D du petit polygone. On a de plus n choix possibles pour D soit $ n\binom{n-k-1}{k-1} $ polygones formés :Toutefois, avec cette méthode, apparaissent des redondances : puisque le tracé d'un polygone à k côtés peut se faire selon k points de départs différents, on obtient avec la précédente k fois le même polygone : pour déterminer le nombre de polygones distincts qui peuvent être tracés, il suffit de diviser ce nombre par k, d'où $ \frac{n}{k}\binom{n-k-1}{k-1} $ polygônes convexes à k côtés dont les sommets coïncident avec des sommets et les cotés avec des diagonales d'un polygone convexe donné de n cotés.

a) Un fumeur achète deux boites d'allumettes et les met dans sa poche.
Chaque fois qu’il allume sa cigarette, il prend au hasard une allumette dans l’une des boîtes. Donc, au bout d’un certain temps,
il prend une boite au hasard, l'ouvre et remarque qu'elle est vide (On suppose qu'il se rend compte qu'une boite est vide qu'au moment où il veut prendre
une allumette et qu'il ne le peut pas et non au moment de prendre la dernière allumette ).

On suppose également que les deux boites contiennent initialement le même nombre n d’allumettes.
Quelle est la probabilité qu'il reste alors k allumettes dans une boite dès lors qu'il remarque que l'autre est vide ? (ici $ 0 \leq k \leq n $ )

b) En utilisant le résultat précédent, évaluer la somme

$ \binom{2n}{n} + 2\binom{2n-1}{n} + 2^2\binom{2n-2}{n} + ...+ 2^n\binom{n}{n} $

Une proposition :

SPOILER:

a) Avant d'arriver à la k-eme cigarette (i.e d'essayer d'attraper une cigarette dans le paquet vide tandis que l'autre contient k cigarettes), le fumeur aura choisit $ 2n-k $ cigarette (n par paquet, 2 paquets). A chaque fois qu'il choisit une cigarette, il a deux options : soit le paquet 1, soit le paquet 2, donc $ 2^{2n-k} $ manières de choisir les cigarettes dans les différents paquets avant d'arriver à la k-ème. Maintenant combien de manières de vider 1 paquet avant de s'en rendre compte ? Il faut prendre n cigarettes d'un même paquet parmi 2n-k cigarettes, soit $ \binom{2n-k}{n} $, d'où une probabilité $ p=\frac{\binom{2n-k}{n}}{2^{2n-k}} $.

b) $ \binom{2n}{n} + 2\binom{2n-1}{n} + 2^2\binom{2n-2}{n} + ...+ 2^n\binom{n}{n} = 2^{2n}\sum_{k=0}^n\frac{\binom{2n-k}{n}}{2^{2n-k}} $. En notant $ p_k $ la probabilité qu'il reste k cigarettes dans le paquet non vide dans la situation précédente, on a donc : $ \binom{2n}{n} + 2\binom{2n-1}{n} + 2^2\binom{2n-2}{n} + ...+ 2^n\binom{n}{n} = 2^{2n}\sum_{k=0}^n p_k $. Or l'intersection des évènements "Il reste 1 allumette",, "Il reste 2 allumettes", "Il reste n allumettes" décrit l'ensemble des situations possibles pour le fumeur, donc $ \sum_{k=0}^n p_k = 1 $, d'où $ \binom{2n}{n} + 2\binom{2n-1}{n} + 2^2\binom{2n-2}{n} + ...+ 2^n\binom{n}{n} = 2^{2n} $

[Mykadeau]

Ah bah non mathophilie, pour une fois qu'une solution me parrasait évidente (les allumettes) et que je me disais que je mettrais la solution le lendemain... Tu pourrais pas rester avec les trucs totalement HP de ton côté, et laisser les exos abordables pour les gens comme moi?

[Siméon]

À propos de l’Exercice 567.1,

OMG j'aurais pas trouvé... Merci. Mais est-on censé maitriser les sommations doubles ? (est-on supposé tomber dessus déjà )

Le calcul fait effectivement apparaître deux sommations, mais il ne faut pas se laisser impressionner. En revanche il vaut mieux se rappeler que l'addition est commutative, de sorte que $ \sum_{a \in A}\sum_{b \in B} f(a,b) = \sum_{b\in B}\sum_{a\in A} f(a,b) $ quels que soient $ A,B $ finis et $ f \colon A\times B \to \mathbb C $.

[wallissen]

Ah bah non mathophilie, pour une fois qu'une solution me parrasait évidente (les allumettes) et que je me disais que je mettrais la solution le lendemain... Tu pourrais pas rester avec les trucs totalement HP de ton côté, et laisser les exos abordables pour les gens comme moi?

Tu peux aussi proposer une solution indépendamment de ce qu'elle fait. D'où l'intérêt de cacher avec le bouton spoiler justement

Concernant ce problème, il a été proposé par un mathématicien et grand fumeur du nom de Stefan Banach. On peut le retrouver sur le net (du moins la première question) sous différentes formes et sous le nom de Problème des allumettes de Banach.

Sinon mathophilie, tes solutions me semblent correctes, enfin faut que les autres approuvent aussi , à part peut être un détail sans importance : tu confonds allumettes et cigarettes

[wallissen]

Exo 1

Une urne contient 2n boules soigneusement mélangés, dont n blanches et n noires.
a) Quelle est la probabilité que chacune de n personnes aux yeux bandés tirant deux boules
à partir de l'urne, puissent tirer des boules de couleurs différentes? (Les boules tirées ne sont pas remises dans l'urne.)

b) Dans les mêmes conditions, quelle est la probabilité que chacune des n personnes tire deux boules de la même couleur?

Question subsidiaire (hors programme) On suppose que n est assez grand, écrire alors les résultats obtenus de façon plus convenable à l'aide de la formule de Stirling $ n! \sim n^ne^{-n}\sqrt{2\pi n} $

Exo2

Un disque est divisé en p secteurs égaux, où p est un nombre premier.

a) De combien de façons différentes ces p secteurs peuvent être colorés avec n couleurs données, sachant que deux coleurs
sont considérées comme différentes que lorsque aucune des deux ne puisse être obtenue à partir de l'autre en faisant tourner le cercle ?

(Remarque Il n'est pas necessaire que les différents secteurs soient de couleurs différentes ou même que deux secteurs adjacents
soient de différentes couleurs.)

b) En déduire le petit théorème de Fermat : si $ p $ est un nombre premier, alors $ n^p - n $ est divisible par $ p $ pour tout $ n $.

[wallissen]

Un plus difficile que les deux précédents.

Montrer que la probabilité qu'un nombre entier soit premier est nulle.

En d'autres termes, montrer que, si $ \pi(N) $ désigne l'ensemble des nombres premiers inférieurs ou égaux à N ( N étant un entier ) alors

$ lim_{n \to +\infty}\frac{\pi(N)}{N} = 0 $

Sans utiliser de résultat Hors programme bien sûr