Exercice 1 : Questions à choix multiple : optimisation, graphes et vote
12 points L'optimisation par programmation linéaireLa théorie des graphesLes procédures de vote
Conditions de l'épreuve : 3 heures, un aide-mémoire manuscrit d'une feuille recto verso (format lettre) préparé par vous, une calculatrice à affichage graphique dont la mémoire a été vidée, une règle et un rapporteur. En section A, seule la lettre choisie compte ; en section B, seule la réponse compte ; en section C, la démarche complète est exigée, car chaque situation est corrigée à la grille descriptive du Ministère.
Section A : six questions, réparties dans les exercices 1 et 2. Pour chacune, une seule des quatre propositions est juste. Les documents ci-dessous servent aux questions a), b) et c).
| Rang | 18 entraîneurs | 12 entraîneurs | 10 entraîneurs |
|---|---|---|---|
| 1er choix | X | Y | Z |
| 2e choix | Y | Z | Y |
| 3e choix | Z | X | X |
- a) Le polygone de contraintes du document 1 a pour sommets , , et . On veut maximiser la fonction . Quelle est la valeur maximale de , et où est-elle atteinte ? A) , au sommet • B) , au sommet • C) , au sommet • D) , au point
- b) Pendant le tournoi, un préposé doit inspecter l'éclairage de chaque allée du document 2 en passant une seule fois dans chacune. Laquelle des affirmations est vraie ? A) Le graphe admet un cycle eulérien : le préposé peut finir là où il a commencé • B) Le graphe n'est pas connexe • C) Le graphe admet une chaîne eulérienne, mais aucun cycle eulérien • D) Le graphe n'admet aucune chaîne eulérienne
- c) Les 40 entraîneurs du tournoi désignent la joueuse ou le joueur par excellence parmi Xavier (X), Yasmine (Y) et Zoé (Z), par le vote par Borda : 3 points pour un premier rang, 2 pour un deuxième, 1 pour un troisième. Le document 3 donne leurs classements. Qui est élu, et avec quel score ? A) Y, avec points • B) X, avec points • C) Z, avec points • D) X, avec points
Voir la correction
Réponses
- a) Réponse B : en
- b) Réponse C : deux sommets impairs ( et ), chaîne eulérienne sans cycle
- c) Réponse A : Y élu avec points (X , Z )
Réponse B : vaut au sommet .
Règle des sommets : quand le maximum existe, il est atteint à un sommet du polygone de contraintes. On évalue donc aux quatre sommets, et seulement là.
; ; ;
Le plus grand est , en , juste devant en : l'écart est d'un point, d'où l'intérêt de calculer chaque sommet au lieu de deviner.
Piège : choisir parce que porte le plus gros coefficient (proposition A), ou combiner le plus grand et le plus grand en (proposition D) : ce point n'est même pas dans la région, puisque la frontière a pour équation et que .
Réponse C : une chaîne eulérienne, mais aucun cycle eulérien.
Degrés lus sur le graphe : : 2, : 3, : 4, : 4, : 3, : 2. Contrôle : , le double du nombre d'allées.
Le graphe est connexe, on va de n'importe quel terrain à n'importe quel autre : B est faux.
Exactement deux sommets sont de degré impair, et : le graphe admet une chaîne eulérienne qui part de l'un et finit à l'autre, mais pas de cycle eulérien, qui exige des degrés tous pairs.
Une chaîne qui convient : B, A, C, B, D, C, E, D, F, E (neuf allées, chacune une fois).
Piège : conclure qu'il n'existe aucune chaîne dès qu'un sommet est impair (proposition D). Le critère compte les sommets impairs : zéro donne un cycle, deux donnent une chaîne, plus de deux ne donnent rien.
Réponse A : Y est élu avec points.
X : ; Y : ; Z :
Contrôle : chaque bulletin distribue points, donc le total vaut , et .
X a le plus de premiers rangs () et gagnerait à la pluralité, mais entraîneurs le placent dernier. Borda récompense le consensus : Y, que personne ne classe dernier, l'emporte.
Piège : ne compter que les premiers rangs (, proposition D), ou donner le gagnant de la pluralité avec son score de Borda (proposition B).
Coche ici les exercices faits ou à revoir : un compte gratuit, sans mot de passe, retient tes coches et tes réponses justes d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander l'exercice qui te manque. Crée ton espace, un courriel suffit.