Path: ...!weretis.net!feeder8.news.weretis.net!news.trigofacile.com!usenet-fr.net!.POSTED!not-for-mail
From: Olivier Miakinen <om+news@miakinen.net>
Newsgroups: fr.rec.jeux.enigmes,fr.comp.lang.python
Subject: F-Nim
Followup-To: fr.rec.jeux.enigmes
Date: Fri, 21 Oct 2022 11:10:37 +0200
Organization: There's no cabale
Lines: 56
Message-ID: <titnme$31k8$1@cabale.usenet-fr.net>
NNTP-Posting-Host: 220.12.205.77.rev.sfr.net
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-15
Content-Transfer-Encoding: 8bit
X-Trace: cabale.usenet-fr.net 1666343438 99976 77.205.12.220 (21 Oct 2022 09:10:38 GMT)
X-Complaints-To: abuse@usenet-fr.net
NNTP-Posting-Date: Fri, 21 Oct 2022 09:10:38 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.4
X-Mozilla-News-Host: news://news.galacsys.net:119
Bytes: 3474

[diapublication, suivi vers fr.rec.jeux.enigmes]

Bonjour,

Voici un autre jeu qui, une fois r�solu strat�giquement, pourra fournir
le sujet d'une programmation en Python[�].

Comme dans le(s) jeu(x) de Nim, c'est un jeu � deux joueurs dans lequel
il s'agit de retirer des allumettes jusqu'� ce qu'il n'en reste plus.
Voici la r�gle compl�te.

==========================================================================
On a un seul tas de N allumettes. Le premier joueur retire le nombre
d'allumettes qu'il veut, sa seule interdiction �tant de retirer la
totalit� du tas. Ensuite, chaque joueur retire un nombre d'allumettes
de son choix, entre 1 allumette et deux fois le nombre d'allumettes
que vient de retirer son adversaire. Le gagnant est celui qui retire la
derni�re allumette et vide le tas.
==========================================================================

Il s'agit de trouver la meilleure strat�gie pour chaque joueur en fonction
de la taille N du tas au d�part.

==========================================================================
Prenons un exemple avec N = 15.
Le premier joueur A doit retirer un nombre d'allumettes compris entre
1 et 14 (il n'a pas le droit de tout retirer au premier coup).

Supposons que A retire 4 allumettes, il en reste 11.
Alors B peut retirer n'importe quel nombre entre 1 et 8 (8 = 2�4).
B retire 3 allumettes, il en reste 8.
A peut retirer n'importe quel nombre entre 1 et 6 (6 = 2�3).
A retire 1 allumette, il en reste 5.
B peut retirer n'importe quel nombre entre 1 et 2 (2 = 2�1)
B retire 1 allumette, il en reste 4.
A peut retirer n'importe quel nombre entre 1 et 2 (2 = 2�1)
A retire 1 allumette, il en reste 3.
B peut retirer n'importe quel nombre entre 1 et 2 (2 = 2�1)
B retire 2 allumettes, il en reste 1.
A retire la derni�re allumette, il a gagn�.

Noter que B aurait pu ne retirer qu'une allumette � son dernier coup,
mais �a n'aurait rien chang� parce que A aurait pu retirer les deux
derni�res allumettes et gagner quand m�me.
==========================================================================


[�] Pour info, j'ai eu un tel programme (pas en python !) dans une
calculette TI 58 dot�e d'une m�moire (programme + donn�es) de 480
octets. Ce programme �tait capable de gagner syst�matiquement d�s
qu'il �tait dans une situation permettant de le faire. Je crois m�me
que le programme pouvait tourner sur une TI 57 (seulement 50 octets
de m�moire disponibles pour le programme, les donn�es �tant � part).

-- 
Olivier Miakinen