[ENFIN RÉSOLU] Re: Autre exercice dont je ne comprends pas bien la règle du jeu...

Cette fois ça y est ! Je vais donner la solution d'une façon un peu plus
générale qu'avec les entiers naturels de 1 à 144, sachant que cette
solution ne fonctionnera que si une certaine condition est remplie (or
elle l'est bien dans le cas 144).

Le 20/10/2022 16:33, Olivier Miakinen a écrit :

 
================================================================================
Zig et Puce disposent d’une grille carrée 12x12 dont les cases sont remplies
avec les entiers naturels de 1 à 144. Le premier joueur barre un nombre pair
puis chaque joueur barre un nombre non encore rayé parmi les multiples ou les
diviseurs du nombre choisi par le joueur précédent. Un joueur est déclaré
vainqueur si son adversaire ne peut plus jouer.Zig joue le premier. Lequel des
deux joueurs a une stratégie gagnante ?
Le vainqueur de la partie joue ensuite en solitaire avec la même grille et selon
les mêmes règles. Son objectif est de barrer le plus grand nombre possible n de
cases.Déterminer n.
================================================================================

Généralisons donc au cas où on peut choisir nos nombres parmi tous les entiers
naturels de 1 à N, avec comme exemple avec N=144.

La condition pour que ma solution fonctionne est qu'il existe trois nombres
premiers distincts p, q et r compris entre N/4 et N/3 :
 N/4 < p, q, r ≤ N/3

Dit autrement, toutes les conditions suivantes doivent être vérifiées :
 p premier, 3p ≤ N < 4p
 q premier, 3q ≤ N < 4q
 r premier, 3r ≤ N < 4r
 p, q et r sont tous différents

L'intérêt d'une telle condition, c'est que les seuls multiples de p
(resp. q, r) permis sont p, 2p et 3p.

Le tableau suivant pourrait s'avérer utile.
 
     |  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12| 13| 14| 15| 16| 17|
 ----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  53 |106|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
  47 | 94|141|   |   |   |   |   |   |   |   |   |   |   |   |   |   |
  43 | 86|129|   |   |   |   |   |   |   |   |   |   |   |   |   |   |
  41 | 82|123|   |   |   |   |   |   |   |   |   |   |   |   |   |   |
  37 | 74|111|   |   |   |   |   |   |   |   |   |   |   |   |   |   |
  31 | 62| 93|124|   |   |   |   |   |   |   |   |   |   |   |   |   |
 ----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Ce tableau montre que pour N=144 on a le choix entre quatre nombres premiers
pour p, q et r, ces quatre nombres étant 37, 41, 43 et 47. C'est plus qu'il
n'en faut.

Par ailleurs, le postulat de Bertrand devenu le théorème de Tchebychev prouve
qu'entre N/2 et N on trouvera toujours au moins un nombre premier. Soit x l'un
quelconque d'entre eux. Pour N=144, x peut être n'importe lequel des nombres de
l'ensemble { 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139 }.


J'en viens maintenant à la stratégie. Le premier à jouer (A) a une stratégie
gagnante en commençant par le nombre pair 2p. Le second joueur (B) ne peut
alors choisir que parmi les trois nombres 1, 2 et p.

Si B choisit 1, A gagne immédiatement en jouant x. Ceci restera vrai à tout
moment dans la partie. Aussi, bien que B puisse toujours jouer 1, je ne le
rappellerai pas à chaque fois.

Sachant cela, après le premier choix de B parmi 2 et p, tous les choix suivants
de B peuvent être forcés par le choix de A, jusqu'à ce que B finisse par perdre.

Les deux déroulements possibles de la partie sont les suivants.

Si B a choisi 2 :
2p -> 2 -> 2q -> q -> 3q -> 3 -> 3r -> r -> 2r -> 1

Si B a choisi p :
2p -> p -> 3p -> 3 -> 3q -> q -> 2q -> 2 -> 2r -> r -> 3r -> 1

Voilà, cette fois je crois ne pas m'être trompé. Encore merci à Dominique
pour cette énigme très intéressante !

--
Olivier Miakinen