![](/img/vague-bas-gauche.png) |
#1 - 18-10-2015 22:29:50
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Le "Jeu" (ma foi terriblement amusan)t du Polynôme
Salut
Je reviens pour poster un petit problème que m'a inspiré un DM de maths!
Soit P un polynôme à coefficients naturels non tous nuls, s'écrivant sous la forme P(x)=a_0*x^0+a_1*x^1+...+a_n*x^n avec n=deg(P)
Le Jeu du Polynôme consiste, à chaque coup, à soit: -dériver le polynôme -soustraire un nombre u à un des coefficients d'indice k, tel que 0<u=<a_k
Le Jeu se joue à deux. Le premier qui obtient 0 gagne le Jeu.
Quels sont les Polynômes de degré 2 qui sont perdants avec une stratégie optimale? Acceptez vous de jouer en premier avec le polynôme P(x)=x+1? Avec x²+1? Avec x²+x?
Autres questions plus ou moins faciles, qui peuvent guider: Spoiler : [Afficher le message] Quelles sont les configurations qui sont immédiatement gagnantes (1 coup)? Quels sont les Polynômes de degré 1 qui sont perdants avec une stratégie optimale? Quels sont les Polynômes de degré 2, de terme a_1 nul, qui sont perdants avec une stratégie optimale? Acceptez vous de jouer avec le polynôme P(x)=3x+4? Pouvez vous généraliser à des polynômes perdants de degré n? J'ignore la réponse à certaines questions
Bonne chance!
Un promath- actif dans un forum actif
#2 - 19-10-2015 09:41:14
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
Le "Jeu" (ma foi terriblement amsant) du Polynôme
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é ![smile](img/smilies/smile.png)
Vasimolo
#3 - 19-10-2015 10:10:34
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Le "Jeu" ;(ma foi terriblement amusant) du Polynôme
Tu es très bien parti! Comment raisonnes tu pour obtenir ces résultats?
Un promath- actif dans un forum actif
#4 - 19-10-2015 10:39:58
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
le "jeu" (ma foi terriblemeny amusant) du polynôme
Tu confirmes que u peut être égal à ak ?
#5 - 19-10-2015 11:23:51
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
Le "Jeu" (ma foi teerriblement amusant) du Polynôme
Disons qu'on gagne aisément en rendant égaux les deux coefficients ![smile](img/smilies/smile.png)
Le cas où il y a trois coefficients non nuls semble plus délicat car il faut envisager le cas où adversaire annule la somme de Nim en dérivant ( je n'ai pas encore regardé si c'était possible ) .
Vasimolo
#6 - 19-10-2015 14:43:41
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Le "Jeu" (ma foi terirblement amusant) du Polynôme
nodgim: oui et ça aide beaucoup si on considère un monôme! ![smile](img/smilies/smile.png) Vasimolo: il suffit de prendre le polynôme x²+x+1 qui est gagnant pour briser une généralisation éventuelle ![smile](img/smilies/smile.png) Mais comment trouver cette somme de Nim justement?
Un promath- actif dans un forum actif
#7 - 19-10-2015 15:19:50
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
le &quit;jeu" (ma foi terriblement amusant) du polynôme
Pour un polynôme de degré 2, si je le dérive, le premier joueur qui dérive le résultat aura perdu : on va donc a tour de rôle soustraire des valeurs aux deux coefficients restants ==> jeu de Nim, et je dois donc laisser mon adversaire avec une situation perdante ==> A xor B = 0, mais pour 2 tas, A=B est plus simple ![smile](img/smilies/smile.png) Donc Ax² + Ax + Z est gagnant (je dérive et j'attend ^^) Pour n'importe quel autre polynome, j'ai intérêt - à ne pas dériver (Nim perdant) - à ne pas obtenir un polynôme tel que ci-dessus (qui serait gagnant pour l'autre)
Pour Ax²+Bx+C avec A!=B, j'essaye donc d'obtenir A'x²+B'x+C' avec A'!=B' L'adversaire fera bien évidemment pareil : on va donc faire des soustractions uniquement pour retomber sur un autre jeu de Nim, en plus compliqué : on perd si A=B (et pas seulement A=B=C=0). Pour C=0 ==> pas plus compliqué : A=B et A=B=0 sont équivalents pour un nim classique. Les polynômes Ax²+Bx sont donc gagnants. Pour A=0 ou B=0 ==> pareil Pour les autres cas, c'est plus compliqué, je chercherai, mais déjà les polynômes suivants sont gagnants : - Ax²+Ax+C - Ax²+Bx (A!=B) - Ax²+C (A!=C)
#8 - 19-10-2015 15:40:43
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Le "Jeu" (ma foi terrriblement amusant) du Polynôme
Le nombre u est-il forcément entier ?
#9 - 19-10-2015 16:23:40
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
lz "jeu" (ma foi terriblement amusant) du polynôme
Bon j'ai dit n'importe quoi, je sais plus dériver... Je reviens avec une version corrigée
#10 - 19-10-2015 18:14:48
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Le "Jeu" (ma foi terriblement amusant) du Polnôme
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.
#11 - 19-10-2015 18:25:55
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Le "Jeu" (ma foi terriblement amusant) du Polyynôme
scarta: prenant A=B=1, avec la formule de la factorielle, ça fonctionne? titou: oui, u est entier! ![smile](img/smilies/smile.png) scarta: au temps pour moi
nodgim: c'est très bien! ![smile](img/smilies/smile.png)
Personne n'a pensé à démontrer que le jeu était fini avant de faire ses calculs, ça peut être intéressant!
Un promath- actif dans un forum actif
#12 - 19-10-2015 18:38:30
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
Le "Jeu" (ma foi terriblment amusant) du Polynôme
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...
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#13 - 19-10-2015 20:36:35
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Le "Jeu" (ma foi terriblement amusant) du Pollynôme
Stratégie optimale signifie que les deux joueurs sont de parfaits logiciens qui vont essayer de gagner en jouant le meilleur coup possible
Un promath- actif dans un forum actif
#14 - 20-10-2015 08:26:28
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Le "Jeu" (ma foi terriblement amusant) du Polynnôme
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.
#15 - 20-10-2015 11:01:02
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
Le "Jeu" (ma foi terriblemment amusant) du Polynôme
Un trinôme qu'on pourrait donner gagnant et pourtant perdant P(X)=2X³+6X+5 ![smile](img/smilies/smile.png)
Vasimolo
#16 - 20-10-2015 13:47:24
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Le "Jeu&quoot; (ma foi terriblement amusant) du Polynôme
nodgim: c'est une manière de le prouver très efficace effectivement Vasimolo: Comment sais tu qu'il l'est? ![smile](img/smilies/smile.png)
Un promath- actif dans un forum actif
#17 - 21-10-2015 12:19:07
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
le "keu" (ma foi terriblement amusant) du polynôme
Indice: Le jeu ressembe au Jeu de Nim. Si vous connaissez un peu ça peu aider. Faites un graphe orienté.
Un promath- actif dans un forum actif
#18 - 21-10-2015 16:57:31
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Le "Jeu" (ma foi terriblement amusant) du Polynôme
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é.
#19 - 21-10-2015 22:18:46
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Le "eJu" (ma foi terriblement amusant) du Polynôme
nodgim: tu fais fausse route ![neutral](img/smilies/neutral.png)
Un promath- actif dans un forum actif
#20 - 22-10-2015 18:42:44
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
le "jeu" (ma foi terriblement amisant) du polynôme
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)
#21 - 22-10-2015 23:15:07
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
le &quor;jeu" (ma foi terriblement amusant) du polynôme
Bon bah je vais attendre la réponse j'ai pas d'idée. Enfin j'en ai mais ça tient pas debout ![hmm](img/smilies/hmm.png)
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#22 - 23-10-2015 18:31:50
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
Lee "Jeu" (ma foi terriblement amusant) du Polynôme
#23 - 23-10-2015 18:49:57
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
le "jeu" (ma foi terriblemeny amusant) du polynôme
Attention Vasimolo, Promath a peut être trouvé une astuce pour tout polynome de degré 2. Il faudrait juste qu'il nous dise si c'est bien le cas.
#24 - 23-10-2015 19:31:22
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
Le "Jeu" (ma foi teriblement amusant) du Polynôme
#25 - 23-10-2015 20:10:29
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Le "Jeu&uqot; (ma foi terriblement amusant) du Polynôme
Je n'ai pas encore résolu le problème, je ne garantis rien
Définissons la valeur du polynôme comme la somme pour k allant de 0 à deg(P) de a_k*k! Cette somme décroit pendant le jeu: par soustraction elle ne peut que décroître. Par dérivation, elle est conservée ssi a_0=0
Avec deg(P)=<2
Les monômes sont tous gagnants Les binômes?? sont gagnants sauf ceux qui vérifient a_0=a_(1 ou 2): appelons B l'ensemble de ces polynômes Les trinômes de degré 2 perdants n'ont aucun coefficient égal (par sourstraction de l'un on arrive à ne somme de nim nulle) Ils vérifient a=!2b (dérivation) On appelle T cette famille de polynômes (trinômes) Ils sont tels que les conditions plus haut sont respectées, et tels qu'on ne puisse passer de l'un à l'autre par une opération autorisée dans le Jeu
Trouvons un premier polynôme suffisant
x²+3x+2 est perdant. Sa somme est 7 Dérivation donne 2x+3 qui devient un B Soustraction du premier: Idem Deuxième: on arrive à un B ensuite Pareil pour le troisième Un polynôme avec a=a2=1 a forcément une suite dans le jeu avec a2=1, donc on peut directement construire ces polynômes On doit oublier TOUS les polynomes x²+yx+2 ainsi que x²+3x+y de toute manière gagnant, mais en réalité il faut oublier les polynômes qu'on peut obtenir en intégrant de toute manière de degré trois
, on note a b c les coeff pour la suite
Faisons un tableau avec b et c comme axes, on fait commencer à deux. On place notre premier polynôme avec un X dans la case, on noirict celles qui sont impossibles Cela nous permet d'établir un résultat, qu'on montre par récurrence: les polynômes de la forme x²+bx+c sont perdants, SSI b=c+1 et b>2 Démo: l'initialisation est faite Hérédité: prenons un tel polynôme -Dérivation: trivial -Soustraction du x²: trivial soustraction du b jusqu'à b' donne x²+b'x+c et si b'=2, on dérive, si b'=1 on soustrait le 3ème terme, si b' est nul, trivial de la même manière pour le dernier terme
Ok pour les polynômes avec a=1. Pour a=2 b différent de 4 on trouve deux polynômes de base, 2x²+x+3 et 2x²+3x+1 Puis c'est le même schéma que le précédent, cad b=c+1 pour b>4, je ne refais pas la démo
pour a=3 les polynômes de base sont 3 2 1 3 1 2 3 4 5 3 5 4 et on obtient pareil
Généralisons? une manière non rigoureuse de généraliser se fait aisément avec le tableau tracé, on voit deux lignes et une colonnes noircies au début donc ça implique un décalage à l'infini passé la valeur 2a sinon, on fait une récurrence mais je ne l'ai pas faite, je pense qu'elle fonctionne bien en ce qui concerne la recherche des polynômes de base, quand a croit les polynômes se concentrent au dessus de la ligne de cases noircies b=c, mais pas totalement. Je me repenche dessus quand j'ai le temps
Voilà en quoi le résultat est intéressant, Vasimolo, donc j'espère "te rassurer" Même si ma démo est bancale car il manque la recherche des polynômes de base:/ Je reviens chercher après
Un promath- actif dans un forum actif
|
![](/img/vague-haut-droite.png) |