Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #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 amusant) du polynômr

Salut smile

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!



Annonces sponsorisées :

Un promath- actif dans un forum actif
  • |
  • Répondre

#0 Pub

 #2 - 19-10-2015 09:41:14

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Le "Je&uquot; (ma foi terriblement amusant) 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

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 terriblemetn 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 : 2953

le "jeu" (ma foi terriblement amusany) 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 : 4733

le "jeu" (ma foi terriblement amusant) du pplynôme

Disons qu'on gagne aisément en rendant égaux les deux coefficients smile

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 terriblement amusant)) du Polynôme

nodgim: oui et ça aide beaucoup si on considère un monôme! smile
Vasimolo: il suffit de prendre le polynôme x²+x+1 qui est gagnant pour briser une généralisation éventuelle smile
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 : 1430

le "jeu" (mz 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
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 : 1746

Le "Jeu" (ma foi terriblement amusant) du Pollynô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 : 1430

Le "Jeu" (ma foi terriblement amusant) du Polynôm

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 : 2953

Le "Jeu" (mma foi terriblement amusant) du Polynô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 Polynôme

scarta: prenant A=B=1, avec la formule de la factorielle, ça fonctionne?
titou: oui, u est entier! smile
scarta: au temps pour moi

nodgim: c'est très bien! smile

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 : 3311

Le "Jeu" (ma foi terriiblement 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 Polyynô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 : 2953

Le "Jeu" (ma foi terriblement aamusant) du Polynô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 : 4733

Le "eJu" (ma foi terriblement amusant) du Polynôme

Un trinôme qu'on pourrait donner gagnant et pourtant perdant P(X)=2X³+6X+5 smile

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" (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


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 "jeu&qiot; (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 : 2953

le "jeu" (ma foi terribkement 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 "Jeu&quoot; (ma foi terriblement amusant) du Polynôme

nodgim: tu fais fausse route neutral


Un promath- actif dans un forum actif

 #20 - 22-10-2015 18:42:44

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Le "Jeu" (ma foi terriblement amusant) du Polynôm

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 : 3311

Le "Jeu" (ma foi terribleent 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


"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 : 4733

le "jeu" (ma foi terribmement amusant) du polynôme

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 lollollollol

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 smile

 #23 - 23-10-2015 18:49:57

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

le "jeu" (ma foi terriblement amusant) du polunô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 : 4733

le "jeu" (ma foi terrinlement amusant) du polynôme

http://www.prise2tete.fr/upload/nobodydy-N40-p55.jpghttp://www.prise2tete.fr/upload/nobodydy-N40-p48.jpghttp://www.prise2tete.fr/upload/nobodydy-N40-p9.jpg

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 smile

Vasimolo

 #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" (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"  lol 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

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 20 moutons, ils meurent tous sauf 12, combien en reste-t-il ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete