Bonjour

Ca ressemble à un jeu de Nim avec la possibilité de dériver en plus .

Les monômes P(X) sont tous gagnants .
Les binômes P(X)=aX+b sont gagnants si b<>a .
Les binômes P(X)=aX²+c sont gagnants si a<>c .
Les binômes P(X)=aX²+bX sont gagnants si b<>a .
Le cas des trinômes aX²+bX+c est un peu plus compliqué

Vasimolo

Tu confirmes que u peut être égal à ak ?

nodgim: oui et ça aide beaucoup si on considère un monôme!
Vasimolo: il suffit de prendre le polynôme x²+x+1 qui est gagnant pour briser une généralisation éventuelle
Mais comment trouver cette somme de Nim justement?

Le nombre u est-il forcément entier ?

C'est une question originale !
Pour l'instant je n'ai que ça:
nx+n est perdant. En effet, si on ôte un des 2 termes, on perd. Si on dérive, on perd. Si on soustrait en laissant les 2 termes, l'adversaire renvoie un mx+m plus petit, et à terme on nous renvoie sur x+1 qui est perdant.

Partant de ce nx+n perdant, on en déduit que nx²+2nx+ a est gagnant par dérivation.

La suite éventuellement si j'ai qq chose d'intéressant.

N'ayant pas l'habitude de résoudre ce genre de problème j'aimerai avoir une petite clarification de ce que veut dire "être perdant avec une stratégie optimale".

Si je prends P=(1,0,1)

Alors il y a deux possibilités de jouer:

Première possibilité
1) (1,0,0)=(1)
2) (0)

Et le joueur 2 gagne.

Deuxième possibilité
1) (1,2,0)=(1,2)
2) (1) ou (2)
1) (0)

Et le joueur 1 gagne.

Dans les deux cas un des deux joueurs peut gagner. La stratégie est "optimale" lorsque le jeu se fini en un minimum d'étape ou lorsque je gagne à coup sur?
Parce que dans la vraie vie on pourrai dire je commence si je fais pile au pile ou face et sinon l'autre commence...

Bref je ne peux pas répondre au problème tant que ce point n'est pas clair pour moi.

NB: Une stratégie optimale peut-elle vouloir dire à chaque tour, chaque joueur joue ce qu'il y a de mieux pour lui? Si oui à ce moment là pour la première possibilité le joueur 1 peut gagner à condition qu'il commence...

La preuve de la finitude du jeu est simple. Les opérations du jeu sont indépendantes de x. En remplaçant x par une valeur supérieure à la plus grande puissance, alors la valeur du polynome est strictement décroissante.

nodgim: c'est une manière de le prouver très efficace effectivement
Vasimolo: Comment sais tu qu'il l'est?

Effectivement, c'est un jeu de Nim dont on connait les règles, mais là il se complique par la possibilité pour celui qui n'a pas la main (c'est à dire celui qui qui se voit imposer la somme 0) de la reprendre par une dérivation. Enfin, tout au moins pour le cas de la généralité.

Bon alors, on a deux opérations possibles, soustraction ou dérivation

- un monôme est gagnant aX^n
Démo : par soustraction

- un polynôme du 1er degré aX+b est gagnant ssi a<>b
Démo : par dérivation je donnerai un polynôme gagnant à l'adversaire.
Par soustraction, je lui donnerai un nouveau polynôme aX+b, sauf si j'arrive à a=0 ou b=0. L'adversaire sera ensuite dans le même cas, etc...
Donc ça revient à nim(a,b), qui est gagnant pour a<>b (je donne a=b à l'adversaire, et quoi qu'il fasse je le remet toujours à a=b avec au final a=b=0)

- un polynôme aX²+b : même chose.
Démo : identique

- un polynôme aX²+bX est perdant ssi a=b
Démo :
Si a=b
>  par dérivation, j'ai 2aX+a et je perds.
>  par soustraction, si a=b, l'adversaire me ramène à un cas similaire en faisant aussi une soustraction similaire, jusqu'à a=0
Sinon
> par soustraction je ramène ça à un polynôme perdant a=b pour l'adversaire

- un polynôme aX²+bX+c avec la seule opération soustraction est gagnant pour XOR(a,b,c) <>0
Démo : c'est un jeu de Nim.

- un polynôme aX²+bX+c avec les deux opérations... plus difficile
Si XOR(a,b,c) = 0, j'ai tout intérêt à dériver, sinon je perds. Mais dériver donne 2aX+b, donc il me faut 2a=b pour gagner.
Je peux essayer de jouer sur a pour forcer un jeu sur b qui donnerait alors b=2a. C'est pas toujours possible, mais voilà comment faire pour trouver la bonne valeur:
- j'ai XOR(a,b,c)=0, je veux jouer sur a et obtenir XOR(a',2a',c) = 0
- Donc a' XOR c = 2a'
- 2a' termine par 0 en base 2, et je connais c, donc je trouve le dernier chiffre de a', donc l'avant dernier de 2a', ...
Exemple : c=10, écrit à l'envers :

c   = 0 1 0 1
2a' = 0 0 1 1
a'  = 0 1 1

(on trouve le chiffre en gras sur la dernière ligne, qu'on remonte au dessus, puis celui en italique, puis celui souligné).
Donc dans ce cas, il faudrait ramener a à 6 (sil est supérieur à 6).
Par exemple, pour a = 7 (et b=13), on aura
- 7x²+13x+10 => je soustrais
- 6x²+13x+10 => pour obtenir XOR=0, l'adversaire est dans ce cas précis obligé d'aller sur 6x²+12x+10 (pas possible de jouer sur a, il faudrait revenir à 7, pas possible de jouer sur c, il faudrait aller sur 11)
- si l'adversaire garde le résultat du XOR, alors j'ai 6x²+12x+10, je dérive pour gagner
- s'il choisit de ne pas garder le résultat du XOR (plus logique du coup), alors je pourrais à mon tour tomber sur un XOR nul et tenter de gagner (sauf que tout ce qu'on vient de dire pourrait être ré-appliqué, donc ça demande encore à être creusé un peu)

Le jeu de Nim en lui même est déjà assez complexe mais il a une solution simple ( disons plutôt limpide ) : autoriser la dérivation ajoute une difficulté . On pourrait aussi par exemple permettre la réduction du polynôme en le privant de ses racines entières ou l'intégrer en lui attribuant une constante égale à 2 , le multiplier par X+1 ... , on peut multiplier les variantes à l'infini .

Une variante est intéressante si elle ajoute un plus à la solution ou si elle ouvre des perspectives de recherche qui la distingue des autres .

Je n'ai rien vu de tel pour le moment : j'espère me tromper

Vasimolo

PS : pourquoi laisser un tel sujet masqué aussi longtemps si on n'apporte aucun indice ? Personnellement j'ai arrêté de chercher depuis longtemps

C'est vrai que le trinôme de degré 2 ne devrait pas être être trop difficile à dévisser : c'est sûrement un peu plus délicat pour un trinôme quelconque .

Mais attendons l'avis de l'auteur

Vasimolo