On considère un jeu avec n tas de pierres, de tailles respectives a1, a2, ..., an. La condition de victoire est la suivante : si le XOR (ou exclusif) de toutes les tailles est nul, alors le premier joueur est en position perdante ; sinon, il peut forcer une victoire.

Cela s'explique par le fait que dans la représentation binaire, les bits sont appariés. En effet, la propriété du XOR donne 1 XOR 1 = 0 et 0 XOR 0 = 0, ce qui entraîne le résultat observé.

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int nb_tas;
    cin >> nb_tas;
    int resultat = 0;
    for (int i = 0; i < nb_tas; ++i) {
        int taille;
        cin >> taille;
        resultat ^= taille;
    }
    if (resultat == 0) {
        cout << "Non" << endl;
    } else {
        cout << "Oui" << endl;
    }
    return 0;
}

Jeu de Nim sur des marches

Dans cette variante, les pierres sont placées sur des marches. Le résultat est le suivant : on calcule le XOR des tailles des pierres sur les marches impaires. Si ce XOR est nul, le premier joueur perd ; sinon, il gagne.

L'argument repose sur le fait que retirer une pierre d'une marche impaire nécessite une seule opération, tandis que pour les marches paires, les pierres peuvent être considérées comme des paires identiques dont le XOR est toujours nul. Ainsi, seules les marches impaires influencent le résultat final.

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int nb_marches;
    cin >> nb_marches;
    int total = 0;
    for (int i = 1; i <= nb_marches; ++i) {
        int pierres;
        cin >> pierres;
        if (i % 2 == 1) {
            total ^= pierres;
        }
    }
    if (total == 0) {
        cout << "Non" << endl;
    } else {
        cout << "Oui" << endl;
    }
    return 0;
}

Introduction à la fonction SG

La fonction Sprague-Grundy (SG) est un outil clé en théorie des jeux combinatoires. On définit d'abord l'ensemble MEX (Minimum Excluded) d'un ensemble de nombres naturels comme le plus petit nombre non présent. Par exemple, MEX{1, 2} = 0 et MEX{0, 1, 2} = 3.

Pour une position dans un jeu, on associe une valeur SG. La position terminale a une valeur SG de 0, car aucun mouvement n'est possible. En remontant, chaque position a une valeur SG calculée comme le MEX des valeurs SG des positions accessibles. Une position avec une valeur SG non nulle permet au joueur actuel de forcer l'adversaire vers une position de valeur SG 0, assurant ainsi un avantage.

Jeu de Nim avec un ensemble de mouvements

Dans ce jeu, chaque tas de pierres peut être modifié selon un ensemble prédéfini de nombres de pierres à retirer. La stratégie utilise la fonction SG pour évaluer chaque tas.

Pour un tas de taille x, on calcule sg(x) en mémoïsation. On collecte les valeurs SG des positions résultantes après chaque mouvement possible, puis sg(x) est le MEX de cet ensemble. Le résultat du jeu est le XOR des valeurs SG de tous les tas.

#include <iostream>
#include <unordered_set>
#include <cstring>
using namespace std;

const int MAX_TAILLE = 100005;
int memo[MAX_TAILLE];
int mouvements[105];
int nb_mouvements;

int calculer_sg(int x) {
    if (memo[x] != -1) return memo[x];
    unordered_set<int> valeurs;
    for (int i = 0; i < nb_mouvements; ++i) {
        if (x >= mouvements[i]) {
            valeurs.insert(calculer_sg(x - mouvements[i]));
        }
    }
    int mex = 0;
    while (valeurs.count(mex)) ++mex;
    return memo[x] = mex;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(memo, -1, sizeof(memo));
    cin >> nb_mouvements;
    for (int i = 0; i < nb_mouvements; ++i) {
        cin >> mouvements[i];
    }
    int nb_tas;
    cin >> nb_tas;
    int xor_total = 0;
    for (int i = 0; i < nb_tas; ++i) {
        int taille;
        cin >> taille;
        xor_total ^= calculer_sg(taille);
    }
    if (xor_total == 0) {
        cout << "Non" << endl;
    } else {
        cout << "Oui" << endl;
    }
    return 0;
}

Jeu de Nim avec division des tas

Cette variante exploite une propriété fondamentale de la fonction SG : pour une position qui peut être divisée en deux sous-positions indépendantes, sa valeur SG est le XOR des valeurs SG des sous-positions. Ainsi, sg(b1, b2) = sg(b1) XOR sg(b2).

Dans ce jeu, un tas peut être divisé en deux tas plus petits. La valeur SG pour une taille x est calculée en considérant toutes les divisions possibles et en prenant le MEX des XOR des valeurs SG des paires résultantes. Le résultat global est le XOR des valeurs SG de tous les tas initiaux.

#include <iostream>
#include <unordered_set>
#include <cstring>
using namespace std;

const int MAX_TAILLE = 105;
int memo[MAX_TAILLE];

int calculer_sg(int x) {
    if (memo[x] != -1) return memo[x];
    unordered_set<int> valeurs;
    for (int i = 0; i < x; ++i) {
        for (int j = 0; j <= i; ++j) {
            valeurs.insert(calculer_sg(i) ^ calculer_sg(j));
        }
    }
    int mex = 0;
    while (valeurs.count(mex)) ++mex;
    return memo[x] = mex;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(memo, -1, sizeof(memo));
    int nb_tas;
    cin >> nb_tas;
    int xor_total = 0;
    for (int i = 0; i < nb_tas; ++i) {
        int taille;
        cin >> taille;
        xor_total ^= calculer_sg(taille);
    }
    if (xor_total == 0) {
        cout << "Non" << endl;
    } else {
        cout << "Oui" << endl;
    }
    return 0;
}