La fonction de Grundy est-elle définie ?

[RME431]

Bonjour,

On me demande de montrer que la fonction de Grundy est une application bien définie.
Cette fonction se définit comme suit :

On considère C l'ensemble des configurations possibles dans un jeu et S(C) (la "suite" de cette configuration) l'ensemble des configurations qu'on peut adopter à partir de C. Autrement dit, on considère un jeu à deux joueurs, et si C est la configuration après que le premier a joué, S(C) est l'ensemble des configurations possibles après que le deuxième a joué (en faisant un coup permis par les règles).
La fonction de Grundy est définie par :
si S(c)=ensemble vide, f(c)=0 (c dans C) et sinon f(c)=mex(f(c') avec c' dans S(c))
Bien sûr ce ne sont pas des parenthèses mais des accolades car c'est un ensemble. Et mex signifie "minimum exclu".

Donc je pensais dire que, si S(c) est l'ensemble vide, la fonction de Grundy est une application bien définie car elle renvoie une seule valeur : 0. Sinon, elle est aussi bien définie car elle renvoie une seule valeur : le mex, et on n'a bien qu'une possibilité, donc un c donné ne pourrait pas avoir plusieurs images par f.

Ça, c'est mon opinion, mais j'ai entendu parler (et lu) qu'il y avait aussi une histoire de "f(c') ne dépend pas de f(c)"... Sauf que je ne comprends pas ce que cela viendrait faire dans le problème, et que je saurais encore moins le montrer...

Quelqu'un saurait-il m'expliquer pourquoi mon idée est fausse (je pense qu'elle l'est, ça m'a l'air un peu trop simple) ?

Merci d'avance !

[Robot]

Imagine un jeu avec deux configurations, notées et , et tel que et . Qu'est-ce que ta fonction de Grundy dans ce cas ?

[RME431]

Elle "tourne en rond" car f(0)=mex(f(1))=mex((mex(f(0)))=...
Donc il faut bien prouver que f(y) ne dépend pas de f(x). Est-ce que ça suffit si je dis que comme le jeu est fini (c'est une des hypothèses de départ), ça veut implicitement dire qu'on n'a pas le droit de boucler, donc on ne reviendra jamais dans la même configuration, et donc c n'est pas dans S(c) ?

[Robot]

Tu remarqueras que dans l'exemple que j'ai donné, c n'est pas dans S(c) ! Tu n'écris pas ce que tu voudrais écrire.

" le jeu est fini (c'est une des hypothèses de départ)"

hypothèse que tu nous avais soigneusement cachée. Que veut dire "Le jeu est fini" ?

[RME431]

Qu'on ne peut pas faire de boucle, qu'il n'existe aucun moyen de "revenir sur ses pas" vers une situation déjà rencontrée.

[Robot]

Qu'on ne peut pas faire de boucle, qu'il n'existe aucun moyen de "revenir sur ses pas" vers une situation déjà rencontrée.

Prenons un jeu dont l'ensemble des configurations est l'ensemble des entiers naturels avec, pour tout entier , .
On ne peut pas faire de boucle, n'est-ce pas ?
Ce jeu est-il fini ? Quelle est sa fonction de Grundy ?
Il serait peut-être temps que tu écrives des choses précises et bien définies. Donne ton énoncé exact.

[RME431]

Alors je dirais qu'un jeu fini est tel qu'on peut arriver à la position finale (un des deux joueurs a gagné) en un nombre fini d'étapes, en partant de n'importe quelle configuration autorisée.
La seule donnée de l'énoncé que je pourrais rajouter est la suivante : le jeu est considéré comme étant dans sa position finale lorsqu'on ne peut plus jouer de coup permis par les règles.

[Robot]

Alors je dirais qu'un jeu fini est tel qu'on peut arriver à la position finale (un des deux joueurs a gagné) en un nombre fini d'étapes, en partant de n'importe quelle configuration autorisée.
La seule donnée de l'énoncé que je pourrais rajouter est la suivante : le jeu est considéré comme étant dans sa position finale lorsqu'on ne peut plus jouer de coup permis par les règles.

Tu ne donnes toujours pas l'énoncé exact. Considère le jeu dont l'ensemble des configuration est avec et pour tout entier .
On peut arriver à la position finale en partant de n'importe quelle configuration en une seule étape.
Quelle est la fonction de Grundy de ce jeu ?

Tu t'es vraisemblablement trompé dans la quantification.
La définition correcte ne serait-elle pas que, quelle que soit la suite de coups joués, on arrive toujours à une position finale en un nombre fini de coups ?

[Darkwolftech]

Bonjour,

On me demande de montrer que la fonction de Grundy est une application bien définie.

Toi, je sais dans quel lycée et dans quelle classe tu es :lol3: