![](/img/vague-bas-gauche.png) |
#1 - 13-03-2011 09:55:15
- franck9525
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1935
- Lieu: 86310
Jeux à deux 1ibs
The proof of the pudding is in the eating.
#2 - 13-03-2011 11:35:45
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
jeux à drux 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](img/smilies/big_smile.png)
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 : 1935
- Lieu: 86310
jeux à seux 1bis
C'est un bon début ![smile](img/smilies/smile.png)
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
eux à deux 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 : 1935
- Lieu: 86310
Jeuux à deux 1bis
Comment, dire... J'ai été un peu vite en éliminant le 1. ![roll](img/smilies/roll.png)
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](img/smilies/big_smile.png)
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 1bi
Sadique ! ![big_smile](img/smilies/big_smile.png)
#7 - 15-03-2011 01:09:40
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
Jeux à deux 1is
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 : 1935
- Lieu: 86310
jeux à dzux 1bis
Eh hop ! Une brillante réponse de Gasole. ![smile](img/smilies/smile.png)
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 : 2010
- Lieu: Paris
JJeux à deux 1bis
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 : 1935
- Lieu: 86310
Jeu à deux 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 : 2010
- Lieu: Paris
jeux à deux 1vis
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 : 1958
Jeu xà deux 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](img/smilies/smile.png) 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 : 1935
- Lieu: 86310
Jeux deux 1bis
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 : 5,418E+3
jeux à drux 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](img/smilies/smile.png)
Vasimolo
#15 - 17-03-2011 16:26:57
- logan
- Passionné de Prise2Tete
- Enigmes résolues : 47
- Messages : 90
Jeeux à 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 : 1935
- Lieu: 86310
Jeux à dex 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 : 1935
- Lieu: 86310
Jexu à deux 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
#19 - 21-03-2011 13:26:10
- franck9525
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1935
- Lieu: 86310
jeux à deux 1nis
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 , pour peut-être une 2bis .
The proof of the pudding is in the eating.
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |