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 - 13-03-2011 09:55:15

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

Jeux à deux bis

Vous vous êtes probablement penché sur l'énigme Jeux à deux de Vasimolo (ici). Je vous propose exactement la même énigme, à deux mots près.

On tire un entier strictement positif N0 au hasard . Le premier joueur choisit alors un diviseur premier (*) de N0 qu'il retranche à N0 pour obtenir un entier strictement positif N1 . Le deuxième joueur choisit un diviseur premier de N1 qu'il retranche à N1 pour obtenir un entier strictement positif N2 ...

Celui qui ne peut plus jouer a perdu .


Quelles sont les chances du second joueur (**) d'emporter la partie ?

(*) Bien que 1 ne soit pas premier, 1 peut aussi être choisi. wink
(**) nommons le premier joueur A et le second B

Exemple :
Joueur A reçoit N0=2, il retranche 2 smile
Joueur B reçoit N1=0, il a perdu sad



Annonces sponsorisées :

The proof of the pudding is in the eating.
  • |
  • Répondre

#0 Pub

 #2 - 13-03-2011 11:35:45

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

jeux à deyx 1bis

Première constatation, celui qui reçoit un nombre premier N a gagné, il lui suffit de soustraire N (d'ailleurs il n'a pas le choix).

Faisons un peu d'analyse rétrograde (je note x << y pour exprimer qu'on passe de y à x), A joue les coups impairs (en partant de la fin) et B les pairs.

0 << p << p+k0 avec k0 premier et diviseur de p+k0, et k0 différent de 1
Or k0 diviseur de p+k0 implique k0 diviseur de p, donc k0=p.

On a donc 0<<p<<2p, mais si p>2 c'est mal joué de la part de A car on a aussi 2(p-1)<<2p et 2(p-1) n'est pas premier (p-1 est pair)...

Donc la fin est nécessairement 0<<2<<4.


A suivre...je vais faire mon marché dominical big_smile

J'ai juste pu examiner les situations perdantes jusqu'à 40 inclus, elles sont :

4 - 8 - 9 - 14 - 15 - 22 - 25 - 26 - 27 - 32 - 35 - 36

Je ne vois rien de simple pour l'instant, tu as une solution au moins ?

 #3 - 13-03-2011 11:38:59

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

Jeux à deux 1biss

C'est un bon début smile


The proof of the pudding is in the eating.

 #4 - 14-03-2011 19:12:38

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Jeux à deuxx 1bis

Je commence à penser qu'il n'y a pas de critère simple... me trompé-je ?

 #5 - 14-03-2011 23:02:15

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

jeuw à deux 1bis

Comment, dire... J'ai été un peu vite en éliminant le 1. roll

Je dois modifier l'énoncé de cette manière:
(*) Bien que 1 ne soit pas premier, 1 peut aussi être choisi comme diviseur. big_smile

ceci devrait donner une solution simple.


The proof of the pudding is in the eating.

 #6 - 14-03-2011 23:23:43

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Jeux à deux 1bbis

Sadique ! big_smile

 #7 - 15-03-2011 01:09:40

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Jeux à deuux 1bis

Bon, ok, avec 1 ça le fait.

Proposition : soit [latex]n[/latex] le nombre reçu, [latex]n[/latex] est perdant ssi [latex]n = 0 (4)[/latex] ([latex]n[/latex] vaut [latex]0[/latex] modulo [latex]4[/latex]).

Preuve (par récurrence) :
Appelons "pseudo-diviseur premier" (pdp en abrégé) de [latex]n[/latex], un diviseur premier de [latex]n[/latex] ou [latex]1[/latex].

La propriété se vérifie facilement pour [latex]n=0,1,2,3[/latex].
------------------------------------
De gauche à droite : si [latex]n = 0 (4)[/latex], soit [latex]p[/latex] un pdp de [latex]n[/latex], bien sûr [latex]p\neq 4[/latex].
On a donc [latex](n-p) \neq 0(4)[/latex].
Par HR, [latex](n-p)[/latex] est gagnant et donc [latex]n[/latex] perdant.
------------------------------------
De droite à gauche : si [latex]n \neq 0(4)[/latex] :
------------------
a) [latex]n = 1(4)[/latex], il suffit de soustraire [latex]1[/latex] pour laisser [latex](n-1)[/latex] qui est égal à [latex]0[/latex] modulo [latex]4[/latex], donc perdant par HR. Donc [latex]n = 1(4)[/latex] est gagnant.
------------------
b) [latex]n = 2(4)[/latex], donc [latex]n[/latex] est pair et il suffit de soustraire [latex]2[/latex] pour laisser [latex](n-2)[/latex] qui est égal à [latex]0[/latex] modulo [latex]4[/latex], donc perdant par HR. Donc [latex]n = 2(4)[/latex] est gagnant.
------------------
c) [latex]n = 3(4)[/latex].
Soient [latex]p_1,..,p_m[/latex] les diviseurs premiers de [latex]n[/latex] (les vrais, pas les pdp), i.e. [latex]n = p_1^{k_1}\times ...\times p_m^{k_m}[/latex].
Comme [latex]n[/latex] est impair, tous les [latex]p_i[/latex] sont impairs aussi,
donc [latex]\forall i : p_i = 1(4) \vee p_i = 3(4)[/latex].
Si [latex]\forall i : p_i = 1(4)[/latex], alors (arithmétique modulaire) [latex]n = 1(4)[/latex]: contradiction.
Donc pour au moins un des [latex]p_i[/latex] on a [latex]p_i= 3(4)[/latex].
Il suffit donc de soustraire ce  [latex]p_i[/latex] pour laisser [latex](n-p_i)[/latex] qui vaut [latex]0[/latex] modulo [latex]4[/latex], donc perdant par HR.
Donc [latex]n = 3(4)[/latex] est gagnant.

 #8 - 15-03-2011 07:21:09

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

jeux à seux 1bis

Eh hop ! Une brillante réponse de Gasole. smile

Déterminer quelles sont les chances de gagner ce petit jeu est à la portée de tous, la démonstration formelle de presque tous...

Allez, allez, à vot' bon coeur !


The proof of the pudding is in the eating.

 #9 - 16-03-2011 11:42:58

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

Jeux à deux 11bis

Le second joueur a 1 chance sur 4 de gagner !
En effet, le premier joueur va gagner, sauf si le premier nombre est un multiple de 4.

Une petite démo par récurrence ?

Soit la proposition suivante pour n supérieur ou égal à 1
P(n) : 4n-3, 4n-2 et 4n-1 sont gagnants, 4n est perdant

J'entends par "gagnant" (resp. "perdant") : celui qui reçoit ce nombre gagne (resp. perd)
Je remarquer avant de commencer que 0 est perdant.

Cas n=1
1 est gagnant, il suffit de retrancher 1 (1 n'est pas premier mais autorisé)
2 est gagnant, il suffit de retrancher 2 (2 est premier)
3 est gagnant, il suffit de retrancher 3 (3 est premier)
Mais 4 est perdant, car 1 et 2 sont les seuls diviseurs autorisés de 4. Si on retranche 1, on donne 3 à l'adversaire, si on retranche 2 on donne 2. Dans les 2 cas, on donne à l'adversaire un nombre gagnant.

On suppose P(n) vraie
4n+1 est gagnant, il suffit de retrancher 1, on laisse 4n à l'adversaire. 4n est perdant d'après P(n)
4n+2 est gagnant, il suffit de retrancher 2 qui est bien un diviseur premier de 4n+2. Et on laisse 4n perdant à l'adversaire
Je laisse pour l'instant de côté le cas 4n+3, il me pose quelques soucis ...
Reste à montrer que 4n+4 est perdant. Si on veut gagner avec 4n+4, il faut pouvoir donner à l'adversaire un nombre perdant, c'est-à-dire un multiple de 4. Or pour passer d'un multiple de 4 à un autre, il faut retrancher un multiple de 4. Comme 4 n'est pas premier, on ne peut pas retrancher un multiple de 4 à 4n+4, bien que 4 soit diviseur de 4n+4. On ne peut alors que donner un nombre gagnant à l'adversaire : 4n+4 est perdant.

Par récurrence, les multiples de 4 sont perdants, les autres sont gagnants !

Il reste le cas 4n+3 à traiter, il me résiste encore ...

EDIT
Je l'ai !
Il suffit de montrer que 4n+3 a au moins un facteur premier dans sa décomposition de la forme 4p+3. Su ce n'était pas le cas, tous les facteurs premiers de la décomposition de 4n+3 seraient de la forme 4p+1, car impairs. Or le produit de nombres congrus a 1 modulo 4 est ... congru a 1 modulo 4 ! Contradiction avec 4n+3 congru a 3 modulo 4.
Il existe donc 4p+3 diviseur premier de 4n+3.
4n+3 - (4p+3)=4(n-p) multiple de 4, donc perdant !
Bon en fait il faut la récurrence forte pour conclure, mais c'est un détail ;-)

 #10 - 16-03-2011 13:24:27

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

Jeux à dexu 1bis

Bravo L00ping007, le résultat est bon, la démonstration aussi.

Pour ceux qui ont un peu de temps, le résultat est facile à trouver, je vous assure, il suffit de faire des essais avec les premiers termes.


The proof of the pudding is in the eating.

 #11 - 16-03-2011 13:27:14

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

Jeux à deux 11bis

Et de ne pas se tromper sur un terme, comme moi au début par exemple avec 12 (et non, 4 n'est pas premier !!!), parce que ça décale tout pour les termes suivants !!!

 #12 - 17-03-2011 09:44:06

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

jeux à feux 1bis

Un joueur qui tombe sur un multiple de 4 a perdu si son adversaire joue, sinon il gagne en jouant au mieux. La démonstration est un peu plus bas.
La stratégie optimale est de donner à son adversaire un multiple de 4, ce qui est toujours possible comme le démontrera aussi la suite.

0 est un nombre "perdant", 1, 2 et 3 sont des nombres "gagnants"
Pour N donné, on suppose que jusqu'à 4N+3 tous les multiples de 4 sont "perdants" et tous les autres sont gagnants.
Au rang N+1, 4N+4 est perdant : en effet, je ne peux pas ôter 4 qui n'est pas premier et je donnerai donc forcément un nombre non multiple de 4 à mon adversaire, qui est gagnant d'après notre hypothèse.
4N+5 est gagnant: il suffit d'ôter 1 pour donner à mon adversaire 4N+4 qui est perdant
4N+6 est gagnant: il suffit d'ôter 2 pour donner à mon adversaire 4N+4 qui est perdant
4N+7 est gagnant, mais c'est un poil plus compliqué à voir.
Déjà, ce n'est pas un multiple de 2, donc ses facteurs sont impairs.
Les facteurs impairs sont soit de la forme 4k+1, soit de la forme 4k+3. Si 4N+7 n'était composé que de facteurs de la forme 4k+1, il serait congru à 1 modulo 4, ce qui n'est pas le cas. Il existe donc un facteur de 4N+7 de la forme 4k+3. Si on ôte ce facteur là, on donne à notre adversaire un multiple de 4 qui le fera perdre.


Edit: j'ai oublié de répondre à la question smile smile smile
Le joueur 2 a donc une chance sur 4 de gagner

 #13 - 17-03-2011 10:20:29

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

jeux à deux 1bos

Bravo Scarta.


The proof of the pudding is in the eating.

 #14 - 17-03-2011 15:59:09

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

jeuc à deux 1bis

En fait la condition est assez simple , le premier joueur perd si et seulement si il a tiré un entier multiple de 4 . On peut le démontrer par récurrence , s'il tire 1 , 2 ou 3 il gagne , s'il tire 4 il perd car après son choix il laisse 2 ou 3 au 2ème joueur qui sont des positions gagnantes . Supposons maintenant que l'équivalence est établie jusqu'au rang n-1 et considérons l'entier n proposé au joueur 1 .

Si [latex]n\equiv 0[mod 4][/latex] alors comme le joueur 1 ne peut pas choisir un multiple de 4 il va donner au deuxième joueur une position gagnante .
Si[latex] n\equiv 1[mod 4][/latex] alors le premier joueur enlève 1 à n et fournit une position perdante au joueur 2 .
Si [latex]n\equiv 2[mod 4][/latex] Le premier joueur enlève 2 et gagne à nouveau .
Si [latex]n\equiv 3[mod 4][/latex] alors n a forcément un diviseur premier [latex]p\equiv 3[mod4][/latex]( s'ils étaient tous congrus à 1 leur produit le serait aussi ) . En retirant [latex]p[/latex] le premier joueur donne une position perdante au deuxième .

Et la propriété est établie smile

Vasimolo

 #15 - 17-03-2011 16:26:57

logan
Passionné de Prise2Tete
Enigmes résolues : 47
Messages : 90

eux à deux 1bis

Bien aimé cette petite énigme alors sauf erreur de ma part je pense que le joueur 1 à 75% de chance de gagner à ce petit.

En effet en regardant les 1er termes on remarque que le joueur 1 ne perd que lorsque le nombre tiré est multiple de 4.

Alors j'ai la flemme de le faire mais je pense qu'un petit raisonnement par récurrence doit suffire mais bon.

 #16 - 17-03-2011 16:42:50

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

Juex à deux 1bis

Bravo aussi à Vasimolo et Logan qui ont tous deux déterminés une simple condition sur N0 pour désigner le vainqueur du duel.

Bien que le résultat soit simple, il n'est pas si intuitif.


The proof of the pudding is in the eating.

 #17 - 21-03-2011 13:05:40

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

jeux à feux 1bis

Le joueur 2 a une chance sur quatre d'emporter la partie.

Je vous propose de consulter les réponses ci-dessus pour une démonstration.


The proof of the pudding is in the eating.

 #18 - 21-03-2011 13:13:38

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Jeuxx à deux 1bis

Sympa ta petite énigme !

 #19 - 21-03-2011 13:26:10

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

JJeux à deux 1bis

Tout le mérite revient à Vasimolo, je m’étais gouré dans les hypothèses et était parvenu à ce surprenant résultat. Vivement la suite de Jeux à deux 2 smile, pour peut-être une 2bis big_smile.


The proof of the pudding is in the eating.
 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
P2T
Jeux de cartes par WhiteSticky
30-09-2012 Enigmes Logiques
P2T
Jeux d'arcade en 2 volets par franck9525
25-03-2011 Enigmes Logiques
P2T
Contraires par darkcod03100
12-12-2010 Enigmes Logiques
P2T
Un nombre unique ! par shadock
18-08-2015 Enigmes Logiques
30-01-2011 Enigmes Logiques
P2T
Portraits de sages par nipon
27-03-2008 Enigmes Logiques
P2T
05-01-2015 Enigmes Logiques
P2T
Echecs marseillais par L00ping007
12-04-2011 Enigmes Logiques
P2T
31-03-2009 Enigmes Logiques

Mots clés des moteurs de recherche

Mot clé (occurences)
Jeu de 1bis (1) — Enigme le perdant gagne (1) — Jeude1bis (1) — Jeu be dux (1) — Jeux1bisi (1) — Jeux de 1bis (1) — Jeux 1 bis (1) — 4n+3 diviseur premier 4p+3 (1) — Jeux1bis (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