Multiple ou diviseur
Bonjour à tous .
Je ne me suis pas trompé de rubrique :-)
Dans un livre de 5ème on propose un jeu dans lequel deux joueurs choisissent à tour de rôle un nombre dans une grille contenant une fois exactement tout les entiers de 1 à 20 . Le choix du premier joueur est libre , ensuite chacun doit choisir un nouvel entier ( pas encore choisi ) qui doit être un multiple ou un diviseur du précédent . Le joueur qui n'a plus de choix a perdu .
L'exercice est vraiment ludique et beaucoup d'élèves trouvent une solution gagnante .
Il y a une 2ème question : et si le premier joueur choisit l'entier 14 ? On y arrive encore facilement .
Une question d'élève : et si le premier joueur prend autre chose que 14 ( un nombre est tiré au hasard ) , qui gagne ?
Le premier joueur a-t-il plus de chance de gagner que le deuxième ( ça c'est moi qui l'ai rajouté ) ?
Je n'ai pas de réponse à ces deux questions et pourtant 20 n'est vraiment pas bien grand .
Merci d'avance pour votre participation :-)
Domi
Je ne me suis pas trompé de rubrique :-)
Dans un livre de 5ème on propose un jeu dans lequel deux joueurs choisissent à tour de rôle un nombre dans une grille contenant une fois exactement tout les entiers de 1 à 20 . Le choix du premier joueur est libre , ensuite chacun doit choisir un nouvel entier ( pas encore choisi ) qui doit être un multiple ou un diviseur du précédent . Le joueur qui n'a plus de choix a perdu .
L'exercice est vraiment ludique et beaucoup d'élèves trouvent une solution gagnante .
Il y a une 2ème question : et si le premier joueur choisit l'entier 14 ? On y arrive encore facilement .
Une question d'élève : et si le premier joueur prend autre chose que 14 ( un nombre est tiré au hasard ) , qui gagne ?
Le premier joueur a-t-il plus de chance de gagner que le deuxième ( ça c'est moi qui l'ai rajouté ) ?
Je n'ai pas de réponse à ces deux questions et pourtant 20 n'est vraiment pas bien grand .
Merci d'avance pour votre participation :-)
Domi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Du coup ça ne m'a pas l'air très intéressant comme jeux... surtout pour le deuxième joueur en fait (:D
Bien sûr, on pourrait construire le graphe des coups (la relation de divisibilité dans [1, 20] sans l'orientation) et pour chaque sommet dérouler l'arbre en supprimant les cycles, et évaluer les sommets (+ pour les terminaux, et remonter, + si tous les descendants sont -, - s'il y a un descendant +)
Mais les 14 arbres qui restent à explorer doivent bien contenir quelques milliers de noeuds !
Entre parenthèses, rigolo ton problème, Domi :-)
Bien sûr que le jeu initial n'est pas intéressant , il est là pour faire comprendre à des élèves de 5éme ce qu'est un multiple , un diviseur ou un nombre premier . La stratégie gagnante pour le premier joueur est facile à trouver , celle du 2ème joueur quand le 1er choisit 14 aussi . Après si le nombre de départ est choisi au hasard , on change de registre .
Domi
PS pour GG : clairement les choix : 11 ; 13 ; 17 et 19 pour le premier joueur sont perdants mais à part 14 autres trajets à étudier sont plutôt délicats .
Après gagnant ou perdant , il faut fixer le cadre . le premier nombre est choisi au hasard et après c'est le joueur 1 qui joue .
Domi
PS : Content de te retrouver :-)
Content moi aussi !
Le 2 est pioché au départ et le joueur 1 doit choisir un 2ème entier .
Domi
Au temps pour moi !
(Merci AD, ta vigilance est sans faille ! Cela dit, je mettrais plus volontiers un t à choisi !)
Domi
Il est clair que tous ces autres entiers sont dans l'une ou dans l'autre catégorie)
Domi
On peut chercher sur la toile "Jeu de Juniper Green".
D'un autre côté je n'ai pas tout lu .
Domi
On voit le rôle particulier du 14 .
Domi
Je simplifie en considérant le jeu pour [1, 12]. La première figure est le graphe du jeu sans 1 (perdant à tout stade du jeu) ni les nombres premiers supérieurs à 6 (gagnants comme premier coup). La deuxième est l'arbre du jeu lorsque le premier joueur choisit 12. Ce 12 est la racine de l'arbre, dont la construction se passe de commentaire. Les deux joueurs choisissant alternativement, les noeuds de profondeur paire sont les nombres choisis par le premier joueur, ceux de profondeur impaire sont ceux du second joueur. A tout noeud on peut associer un + ou un - selon que le joueur qui choisit ce nombre (à ce stade du jeu) a une stratégie gagnante quelle que soit la réponse de l'adversaire, ou que l'adversaire a au moins une réponse gagnante pour lui (donc un + pour son noeud). Ainsi, les noeuds terminaux sont tous des +, un noeud est un - s'il existe au moins un noeud successeur +, et un + si tous les successeurs sont des -. Pour montrer que 12 est gagnant, on voit qu'il suffit d'évaluer une fraction des noeuds (prunning).
Si l'on avait la patience d'évaluer de cette manière les 8 autres noeuds initiaux, on aurait la proportion de premiers coups gagnants (sans oublier 1, 7, 11). Ces coups gagnants du premier joueur conduisant à une réponse perdante du deuxième joueur, et les perdants une réponse gagante du dexième joueur (à condtion qu'il joue au mieux bien sûr !), on saurait immédiatement s'il vaut mieux commencer ou non lorsqu'on tire au hasard le premier nombre (dans ce cas le deuxième joueur s'appelle le premier, et vice-versa). J'espère que je suis plus clair ! :-)
Ce qui me semble intéressant, ce serait de trouver des critères (issus de la théorie des graphes (à laquelle hélas je ne connais rien !)) qui permettrait de savoir, par la seule inspection du graphe initial, quels sont les coups gagnants sans avoir à construire les arbres !
P.S. Je me suis trompé. J'ai oublié les arêtes 2,8 et 4,12. Ce qui change (et complique) tout ! Mais tu vois l'idée ..
J'ai corrigé un de mes messages antérieur car j'avais commencé à regarder le problème avec les 100 premiers entiers dans lequel tous les nombres premiers supérieurs à 50 étaient perdants et tous les premiers inférieurs à 50 ( et 1 ) étaient gagnant : ce n'est pas aussi simple avec 20 entiers .
Si le problème t'intéresse il me semble qu'il serait malin de trouver des coups gagnants pour le joueur qui joue en premier ( juste après le tirage au sort ) . Pour le moment seuls 1 , 11 , 13 , 14 , 17 , 19 ont leurs solutions . Il me semble qu'il vaut mieux regarder en priorité les sommets de plus fort degré car le graphe se simplifie énormément si on supprime toutes les arêtes issues de ces sommets , il reste alors à trouver un bon chemin dans ce qu'il reste .
Je ne vais pas te rassurer , j'en connais sûrement encore moins que toi en théorie des graphes . Ça n'empêche pas d'être curieux :-)
Domi
Pour le jeu à 20 nombres, par ordinateur, je trouve que les seuls premiers coups perdants sont 1 et 14.
Pour le jeu à 12 nombres, les premiers coups perdants sont 1,3 et 10.
En effet, si le premier joueur joue 3, le second joue 9, le premier joue nécessairement 1, et le second peut jouer par exemple 7, le premier ne peut alors plus jouer.
Une question bête : on choisit le premier entier au hasard et ensuite chacun joue en suivant les règles . On considère alors deux parties ayant utilisé exactement les mêmes nombres et aboutissant sur le même entier . En finissant la partie proprement ( chacun joue au mieux ) , le gain sera toujours du même côté ?
Domi
Après je n'ai pas approfondi plus que ça et je ne sais pas si on peut appliquer des résultats de ce chapitre au jeu mentionné dans ce fil, mais si ça peut intéresser quelqu'un...
@Marco : Je ne suis pas fan d'informatique mais tu peux donner une idée de ton programme. Donne-t-il une réponse dans des temps raisonnables pour 100 entiers au lieu de 20 (ça c'est pour répondre à un autre site ou j'ai balancé le problème sans vraiment réfléchir :-D ).
Il est clair que le résultat est très sensible à la borne choisie (comme dans la version initiale du jeu).
Domi
Pour 75 nombres, le temps de calcul est trop long.
A[1]=VRAI, ... , A[N]=VRAI
(A[ i ]=VRAI si on n'a pas encore joué le nombre i).
Puis, on écrit la fonction récursive suivante qui renvoie VRAI ou FAUX.
GAIN(i):
A[ i ]=FAUX
Pour tous les multiples ou diviseurs j de i tels que 0 $<$ j $\leq$ N : si A[ j ]=VRAI et si GAIN(j)=VRAI, alors ( A[ i ]=VRAI et on retourne FAUX ).
Après cette boucle: A[ i ]=VRAI, et on retourne VRAI.
Alors, GAIN(5), par exemple, retournera VRAI si on gagne en jouant 5 au premier coup.
Le programme est très simple mais épuise assez vite la machine .
J'ose une nouvelle variante : l'entier de départ est choisi parmi les entiers premiers d'une liste de taille quelconque : qui gagne ?
La question est vite réglée pour les "grands" premiers ( supérieurs à la moitié de la borne supérieure ) . J'ai l'impression qu'à partir d'une certaine taille de la liste tous les "petits" ( non grands ) premiers sont gagnants pour celui qui commence .
Avis aux amateurs .
Domi
Pour l'ensemble des entiers inférieurs à n , on considère le graphe dont les sommets sont les entiers premiers inférieurs ou égaux à n/2 ( en fait on peut enlever les sommets s tels que n/2<s²<n ) . Les arêtes du graphe relient tous les sommets dont le produit est supérieur à n/2 . L'idée est de construire une chaîne de coups forcés dont le dernier est 1 ( et donc fatal ) pour le joueur 2 .
Je joins le graphe pour n=200 .
A partir d'un élément imposé , on choisit n'importe quel chemin issu de ce sommet et se mordant quelque part .
Par exemple en partant de 19 : 19 - 7 - 23 - 5 - 37 - 3 - 53 - 2 - 61 - 3 .
Il reste à proposer les entiers :19X7 , 7X23 , 23X5 , ... et attendre la réponse du joueur 2 .
Pour les petites valeurs de n le graphe n'est pas connexe , d'où les résultats surprenants .
Domi