Jeu vidéo, trajets sur un graphe, probabilité de gagner une partie

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2014 | Académie : Antilles, Guyane

 

Antilles, Guyane • Septembre 2014

Exercice 2 • 5 points

Jeu vidéo, trajets sur un graphe, probabilité de gagner une partie

Dans le jeu vidéo « Save the princess », l’objectif est d’aller délivrer une princesse tout en récoltant des trésors situés dans les couloirs du château.

Le plan du château est représenté par le graphe pondéré ci-dessous. Les sommets de ce graphe représentent les salles et les arêtes représentent les couloirs reliant les salles entre elles.

matT_1409_04_00C_03

PARTIE A

1. Le joueur se trouve dans la salle A. Il décide de visiter chacun des couloirs afin de trouver le plus de trésors possibles. Peut-il trouver un trajet lui permettant de passer par tous les couloirs une et une seule fois ? Justifier la réponse. (0,5 point)

2. Dans chaque couloir se trouve un certain nombre de monstres. Les étiquettes du graphe pondéré donnent le nombre de monstres présents dans les couloirs.

Le joueur souhaite, en partant de A, rejoindre la princesse enfermée dans la salle G.

Déterminer le chemin qu’il doit prendre pour délivrer la princesse en combattant le moins de monstres possible.

Combien de monstres aurait-il alors à affronter ? (1,5 point)

PARTIE B

Pour un joueur régulier, on estime que :

s’il gagne une partie, la probabilité qu’il gagne la partie suivante est 0,7 ;

s’il perd une partie, la probabilité qu’il perde la partie suivante est 0,6.

On note 125717-Eqn34l’état probabiliste lors de la 125717-Eqn35-ième partie où 125717-Eqn36 désigne la probabilité que la partie soit gagnée et 125717-Eqn37 celle que la partie soit perdue.

1. Traduire les données de l’énoncé par un graphe probabiliste. On nommera les sommets U (pour la partie gagnée) et V (pour la partie perdue). (0,75 point)

2. En déduire la matrice de transition en considérant les sommets dans l’ordre U, V. (0,75 point)

3. On suppose la première partie perdue, l’état probabiliste initial est donc 125717-Eqn38

Montrer que la probabilité que le joueur gagne la 3e partie est 0,52. (0,75 point)

4. Déterminer la probabilité que le joueur gagne la 15e partie. Arrondir le résultat au centième. (0,75 point)

Les clés du sujet

Durée conseillée : 45 minutes

Les thèmes en jeu

Chaîne eulérienne • Plus court chemin • Graphe probabiliste • Probabilité conditionnelle

Les conseils du correcteur

Partie A

1. Utilisez le théorème d’Euler.

2. Utilisez l’algorithme de Dijkstra.

Partie B

1. Dans un graphe probabiliste, les arêtes issues d’un même sommet sont pondérées par des probabilités conditionnelles de somme égale à 1.

3. et 4. D’après le cours, pour tout entier naturel non nul 125717-Eqn83, 125717-Eqn84.

Corrigé

Corrigé

PARTIE A

1. Déterminer si un graphe possède une chaîne eulérienne

On détermine le degré de chaque sommet du graphe ; on résume les résultats dans un tableau :

Sommet

A

B

C

D

E

F

G

Degré

3

2

3

3

3

5

3

Le graphe a 6 sommets de degré impair, donc d’après le théorème d’Euler, le graphe ne possède aucune chaîne eulérienne ; le joueur ne peut donc pas trouver un trajet lui permettant de passer par tous les couloirs une fois et une seule.

2. Déterminer sur un graphe un chemin de « poids » minimal partant d’un sommet donné

On utilise l’algorithme de Dijkstra pour déterminer un chemin de A à G correspondant au nombre minimal de monstres rencontrés.

A

B

C

D

E

F

G

0

5 (A)

7 (A)

3 (A)

 

5 (A)

5 (F)

4 (F)

7 (F)

3 (A)

22 (F)

 

5 (A)

5 (F)

4 (F)

7 (F)

 

22 (F)

 

5 (A)

5 (F)

 

7 (F)

 

22 (F)

   

5 (F)

 

7 (F)

 

19 (C)

       

7 (F)

 

15 (E)

Pour aller de A à G en rencontrant le moins de monstres possibles, le joueur doit suivre le chemin :

125717-Eqn156

125717-Eqn157. Le joueur devra affronter 15 monstres.

PARTIE B

1. Traduire les données d’un énoncé par un graphe probabiliste

matT_1409_04_00C_06

2. Déterminer la matrice de transition d’un graphe probabiliste

Pour tout entier naturel 125717-Eqn158 non nul :

125717-Eqn159

Donc :

125717-Eqn160.

La matrice de transition du graphe est :

125717-Eqn161

3. Déterminer un état probabiliste

L’état probabiliste lors de la 3e partie est :

125717-Eqn162

La probabilité que le joueur gagne la troisième partie est donc égale à 0,52.

4. Déterminer un état probabiliste

De même, l’état probabiliste lors de la 15e partie est :

125717-Eqn163

La probabilité que le joueur gagne la 15e partie est 125717-Eqn164

D’après les résultats précédents, 125717-Eqn165 est égal au coefficient de 125717-Eqn166 situé à l’intersection de la deuxième ligne et de la première colonne de 125717-Eqn167

En utilisant la calculatrice et en arrondissant au centième :

125717-Eqn168.

La probabilité que le joueur gagne la 15e partie est environ 0,57.