Graphes probabilistes

Ens. de spécialité

matT_1706_07_06C

France métropolitaine • Juin 2017

Exercice 2 • 5 points • ⏱ 45 min

Suite d'énigmes et temps de parcours minimal

Les thèmes clés

Graphe probabiliste • Plus court chemin.

partie a

Dans un jeu vidéo, une suite d'énigmes est proposée au joueur. Ces énigmes sont classées en deux catégories : les énigmes de catégorie A sont les énigmes faciles les énigmes de catégorie B sont les énigmes difficiles.

Le choix des énigmes successives est aléatoire et vérifie les conditions suivantes :

la première énigme est facile

si une énigme est facile, la probabilité que la suivante soit difficile est égale à 0,15

si une énigme est difficile, la probabilité que la suivante soit facile est égale à 0,1.

Pour n ≥ 1, on note :

an la probabilité que l'énigme numéro n soit facile (de catégorie A)

bn la probabilité que l'énigme numéro n soit difficile (de catégorie B)

Pn = (an bn) l'état probabiliste pour l'énigme numéro n.

▶ 1. Donner la matrice P1. (0,25 point)

▶ 2. Représenter la situation par un graphe probabiliste de sommets A et B. (0,75 point)

▶ 3. Écrire la matrice M associée à ce graphe, puis donner la matrice ligne P2. (0,5 point)

▶ 4. Sachant que, pour tout entier n ≥ 1, on a an + bn = 1, montrer que, pour tout entier n ≥ 1, on a :

an+1 = 0,75 an + 0,1. (0,5 point)

▶ 5. Pour tout entier naturel n ≥ 1, on pose vn = an - 0,4.

a) Montrer que (vn) est une suite géométrique dont on précisera le premier terme et la raison. (0,5 point)

b) Exprimer vn en fonction de n, puis montrer que pour tout entier n ≥ 1 :

$a_{n} = 0,8 \times {0,75}^{n} + 0,4 .$ (0,75 point)

c) Préciser la limite de la suite (vn). (0,25 point)

d) Une revue spécialisée dans les jeux vidéo indique que, plus le joueur évolue dans le jeu, plus il risque d'avoir à résoudre des énigmes difficiles. Que penser de cette analyse ? (0,5 point)

partie b

Une des énigmes consiste à réaliser un parcours en le minimum de temps. Le graphe suivant schématise le parcours. L'étiquette de chaque arête indique le temps de parcours en minute entre les deux sommets qu'elle relie. Par exemple, le temps de parcours de C vers D, ou de D à C, est égal à quatre minutes.

matT_1706_07_00C_01

Quel chemin le joueur doit-il prendre pour aller de A à G en minimisant son temps de parcours ? Expliquer la démarche utilisée. (1 point)

Les clés du sujet

Partie A

▶ 1. P1 donne l'état probabiliste pour l'énigme numéro 1.

▶ 2. Sur un graphe probabiliste, la somme des probabilités portées par les arêtes issues d'un même sommet est égale à 1.

▶ 5. d) Considérez le sens de variation de la suite (bn).

Partie B

Utilisez l'algorithme de Dijkstra.

Corrigé

partie A

▶ 1. Donner l'état initial d'un graphe probabiliste

Puisqu'on sait que la première énigme est facile :

$P_{1} = (1 0)$

▶ 2. Représenter une situation par un graphe probabiliste à deux sommets

La situation peut être représentée par le graphe suivant :

matT_1706_07_00C_03

▶ 3. Déterminer la matrice associée à un graphe probabiliste

La matrice associée au graphe probabiliste précédent est :

$M = (\begin{matrix} 0,85 & 0,15 \\ 0,1 & 0,9 \end{matrix})$

P2 = P1 × M, d'où :

$P_{2} = (1 0) (\begin{matrix} 0,85 & 0,15 \\ 0,1 & 0,9 \end{matrix})$

$P_{2} = (0,85 0,15)$

▶ 4. Établir une relation entre deux termes consécutifs d'une suite

Pour tout entier n ≥ 1, on a Pn+1 = Pn × M, donc :

${\begin{cases} a_{n + 1} = 0,85 a_{n} + 0,1 b_{n} \\ b_{n + 1} = 0,15 a_{n} + 0,9 b_{n} \end{cases}$

Puisque an + bn = 1, on a bn = 1 - an.

En remplaçant dans l'égalité an+1 = 0,85 an + 0,1 bn, on a successivement :

an+1 = 0,85 an + 0,1 (1 - an)

an+1 = 0,85 an + 0,1 - 0,1 an

$a_{n + 1} = 0,75 a_{n} + 0,1$

▶ 5. a) Montrer qu'une suite est une suite géométrique

Pour tout entier naturel n ≥ 1 :

vn+1 = an+1 - 0,4

vn+1 = 0,75 an + 0,1 - 0,4

$v_{n + 1} = 0,75 (v_{n} + 0,4) - 0,3$

vn+1 = 0,75 vn.

Donc $(v_{n})$ est une suite géométrique de raison 0,75.

Son premier terme est v1 = a1 - 0,4 = 1 - 0,4 = 0,6.

b) Donner l'expression du terme général d'une suite géométrique et d'une suite associée

Pour tout entier naturel n : $v_{n} = v_{1} \times q^{n - 1}$

où q est la raison de la suite géométrique (vn). D'où :

$v_{n} = 0,6 \times {0,75}^{n - 1}$

$a_{n} = v_{n} + 0,4 = 0,6 \times {0,75}^{n - 1} + 0,4$ .

Or 0,6 = 0,8 × 0,75, donc :

$a_{n} = 0,8 \times 0,75 \times {0,75}^{n - 1} + 0,4$ ,

$a_{n} = 0,8 \times {0,75}^{n} + 0,4$

c) Donner la limite d'une suite

0 0,75 1, donc :

$\lim_{n \to + ∞} v_{n} = 0 .$

d) Interpréter le sens de variation d'une suite

La suite (vn) est une suite géométrique de premier terme positif et de raison strictement comprise entre 0 et 1, donc elle est décroissante.

On en déduit que la suite (an) est également décroissante et que la suite (bn) est croissante.

Donc, plus $n$ augmente, plus $b_{n}$ augmente, ce qui signifie que plus le joueur évolue dans le jeu, plus la probabilité d'avoir à résoudre une énigme difficile augmente : l'analyse proposée est donc exacte.

partie b

Déterminer sur un graphe un chemin de longueur minimale

Pour déterminer le chemin que le joueur doit prendre pour aller de A à G en minimisant son temps de parcours, on utilise l'algorithme de Dijkstra qui peut être résumé par le tableau suivant :

A	B	C	D	E	F	G
0	∞	∞	∞	∞	∞	∞
	2 A	6 A	10 A	∞	∞	∞	A (0)
		5 B	10 A	∞	∞	17 B	B (2)
			9 C	14 C	∞	17 B	C (5)
				12 D	∞	17 B	D (9)
					13 E	16 E	E (12)
						16 E	F (13)

On en déduit que le chemin qui permet d'aller en un temps minimum de A à G est :

$A – B – C – D – E – G$

La durée de ce parcours est 16 minutes.

Suite d'énigmes et temps de parcours minimal

partie a

partie b

Partie A

Partie B

partie A

▶ 1. Donner l'état initial d'un graphe probabiliste

▶ 2. Représenter une situation par un graphe probabiliste à deux sommets

▶ 3. Déterminer la matrice associée à un graphe probabiliste

▶ 4. Établir une relation entre deux termes consécutifs d'une suite

▶ 5. a) Montrer qu'une suite est une suite géométrique

b) Donner l'expression du terme général d'une suite géométrique et d'une suite associée

c) Donner la limite d'une suite

d) Interpréter le sens de variation d'une suite

partie b

Déterminer sur un graphe un chemin de longueur minimale

Pour lire la suite