Corrigé bac NSI 2026 Métropole jour 1 — Exercice 2 : Jeu du Recto-Verso : configurations binaires, xor et graphe des configurations

Partie A : représentation binaire des configurations

1. Le plateau compte $3\times 3=9$ jetons et chaque jeton a exactement deux états possibles (Recto ou Verso), indépendamment des huit autres. Une configuration est le choix d'un état pour chacun des neuf jetons : par le principe multiplicatif, il y a $2\times 2\times \cdots \times 2=2^9=512$ configurations. C'est aussi le nombre de mots de 9 bits, ce qui annonce la représentation binaire de la suite.

2. On note un plateau ligne par ligne, Recto $=1$ et Verso $=0$. La configuration de la figure 1 est [0, 0, 1, 0, 0, 1, 1, 1, 0]. On joue les trois coups, chacun retournant les trois jetons de la ligne ou de la colonne choisie :

La configuration finale [1, 0, 0, 1, 0, 0, 1, 0, 0] n'est pas la configuration victorieuse (les neuf jetons côté Recto) : la séquence ne mène pas à la victoire.

Ce que le correcteur attend : l'erreur porte sur le dernier coup. Après « ligne 1 » puis « ligne 2 », seule la colonne 3 est entièrement Verso ; le coup gagnant est « colonne 3 » et non « colonne 2 », qui retourne trois jetons déjà Recto. La séquence ligne 1, ligne 2, colonne 3 mène bien à la victoire (nous l'avons vérifié).

3. La liste de la figure 1, [0, 0, 1, 0, 0, 1, 1, 1, 0], lue comme l'écriture binaire d'un entier (le premier bit est celui de poids fort, $2^8$), donne :

$$0\cdot 2^8+0\cdot 2^7+1\cdot 2^6+0\cdot 2^5+0\cdot 2^4+1\cdot 2^3+1\cdot 2^2+1\cdot 2^1+0\cdot 2^0=64+8+4+2=78.$$

La configuration de la figure 1 est représentée par l'entier 78. (Contrôle de la méthode sur l'exemple du sujet : [0, 0, 1, 0, 0, 0, 0, 1, 1] donne $64+2+1=67$.)

4. On parcourt la liste de gauche à droite : à chaque bit, l'entier déjà construit est décalé d'un rang (multiplié par 2) et le bit courant s'y ajoute (schéma de Horner). Cela évite de calculer des puissances de 2 et fonctionne quelle que soit la longueur de la liste.

def representant(liste):
    n = 0
    for bit in liste:
        n = 2 * n + bit
    return n

Trace sur [0, 0, 1, 0, 0, 0, 0, 1, 1] : n prend successivement les valeurs $0,0,1,2,4,8,16,33,67$ ; la fonction renvoie 67. Sur la liste de la figure 1 elle renvoie 78, sur [1]*9 elle renvoie 511 et sur la liste vide elle renvoie 0.

Variante équivalente avec les puissances de 2, l'indice $i$ portant le poids $2^{\mathtt{len}(\mathtt{liste})-1-i}$ :

def representant(liste):
    n = 0
    for i in range(len(liste)):
        n = n + liste[i] * 2 ** (len(liste) - 1 - i)
    return n

5. On applique xor indice par indice et l'on accumule les résultats dans une nouvelle liste, sans modifier les listes reçues :

def xor_etendu(l_x, l_y):
    resultat = []
    for i in range(len(l_x)):
        resultat.append(xor(l_x[i], l_y[i]))
    return resultat

Tests : xor_etendu([1, 1], [0, 1]) renvoie [1, 0] (l'exemple du sujet) ; xor_etendu([0, 0, 1, 0, 0, 0, 0, 1, 1], [1, 1, 1, 0, 0, 0, 0, 0, 0]) renvoie [1, 1, 0, 0, 0, 0, 0, 1, 1], dont le représentant est 387 (figure 3) ; sur deux listes vides elle renvoie []. La boucle fait len(l_x) tours : coût linéaire en la longueur des listes.

6. La configuration reçue est un entier : on la convertit d'abord en liste de neuf bits avec binaire. On parcourt ensuite les clés du dictionnaire (les noms des huit coups), on récupère pour chaque coup sa liste de bits (le « masque » des jetons à retourner), on l'applique par $\oplus$ et l'on convertit le résultat en entier avec representant :

def configurations_suivantes(config):
    config_bin = binaire(config)
    voisins = []
    for coup in coups_possibles:
        masque = coups_possibles[coup]        # ligne facultative
        resultat = xor_etendu(config_bin, masque)
        voisins.append(representant(resultat))
    return voisins

La ligne facultative peut être supprimée en écrivant directement resultat = xor_etendu(config_bin, coups_possibles[coup]). On peut aussi parcourir coups_possibles.values() et se passer de la clé. Comme un dictionnaire Python est parcouru dans l'ordre d'insertion de ses clés, l'appel configurations_suivantes(67) renvoie exactement [387, 123, 68, 359, 209, 10, 338, 23], la liste de la figure 3 et de la ligne 67 du dictionnaire graphe (vérifié par exécution) ; configurations_suivantes(4) renvoie [452, 60, 3, 288, 150, 77, 277, 80].

Partie B : graphe des configurations

7. Soit une arête $x\to y$ : il existe un coup, de masque $c$, tel que $y=x\oplus c$ (bit à bit). Jouons le même coup depuis $y$ :

$$y\oplus c=(x\oplus c)\oplus c=x\oplus (c\oplus c)=x\oplus 0=x,$$

car $\oplus$ est associatif, qu'un bit « ou exclusif » lui-même vaut 0 ($0\oplus 0=0$ et $1\oplus 1=0$) et que $\oplus 0$ laisse chaque bit inchangé. Concrètement, retourner deux fois de suite les mêmes jetons les remet dans leur état initial : chaque coup est sa propre opération inverse. Le coup $c$ mène donc de $y$ à $x$, et l'arête $y\to x$ existe. Le graphe est en fait non orienté (nous l'avons vérifié sur ses 512 sommets) ; chaque sommet a exactement 8 voisins.

8. Le graphe possède $2^9$ sommets.

• Une matrice d'adjacence est un tableau carré à $2^9$ lignes et $2^9$ colonnes, soit $2^9\times 2^9=2^{18}=262144$ entiers (des 0 et des 1), quel que soit le nombre d'arêtes.
• Le dictionnaire associe à chacun des $2^9$ sommets la liste de ses 8 voisins, donc $2^9\times 8=2^9\times 2^3=2^{12}=4096$ entiers dans les listes, auxquels s'ajoutent les $2^9=512$ clés : $2^{12}+2^9=4608$ entiers en tout.

La matrice occupe environ 64 fois plus de mémoire ($2^{18}/2^{12}=2^6$), et elle est presque entièrement remplie de 0 : chaque sommet n'a que 8 voisins sur 512 possibles, le graphe est creux. Le dictionnaire (listes d'adjacence) ne stocke que les arêtes qui existent ; de plus, parcourir les voisins d'un sommet y coûte 8 opérations au lieu de 512 (une ligne entière de la matrice). C'est le choix adapté.

9. Le sommet en cours de visite est ajouté à vus, puis on visite récursivement chacun de ses voisins non encore vus ; les voisins sont lus dans le dictionnaire :

def parcours_profondeur(graphe, configuration, vus):
    vus.append(configuration)
    for s in graphe[configuration]:
        if s not in vus:
            parcours_profondeur(graphe, s, vus)

La récursion termine car chaque appel ajoute un nouveau sommet à vus et que le graphe est fini (au plus 512 appels, profondeur de pile bien inférieure à la limite de Python) ; le test s not in vus empêche de tourner en rond dans les cycles.

10. La configuration victorieuse a ses neuf jetons côté Recto : c'est la liste [1]*9, soit l'entier $2^9-1=511$. Une configuration est perdante si aucune suite de coups ne mène à la victoire, c'est-à-dire si 511 n'est pas atteignable depuis elle dans le graphe : on lance le parcours depuis 4 et l'on regarde si 511 figure parmi les sommets vus.

victoire = representant([1, 1, 1, 1, 1, 1, 1, 1, 1])   # 511
vus = []
parcours_profondeur(graphe, 4, vus)
print(victoire not in vus)   # affiche True : 4 est perdante

On peut aussi écrire assert 511 not in vus. Exécuté sur le graphe construit avec configurations_suivantes, le parcours depuis 4 atteint 128 configurations, et 511 n'en fait pas partie : la configuration 4 est bien perdante. (Depuis 67, au contraire, les 128 configurations atteintes contiennent 511.)

Ce que le correcteur attend : la liste vus doit être créée vide avant l'appel et passée en argument, puisque c'est la fonction qui la remplit ; l'argument est l'entier 4, pas la liste binaire(4).

11. Le parcours en largeur est le plus approprié. Il explore le graphe par « couches » à l'aide d'une file : d'abord la configuration de départ, puis toutes celles accessibles en un coup, puis celles accessibles en deux coups, etc. Comme toutes les arêtes ont le même poids (un coup), la première fois que la victoire est rencontrée, c'est nécessairement à la distance minimale : le chemin reconstitué a le minimum de coups.

Le parcours en profondeur, lui, s'enfonce le plus loin possible le long d'une branche avant de revenir en arrière : il atteint la victoire par le premier chemin qu'il trouve, en général très long. Par exemple, depuis la configuration 78 de la figure 1, le parcours en profondeur écrit à la question 9 atteint 511 après 23 coups, alors que le parcours en largeur donne le chemin minimal en 3 coups : ligne 1, ligne 2, colonne 3 (question 2).