Problème 1019
Alice et Bob, assis du même côté de la table, jouent à « volte-face ». 6 cartes, numérotées de gauche à droite de 1 à 6, ont une face bleue et une face rouge (la couleur visible des cartes au départ est aléatoire).Chacun des deux joueurs, à son tour, choisit une « carte meneuse » parmi celles numérotées 1 à 4 dont la face visible est bleue, puis retourne la carte meneuse et les deux suivantes. Celui qui ne peut plus jouer a perdu. Le gagnant marque 20 points moins le nombre total de coups joués durant la partie, le perdant marque ce nombre de coups. Chacun joue pour le mieux. Alice commence.
- 1A. Si toutes les cartes sont face bleue au départ, qui gagnera ? Alice (répondre 1) ou Bob (répondre 2) ?
- 1B. Quel est alors le nombre total de coups joués si chacun cherche à optimiser son score ?
- 1C. Parmi les 16 orientations possibles des cartes de 1 à 4 au départ, combien permettent à Alice de gagner ?
- 2A, 2B, 2C. Toutes les cartes sont face bleue au départ. Combien de cartes seront meneuses un nombre impair de fois ?
On peut modéliser le problème par un graphe. Les noeuds sont les configurations des 4 (ou 10) cartes que l'on peut jouer, et les arcs les transitions possibles correspondant à un coup. On peut voir que ce graphe est sans cycle, car si on modélise le bleu par 0 et le rouge par 1, le nombre binaire encodé est toujours strictement plus grand après le coup. Ce graphe est donc un DAG.
Une fois les noeuds et arcs construits, on peut calculer un ordre total respectant l'ordre partiel du DAG. Cela permet de simplifier ensuite le traitement des noeuds (en parcourant les noeuds dans cet ordre ou dans l'ordre inverse, on sait que les noeuds correspondant aux arcs entrant ou sortant ont déjà été traités).
Une fois cela fait, on peut tagger les noeuds en fonctions de s'il correspondent à un noeud gagnant ou perdant (en choisissant arbitrairement une sémantique, par exemple, c'est à Alice de jouer), puis calculer la distance au noeud final (cartes rouges uniquement) en considérant le fait que sur un noeud gagnant, on cherche à prendre le chemin le plus court possible, et sur un noeud perdant le plus long possible.
Enfin, on peut calculer les différents chemins correspondant à cette distance. Le programme écrit peut générer sous forme de graphe (au format .dot) les différents chemins. Le paramètre explore_all_paths permet d'énumérer tous les chemins (et les afficher, générer le graphe, compter le nombre de fois où chaque carte est meneuse), ou bien de n'énumérer que les chemins "optimaux" (pour le paramètre N = 10, il est déconseillé d'explorer tous les chemins). Pour la question 2, l'énoncé est ambigü, car si l'on suppose que chacun joue pour le mieux (selon le sens : il cherche d'abord à gagner, puis à optimiser son score), un joueur qui perd peut marquer plus de point qu'un joueur qui gagne... en effet, avec cette stratégie, on trouve une longueur de 16 (16 coups), ce qui selon l'énoncé, apporte plus de points au perdant. Concernant cette question, il faut soit se contenter des chemins "optimaux" avec le problème décrit précédemment (il y a 146 chemins), soit remarquer que le nombre de cartes étant meneuses un nombre impair de fois est toujours le même sur des millions de chemins (si l'on essaie une énumération complète), et supposer que c'est toujours vrai... Maximiser le score sans chercher à gagner d'abord requiert une modélisation complémentaire.
Le code est disponible ici.
Une fois les noeuds et arcs construits, on peut calculer un ordre total respectant l'ordre partiel du DAG. Cela permet de simplifier ensuite le traitement des noeuds (en parcourant les noeuds dans cet ordre ou dans l'ordre inverse, on sait que les noeuds correspondant aux arcs entrant ou sortant ont déjà été traités).
Une fois cela fait, on peut tagger les noeuds en fonctions de s'il correspondent à un noeud gagnant ou perdant (en choisissant arbitrairement une sémantique, par exemple, c'est à Alice de jouer), puis calculer la distance au noeud final (cartes rouges uniquement) en considérant le fait que sur un noeud gagnant, on cherche à prendre le chemin le plus court possible, et sur un noeud perdant le plus long possible.
Enfin, on peut calculer les différents chemins correspondant à cette distance. Le programme écrit peut générer sous forme de graphe (au format .dot) les différents chemins. Le paramètre explore_all_paths permet d'énumérer tous les chemins (et les afficher, générer le graphe, compter le nombre de fois où chaque carte est meneuse), ou bien de n'énumérer que les chemins "optimaux" (pour le paramètre N = 10, il est déconseillé d'explorer tous les chemins). Pour la question 2, l'énoncé est ambigü, car si l'on suppose que chacun joue pour le mieux (selon le sens : il cherche d'abord à gagner, puis à optimiser son score), un joueur qui perd peut marquer plus de point qu'un joueur qui gagne... en effet, avec cette stratégie, on trouve une longueur de 16 (16 coups), ce qui selon l'énoncé, apporte plus de points au perdant. Concernant cette question, il faut soit se contenter des chemins "optimaux" avec le problème décrit précédemment (il y a 146 chemins), soit remarquer que le nombre de cartes étant meneuses un nombre impair de fois est toujours le même sur des millions de chemins (si l'on essaie une énumération complète), et supposer que c'est toujours vrai... Maximiser le score sans chercher à gagner d'abord requiert une modélisation complémentaire.
Le code est disponible ici.
- 1A. 2. Si aucune carte n'est rouge, Alice perdra.
- 1B. 6. Les parties les plus longues ont 6 coups.
- 1C. 8. Il y a 8 situations gagnantes et 8 perdantes.
- 2A. 4. Meneuses un nombre impair de fois : 1, 4, 7 et 10.