Exercices d’aprofondissement

Exercices d’aprofondissement ============================ ## 99 p 303 ### 1. On choisit comme unité 50cm, le côté d’un carreau. La longeur de la salle est de 10m. Donc il y a 10m / 50cm carreaux sur une longeur = 20 La largeur est de 1.5m. Donc il y a 1.5m / 50cm carreaux sur une largeur= 3 On peut donc disposer 20×3 = 60 carreaux sur toute la surface de la pièce. Les couleurs de tous les carreaux étant indépendantes, l’ensemble des carrelages correspond à $$\{rouge, bleu, jaune\}^{60}$$ Le cardinal de cet ensemble est $3^{60}$ ### 2. On appelle un carelage estéthique un carrelage dont aucun carré adjacent n’a la même couleur. **a)** On veut déterminer $u_1$, c’est à dire le nombre de carrelages esthétiques pour la première rangée. On choist d’abord la couleur du carré central, qu’on note $c$ ``` ⬜🟫⬜ 3 possibilités pour le carré central ``` Ensuite, on choisit la couleur du premier carré (2 possibilités, car ça ne peut pas être $x$) et le dernier (2 possibilités également). On trouve $u_1 = 3\times 2 \times 2 = 12$ **b)** Erreur dans l’énnoncé: la suite n’est pas géométrique !!! On cherche à déterminer l’évolution du nombre de possibilités quand on rajoute une rangée de 3 carrés au carrelage total. On peut d’abbord lister toutes les rangées possibles: ``` 🟥🟦🟥 🟥🟦🟨 🟥🟨🟦 🟥🟨🟥 🟦🟨🟥 🟦🟨🟦 🟦🟥🟨 🟦🟥🟦 🟨🟦🟥 🟨🟦🟨 🟨🟥🟦 🟨🟥🟨 ``` #### Remarque: La nème rangée ne peut être que de 2 types: - la nème rangée est de trois couleurs différentes `ABC` Si la nème rangée est de la forme `ABC`, on peut regarder lesquelles des 12 rangées possible de la question précédente fonctionne: ``` ABC ABC ABC ABC ABC ABC ABC ABC ABC ABC ABC ABC ABA ABC ACA ACB BAB BAC BCA BCB CAB CAC CBA CBC ^^ ^^^ ^ ^ ^ ^ ^ ^ ``` On trouve 4 façons de compléter le carrelage dans le cas où la rangée est de la forme `ABC`. Parmi ces rangées, deux sont de 3 couleurs différentes `BCA CAB` et deux sont de 2 couleurs différentes: `BAB BCB` - la nème rangée est de deux couleurs différentes `ABA` Si la dernière rangée est de la forme `ABA`, on peut essayer de la compléter de la même façon: ``` ABA ABA ABA ABA ABA ABA ABA ABA ABA ABA ABA ABA ABA ABC ACA ACB BAB BAC BCA BCB CAB CAC CBA CBC ^^^ ^^ ^ ^ ^ ^ ^ ``` On trouve cette fois 5 façons de compléter le carrelage dans le cas où la rangée est de la forme `ABA`. Parmi ces rangées, deux sont de 3 couleurs différentes `BCA CAB` et trois sont de 2 couleurs différentes: `BAB BCB CAC` On note $(v_n)$ le nombre de façons de créer un carrelage de longueur $n$ dont la dernière rangée a 3 couleurs différentes On note $(w_n)$ le nombre de façons de créer un carrelage de longueur $n$ dont la dernière rangée a deux couleurs différentes. On a $u_n = v_n + w_n$ On sait qu’après une rangée tricolore, on peut ajouter une rangée parmi 2 rangées tricolores et 2 rangées bicolores. Et on sait qu’après une rangée bicolore, on peut ajouter une rangée parmi 2 rangées tricolores et 3 rangées bicolores. Propriétés pour tout $n \in [\![1; +\infty[\![$ $$ \begin{cases} v_{n+1} = 2\cdot v_n + 2 \cdot w_n\\ \\ w_{n+1} = 2\cdot v_n + 3 \cdot w_n \end{cases} $$ Avec comme valeur initiales $$ \begin{cases} v_0 = 6 \\ w_0 = 6 \end{cases} $$ Enfin, on sait que $$u_n = v_n + w_n$$ **c) calcul pour la pièce entière** Programme python: ```py def carrelage(n: int) -> int: assert n>=1 v = w = 6 for _ in range(1, n): v_copie = v v = 2*v_copie + 2*w w = 2*v_copie + 3*w return v + w ``` Avec `carrelage(20)`, on obtient **39426691159122** Il y a donc **39426691159122** carrelages esthetiques possibles dans cette salle. ## 77 p 299 ### 1. - $n = 2$ l’ensemble $E$ est donc $\{1, 2\}$ L’ensemble des permutations de $E$ est : $$\{(1, 2), (2, 1)\}$$ Mais il contient $E$, l’ensemble original. L’ensemble des dérangements est $$\{(1, 2)\}$$ Donc $D_2 = 1$ - $n = 3$ l’ensemble $E$ est donc $\{1, 2, 3\}$ L’ensemble des permutations de $E$ est : $$\{(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)\}$$ Si on ne garde que les triplets sans élément commun avec $(1, 2, 3)$, on obtient $$\{(2, 3, 1), (3, 1, 2)\}$$ Donc $D_3 = 2$ ### 2. On pose $n = 4$ **a)** le quadruplet original est $(1, 2, 3, 4)$ Le premier élément d’un dérangement de E peut être 2, 3 ou 4. **b)** Le dérangement commence par $(2, 1, …)$ Il n’y a que deux permutations possibles: - $(2, 1, 3, 4)$ : ce n’est pas un dérangement valide car 3 et 4 sont à la même place - $(2, 1, 4, 3)$ : c’est un dérangement valide Il existe donc un seul dérangement de $E$ commençant par (2, 1…) **c)** On cherche tous les dérangements de $E$ de la forme $(2, a, b, c)$ avec $a\not= 1$ Deux cas pour a: - $a = 3$ --- Seul dérangement dans ce cas : $(2, 3, 4, 1)$ - $a = 4$ --- Seul dérangement dans ce cas : $(2, 4, 3, 1)$ On a seulement 2 dérangements. **d)** Trois dérangements de $E$ commencent par 2 On peut justifier qu’autant de dérangements de $E$ commenceront par un 3 et un 4. [pas le temps de justifier, mais on peut simplement permuter le quadruplet original pour voir que la situation obtenue est indiscernable] Donc $D_4 = 3\times3 = 9$ ### 3. **a)** $\begin{array}{cl} D_5 &= (5-1)(D_3 + D_4)\\ &= 4(2 + 9)\\ &= 44 \end{array}$ **b)** ```py def derangement(n: int): assert n>=3 if n == 3: return 2 if n == 4: return 9 return (n-1) * (derangement(n-1) + derangement(n-2)) ``` ### 4. On s’intéresse à l’ensemble des permutations d’un ensemble de dix enveloppes. Le cardinal de cet ensemble est de $10!$ **a)** On appel cet évenement A Tous les courriers arrivent à la bonne adresse pour une seule des permutations. Donc $P(A) = \dfrac{1}{10!}$ **b)** On appel cet évenement B Aucun des courriers n’arrivent à la bonne adresse si la permutation est un dérangement de l’ensemble des enveloppes. Donc $P(B) =\dfrac{D_{10}}{10!} = \dfrac{1334961}{3628800} \approx 0.368$ ## 100 p 303 On appelle $F$ l’ensemble des coureuses. On a $$\text{card}(N) = 100$$ ### 1. Le nombre de groupes différents correspond au cardinal de l’ensemble des combinaisons de 8 éléments de $F$ Ce qui fait $\displaystyle{100\choose8}$ ### 2. Programme original: ```py from random import randint def controle(): L = [] D = [] for k in range(100): L.append(k) for i in range(8): x = L.pop(randint(0, 99-i)) D.append(x) return L ``` Le programme ne renvoie pas la bonne liste. Programme corrigé et réécrit: ```py from random import randint def controle(): L = list(range(100)) return [L.pop(randint(0, 99-i) for i in range(8))] ``` ### 3. On note $C$ l’évenement «la coureuse s’est fait controller à cette étape» **a)** $$P(C) = \dfrac{8}{100}$$ **b)** On répète une épreuve de Bernouilli 6 fois de suite. Le rombre d’issues possibles est de $2^6$ À chaque évenement, le nombre de branches est multiplié par deux. On part de 2 branches, et on les doubles 5 fois. $$\sum_{n=1}^{6} 2^n = \dfrac{2^1 - 2^{n+1}}{1-2} = 126$$ On a donc 126 branches au total. **c)** Soit A l’évenement: «la coureuse a été controlée exactement cinq fois» On a là une épreuve de Bernouilli répétée 6 fois. Donc ${6\choose5} = 6$ issues mènent à 5 succès. On peut aussi voir que l’évenement se réalise quand la coureuse n’a pas été téstée pendant une unique étape. Elle peut ne pas avoir été testé au tour 1, 2, 3, 4, 5 ou 6. Cela fait bien 6 issues. Donc $$P(A) = \dfrac{6}{2^6} \approx 0.09$$ **d)** [probabilité qu’une coureuse ne soit jamais controllée] - probabilité qu’elle ne soit pas controllée dans une étape: $P(\bar{C}) = 1-P(C) = \dfrac{92}{100}$ - Il n'existe qu'un chemin dans l'arbre pour qu’elle ne soit controllée à aucune étape. La probabilité d'être controlé à aucune étape est donc: $P(\bar{C})^6 = \left(\dfrac{92}{100}\right)^6 \approx 0.60$ ### 4. On note l'évenement D être sur le podimium et X, Y, Z être respectivement premier deuxième et troisième $P(D)=P(X)+P(Y)+P(Z)=\dfrac{1}{100}\times 3=\dfrac{3}{100}$ Il y a donc 3 chances sur 100 de choisir quelqu'un qui sera sur le podium ## 92 p 301 #### Lemme 1 On veut prouver $${n\choose k-1} + {n \choose k} = {n+1 \choose k}$$ On part de la définition du coefficient binomial $${n \choose k} = \dfrac{n!}{k!(n-k)!}$$ Donc $$ \begin{array}{cl} \displaystyle{n\choose k-1} + {n \choose k} &= \dfrac{n!}{(k-1)!(n-k+1)!} + \dfrac{n!}{k!(n-k)!}\\[2ex] &= \dfrac{n!\cdot k}{k!(n-k+1)!} + \dfrac{n!(n-k+1)}{k!(n-k+1)!}\\[2ex] &= \dfrac{n!((k)+(n-k+1))}{k!(n-k+1)!}\\[1ex] &= \dfrac{n!(n+1)}{k!(n-k+1)!}\\[2ex] &= \dfrac{(n+1)!}{k!(n+1-k)!}\\[2ex] &= \displaystyle {n+1 \choose k} \end{array} $$ ### démonstration 1: Formule de Pascal $$(a+b)^n = \sum_{k=0}^n {n \choose k}a^{n-k} \cdot b^k$$ On le prouve par récurrence. - Initialisation $$(a+b)^0 = 1 = {0 \choose 0}$$ - Récurence Soit $n$ un entier naturel On suppose $(a+b)^n = \displaystyle \sum_{k=0}^n {n \choose k}a^{n-k} \cdot b^k$ on veut déterminer $(a+b)^{n+1}$ $$\begin{array}{cl} (a+b)^{n+1} &= a(a+b)^n + b(a+b)^n\\[1ex] &= a\displaystyle \sum_{k=0}^n {n \choose k}a^{n-k} \cdot b^k + b \displaystyle \sum_{k=0}^n {n \choose k}a^{n-k} \cdot b^k\\[2ex] &= \displaystyle \sum_{k=0}^n {n \choose k}a^{n-k+1} \cdot b^k + \displaystyle \sum_{k=0}^n {n \choose k}a^{n-k} \cdot b^{k+1}\\[2ex] &= \displaystyle \sum_{k=0}^n {n \choose k}a^{n-k+1} \cdot b^k + \displaystyle \sum_{k=1}^{n+1} {n \choose k-1}a^{n-k+1} \cdot b^{k}\\[2ex] &= \displaystyle {n\choose 0} a^{n+1} + \displaystyle \sum_{k=1}^n \left({n \choose k} + {n \choose k-1}\right )a^{n-k+1} \cdot b^k + {n\choose n} b^{n+1}\\[2ex] \end{array}$$ Or, ${n\choose 0} = 1 = {n+1\choose 0}$ et ${n\choose n} = 1 = {n+1\choose n+1}$ $$\begin{array}{cl} (a+b)^{n+1} &= \displaystyle {n+1\choose 0} a^{n+1} + \displaystyle \sum_{k=1}^n {n+1 \choose k}a^{n-k+1} \cdot b^k + {n+1\choose n+1} b^{n+1}\\[2ex] &= \displaystyle \sum_{k=0}^{n+1} {n \choose k}a^{n+1-k} \cdot b^k \end{array}$$ On a bien $(a+b)^n = \displaystyle \sum_{k=0}^n {n \choose k}a^{n-k} \cdot b^k \implies \displaystyle \sum_{k=0}^{n+1} {n \choose k}a^{n+1-k} \cdot b^k$ - récurence: Propriété initialisée au rang 0 et héréditaire. Par récurence, on a démontré la formule de Pascal. ### 1 On définit la fonction $f$ sur $\mathbb{R}$ $n$ est un entier naturel. $$f(x) = (1+x)^n$$ $$(1+x)^n = \displaystyle \sum_{k=0}^n {n \choose k}1\cdot x^k$$ On peut utiliser la formule de la somme: $$f’(x) = \sum_{k=0}^n {n \choose k}k\cdot x^{k-1}$$ On peut également utiliser la propriété de $(g^n)’$ $$g^n = n\cdot g^{n-1} g’$$ $$f’(x) = n\cdot (1+x)^{n-1}\cdot 1$$ On obtient $$n\cdot (1+x)^{n-1} = \sum_{k=0}^n {n \choose k}k\cdot x^{k-1}$$ ### 2. On peut évaluer cette expression avec $x=1$ $$n\cdot (1+1)^{n-1} = \sum_{k=0}^n {n \choose k}k\cdot 1^{k-1}$$ Le premier terme de cette somme est $0 \times {n \choose 0} = 0$, on peut donc l’ignorer. En réarangeant, on trouve $$\sum_{k=1}^n k\cdot {n \choose k} = n \times 2^{n-1}$$