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 - 06-11-2013 10:11:46

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

Jouons au Nim avec les nombres premieers

Bonjour à tous.
On peut jouer au Nim avec les nombres premiers. On écrit dans l'ordre la suite des nombres premiers et on se donne un nombre n. 1 seul jeton posé au départ  sur le 2, et chacun des joueurs avance tour à tour ce jeton en ajoutant au maximum n au nombre où se trouve le jeton. Le perdant est celui qui ne peut plus jouer parce que le nombre premier suivant est à un écart supérieur à n. Par exemple, pour n=5, celui qui devra avancer le jeton posé en 23 ne pourra le faire, car le premier suivant est 29, à une distance de 6>5 de 23.
Il y a bien entendu une stratégie gagnante, comme pour le Nim classique.
Il se trouve que le premier joueur gagne pour tout n jusqu'à 79, et perd pour n=80. Sans partir dans de longs calculs, pourrez vous trouver d'autres n pour lequel le premier joueur gagnera à coup sûr ?

  • |
  • Répondre

#0 Pub

 #2 - 06-11-2013 11:56:00

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

jouons au nim avec les nombres premuers

J'apporte une correction à la question initiale qui n'a pas en fait beaucoup d'intérêt...

 #3 - 06-11-2013 13:29:29

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 6,004E+3

jouons au nim avec les nombres preliers

80 perd arrivé à 155921 en 1738 coups.

Le suivant est 86 qui perd en 3688 coups arrivé à 360749

 #4 - 06-11-2013 13:57:29

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

houons au nim avec les nombres premiers

Pour que le premier joueur soit perdant, une condition nécessaire (mais pas suffisante) est que 3+n soit premier.

En effet si 3+n n'est pas premier et que le premier joueur déplace le jeton sur 3, son adversaire ne peut pas jouer de coup que le premier joueur n'aurait pas pu jouer, donc il est perdant à tout les coups.

Donc déjà tout les n différent de p-3 (où p est premier) sont gagnants pour le premier joueur smile

 #5 - 06-11-2013 17:24:27

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

Jouons au Nim avec les nombres premier

Gwen, c'est sans doute vrai que 86 est perdant, je me garderai bien de vérifier. Tu peux au besoin donner un aperçu sur ta méthode pour arriver au résultat, c'est en tout cas très rapide !
Sinon, la question corrigée est un peu différente, mais peut être ne l'as tu pas vue ?

 #6 - 06-11-2013 21:31:30

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

jouons au num avec les nombres premiers

Je développe mon raisonnement :

Supposons que le premier joueur déplace le jeton sur 3.
Il y a deux cas :
_soit son adversaire n'a pas de stratégie gagnante à partir de 3
_soit son adversaire a une stratégie gagnante en déplaçant son jeton sur le nombre premier k où k <= n+3

Si n+3 n'est pas premier, on a même k<=n+2
Le premier joueur aurait pu jouer k dès le premier coup. Donc il a une stratégie gagnante en jouant soit 3 soit k.

Mathieu

 #7 - 06-11-2013 21:47:21

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 6,004E+3

Jouons au Nim avec le nombres premiers

Euh, non , je ne l'ai pas vue et je ne comprends pas la nuance.

De plus, je me suis planté car pour 86 , la victoire se joue sur 3/5 et non sur 2/3.

 #8 - 07-11-2013 19:12:33

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

Jouons au Nimm avec les nombres premiers

A Gwen: Dommage, ce n'est pas passé loin pour 86. J'étais tout de même surpris que n=80 étant la 1ère valeur perdante, la seconde se trouvât aussi proche. Ce que je demande en fait, ce sont les valeurs de n pour lesquelles on est sûr et certain de gagner quand on commence. Il y a en a beaucoup...

A w9: je vais encore réfléchir à ta proposition, en attendant tu peux chercher d'autres valeurs de n, il y en a bien plus que ce que tu proposes.

 #9 - 07-11-2013 19:56:29

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 6,004E+3

jouons au nim avec les nombres premierd

81 en est déjà 1 : la seule valeur gagnante certaine avec 80 est 83, donc avec 81 , on gagne.

Je dirais que dans ce cas de figure, tous les n impairs sont gagnants, car ils laissent le choix entre 3 et 5 sans changer la suite du parcours.

Ou peut-être les n égaux à un nombre premier -2 car on peut choisir la "parité" de la réponse au premier coup.

On sait que, en partant de la fin, celui qui dit le nombre premier juste inférieur à la limite (-n) va gagner. A rebours, il y a donc un nombre gagnant dans l'intervalle allant de 2 au premier nombre premier après n+2.

Si ce nombre peut être atteint avec n, le joueur 1 gagne. Sinon, ce nombre est le premier juste au dessus de n+2. (avec quel écart ? )
Sinon :
Avec n pair, c'est la roulette. Je ne vais pas compter. 5 est-il gagnant ?
Avec n impair, on est libre : Soit l'écart nous est favorable, et on le garde, soit on dit 3 et l'écart va devenir défavorable au second joueur qui ne pourra utiliser que n-1 au lieu de n.

 #10 - 07-11-2013 20:30:01

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

Jouons au Nim avec les nombre premiers

A w9: c'est bon pour ta sélection, elle englobe même de facto celle à laquelle je pensais. C'est juste que le cheminement qui tu as suivi est différent de celui que j'avais vu, je ne l'ai pas compris tout de suite.
Bravo !

 #11 - 07-11-2013 20:31:25

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

Joons au Nim avec les nombres premiers

Gwen oui, c'était aussi ma démarche.
w9 est allé juste un peu plus loin....

 #12 - 07-11-2013 21:34:41

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

Jouon au Nim avec les nombres premiers

Je suis étonné que ta méthode soit englobé dans la mienne parce qu'il y a plein de n avant 80 qui ne sont pas dans ma sélection.

En remontant la liste des nombres premier à partir du premier saut plus grand que n on peut savoir si le premier joueur gagne ou pas, mais quand on se rapproche de n=80, il faut partir de très très loin dans la liste. Même avec la force brute ça semble difficile (peut être un programme?)

Comment tu as fait?

 #13 - 09-11-2013 11:21:43

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

jouons au nim avec lzs nombres premiers

Sans revenir sur la stratégie du jeu de Nim, assez connue, on peut remarquer que, pour un 2n donné, la suite des nombres gagnants est la même pour le 2n+1, sauf si le premier nombre de la suite gagnante est 2, auquel cas 2 ne sera pas dans la suite de 2n+1.
Les n impairs aboutissent toujours à une victoire.
W9 a observé que si le premier nombre de la suite 2n est 2, alors il y a forcément un premier en 2n+3, ce qui englobe de facto les n impairs.

On ne sait pas s'il existe une infinité de 2n perdants, mais ils sont de toute façon rares dans n.

 

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 40 moutons, ils meurent tous sauf 18, combien en reste-t-il ?

Mots clés des moteurs de recherche

Mot clé (occurences)
Au nim (1) —

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