1) On peut démontrer qu’une position est gagnante pour celui qui a la main si et seulement si le nombre d’allumettes n’est pas divisible par 7.

Preuve : supposons que cela soit faux, et considérons le plus entier n qui contredirait ce qu’on veut montrer. Si 1 ? n ? 7, c’est évident. Supposons n ? 8.

Si n est divisible par 7 tandis que la position est gagnante, il y a une contradiction, car tout coup jouable mène à un entier non divisible par 7 qui par hypothèse de récurrence est une position gagnante. C’est bien une contradiction : d’une position gagnante il doit y avoir au moins un coup donnant `a mon adversaire une position perdante.

Si n n’est pas divisible par 7 tandis que la position est perdante, il y a une contradictions, car enlever n mod 7 allumette mène à un entier divisible par 7 qui par hypothèse de récurrence est une position perdante. C’est bien une contradiction : d’une position perdante, tout coup doit donner `a mon adversaire une position gagnante.

2)

#include
#define ORDI 0
#define HUMAIN 1
main(){
int coup, pos, joueur;
printf("Combien d’allumettes : ");
scanf("%i", &pos);
printf("Qui commence (%i pour l’ordi, %i pour vous) : ", ORDI, HUMAIN);
scanf("%i", &joueur);
while(pos!=0){
if (joueur == ORDI){
coup = pos%7;
if (coup == 0) coup = 1;
printf("Il y a %i allumettes, j’en enleve %i.\n", pos, coup);
}
else{
printf("Il y a %i allumettes. Votre coup svp : ", pos);
scanf("%i", &coup);
}
pos = pos - coup;
joueur = !joueur;
}
if (joueur == ORDI) printf("Vous avez gagne !\n");
else printf("Vous avez perdu...\n");
return 0;
}