Suite d’énigmes et temps de parcours minimal

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2017 | Académie : France métropolitaine


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 = (anbn) 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 :

an=0,8×0,75n+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.