TI-62 Galaxy

[Andromede]

Merci pour le lien. En effet, le sujet a été très bien traité Par contre, je me demande toujours si on lui a trouvé un domaine d'application ou c'est resté uniquement au stade d'énigme mathématique

[C.Ret]

L'objectif des mathématiques n'est pas nécessairement d'être appliquées. Evidemment, il y a l'apport incontestable des mathématiques dans les applications quotidiennes et pragmatiques.

Mais le fait que la Conjecture de Syracuse ne soit pas (encore) démontrée rigoureusement et mathématiquement bien que vérifié sur des milliards de milliards de nombres initiaux par les progrès du calcul électronique pose un intéressant problème en soi.

Les mathématiques seraient-elles incomplètes ou inopérantes à considérer certains problèmes pourtant simple à poser ? Gödel aurait-il raison ?

[Andromede]

Bonjour,
En fait, pour le code précédent relatif à la Conjecture de Syracuse, il s'agit de la suite de Syracuse compressée car :
si u(n) est impair alors u(n+1) = 3*u(n) / 2.
Par contre, pour une suite classique, si u(n) est impair alors u(n+1) = 3 x u(n) + 1
J'ai donc modifié légèrement le code

Code : Tout sélectionner

--------------------------------------------
Ordinateur de poche
N°6 Mai-Juin 82
Page 76
Conjecture Tchèque
TI-57 réadapté sur TI-62 GALAXY
Version 2.0
--------------------------------------------
00	STO 0
01	STO 1
02	0
03	STO 2
04	LBL 1
05	1
06	ST+ 2
07	0
08	x <> t
09	RCL 0
10	/
11	2
12	=
13	FRAC
14	x différent t
15	GTO 2
16	1
17	x <> t
18	RCL 0
19	/
20	2
21	=
22	STO 0
23	PAUSE
24	x = t
25	GTO 3
26 	GTO 1
27 	LBL 2		#------------------------------------#
28	RCL 0		#                                            	
29	*		#                                            
30	3		#        Sous-programme de        
31	+		#        calcul de                         
32	1		#        u(n+1) = 3 x u(n) + 1       
33	=		#                                            
34	STO 0		#                                             
35	PAUSE		#------------------------------------#
36	GTO 1
37	LBL 3
38	RCL 1
39	R/S
40	RCL 2
41	R/S

Le fonctionnement est identique au précédent programme (version 1.0). Il affiche donc :
1. L'ensemble des nombres constituant la suite de Syracuse avec des temps de pause
2. Le temps de vol

Il reste encore à l'améliorer en vue de calculer également :
1. Le temps de vol en altitude
2. L'altitude maximale

[Andromede]

Bonjour,
J'ai complété le programme précédent dans sa version 2.0 afin de prendre également en charge l'affichage du temps de vol en altitude

Code : Tout sélectionner

--------------------------------------------
Ordinateur de poche
N°6 Mai-Juin 82
Page 76
Conjecture Tchèque
TI-57 réadapté sur TI-62 GALAXY
Version 3.0
--------------------------------------------
00	STO 0
01	STO 1
02	0
03	STO 2
04	0		#----- Initialisation du Registre R3 destiné à
05	STO 3		#----- à recevoir la valeur du temps de vol en altitude
06	LBL 1
07	1
08	ST+ 2
09	0
10	x<>t
11	RCL 0
12	/
13	2
14	=
15	STO 4
16	FRAC
17	x différent de t
18	GTO 2
19	RCL 4
20	STO 0
21	PAUSE
22	0		#------------POUR a PAIR-------------------------------
23	x<>t		#  Tant que le Registre R3 n'est pas vide	
24	RCL 3		#  alors continuer à chercher 
25	x=t		#  le temps de vol en altitude
26	SBR 5		#------------------------------------------------------
27	1
28	x<>t
29	RCL 0
30	x=t
31	GTO 3
32	GTO 1
33	LBL 2
34	RCL 0
35	*
36	3
37	+
38	1
39	=
40	STO 0
41	PAUSE
42	0		#-----------POUR a IMPAIR------------------------------
43	x<>t		#  Tant que le Registre R3 n'est pas vide
44	RCL 3		#  alors continuer à chercher
45	x=t		#  le temps de vol en altitude
46	SBR 5		#------------------------------------------------------
47	GTO 1
48	LBL 3
49	RCL 1
50	R/S
51	RCL 2
52	R/S
53	RCL 3
54	R/S
55	LBL 5		#--------------------------------------------------#
56	RCL 1		#
57	x<>t		#   Sous-programme de recherche 
58	RCL 0		#   du temps de vol en altitude 
59	x<t		#   et sauvegarde de sa valeur 
60	STO 3		#   dans le registre R3
61 	RTN		#--------------------------------------------------#

Il reste encore à rechercher l'altitude maximale

[Andromede]

Bonsoir,
Voici la version complète du code calculant, pour une suite de Syracuse :
1. Le temps de vol
2. Le temps de vol en altitude
3. L'altitude maximale

Code : Tout sélectionner

--------------------------------------------
Ordinateur de poche
N°6 Mai-Juin 82
Page 76
Conjecture Tchèque
TI-57 réadapté sur TI-62 GALAXY
Version finale
--------------------------------------------
00    LBL 1
01    1
02    ST+ 2
03    0
04    x<>t
05    RCL 0
06    /
07    2
08    =
09    STO 4
10    FRAC
11    x diffèrent t
12    GTO 2
13    RCL 4
14    SBR 6
15    1
16    x<>t
17    RCL 0
18    x=t
19    GTO 3
20    GTO 1
21    LBL 2
22    RCL 0
23    *
24    3
25    +
26    1
27    =
28    SBR 6
29    GTO 1
30    LBL 3
31    RCL 2
32    R/S
33    RCL 5
34    -
35    1
36    =
37    R/S
38    RCL 6
39    R/S
40    LBL 5
41    1
42    ST+ 5
43    RCL 1
44    x<>t
45    RCL 0
46    x<t
47    STO 3
48    RTN
49    LBL 6
50    STO 0
51    PAUSE 
52    RCL 6
53    x<>t
54    RCL 0
55    x>t
56    STO 6
57    0
58    x<>t
59    RCL 3
60    x=t
61    SBR 5
62    RTN

--------------------------------------------------
Initialisation des registres
2nd STO (CM)
ON/C
ON/C
RST
X STO 0 (avec X le nombre de départ)
STO 1
R/S
--------------------------------------------------
Exemple
15 STO 0
STO 1
R/S
--------------------------------------------------
Résultats
Le temps de vol : 17
R/S
Le temps de vol en altitude : 10
R/S
L'altitude maximale : 160

[Andromede]

LE JEU DES ALLUMETTES
Un jeu très connu et qui a été repris sur plusieurs ordinateurs de poche. J'ai adapté le jeu sur la TI-62 et cela fonctionne très bien sans pour autant en comprendre tout le raisonnement de l'auteur. Je souhaite savoir quel a été le principe général utilisé pour arriver à ce code car je ne m'y retrouve point ?

Code : Tout sélectionner

---------------------------------------------
L'Ordinateur Individuel
N° 19 Juillet - Août 1980 Page 62
Le jeu des allumettes sur TI 57
Adapté sur TI-62 Galaxy
Version 1.0
---------------------------------------------
00	STO 1
01	+
02	3
03	LBL 1
04	-
05	4
06	=
07	X=T
08	GTO 4
09	X>T
10	GTO 1
11	X<=T
12	GTO 2
13	LBL 4
14	STO 2
15	1
16	ST+ 0
17	RCL 0
18 	-
19	(
20	RCL 0
21	/
22	3
23	)
24	INTG
25	*
26	3
27	+
28	1
29	=
30	ST+ 2
31	RCL 2
32	GTO 3
33	LBL 2
34	+
35	4
36	=
37	LBL 3
38	PAUSE
39	PAUSE
40	ST- 1
41 	RCL 1
42	-
43	R/S
44	=
45	PAUSE
46	PAUSE
47	X Différent T
48	RST
49	GTO 8

[Schraf]

@Andromede : Numworks vient de publier ce matin une version de ce jeu pour leur calculatrice.

Il existe un autre programme qui fait intervenir le nombre d'or (L'Ordinateur Individuel 77 HS (déc 1985) page 48). Il faudra que je me plonge dedans pour comprendre le principe.

Pour ma part, j'avais fait une vidéo sur le jeu de Nim avec les explications pour pouvoir gagner, plus précisément "Je peux perdre, mais je gagne toujours"

Voici l'algo utilisé pour le programme proposé par Numworks, pas spécialement optimisé ! allumettes désigne le nb d'allumettes restantes.

Code : Tout sélectionner

if allumettes==19:
    draw_string("Vous avez gagné",100,30)
  else:
    if (20-allumettes)%4==3:
      allumettes+=2
    else:
      if (20-allumettes)%4==0:
        allumettes+=3
      else:
        if (20-allumettes)%4==2:
          allumettes+=1
        else:
          allumettes+=randint(1,3 if allumettes<17 else 20-allumettes-1)

Pour ta question :

- Ce qui me surprend le plus c'est l'intervention de la mémoire n°0, qui n'est même pas initialisée quand on lit l'article et il y a pourtant un SUM 0 (soit STO+0) dans le programme. Je pense que c'est pour tirer un nombre "au hasard" comme dans le "else" du programme ci-dessus.
- Le début (lignes 00 à 10), c'est le calcul de [(N+3) modulo 4] - 4 où N est le nombre d'allumettes restantes. Par exemple pour N = 20 ça fera (23 mod 4) - 4 = 3 - 4 = -1.
- Par exemple si N%4 == 3 alors (N+3)%4 = 2 qui est traduit en if (20-allumettes)%4==3: allumettes+=2 (où N = 20-allumettes). On retrouve les autres cas N%4 == 0 et N%4 == 2. C'est le cas N%4 == 1 qui fait que l'on choisit un nombre au hasard (Lbl 4 dans le programme)

Bref, pour moi l'algo utilisé pour la Ti-57 est exactement le même que celui publié par NUMWORKS ce matin.

J'ai donc juste déplacer le problème, il faut maintenant comprendre l'explication mathématique qui est basée sur :

Si celui qui prend la dernière perd, à votre tour, vous devez laisser un nombre d'allumettes correspondant à un multiple de 4 plus 1, c'est-à-dire : 1, 5, 9, 13, 17, 21, 25, 29, 33, ... Ainsi, le nombre d'allumettes diminuant, vous laisserez forcément la plus petite position possible, c'est-à-dire 1 allumette. L'autre aura perdu.

[Schraf]

Je viens d'écrire ce petit programme en Python qui fait la même chose que pour la Ti-57 et la Numworks :

Code : Tout sélectionner

from random import randint

def jeu(n):
  while True:
    if n == 0: return "Tu perds"
    if n == 1: return "Tu gagnes" 
    t = (n-1) % 4
    if t == 0: t = randint(1,3)
    n -= t
    print("J'enleve",t)
    print("Reste",n, "allumettes") 
    r = int(input("A toi (1-3) : "))
    n -= r

J'ai joué et... j'ai perdu. Le seul moyen de gagner est de lui donner un nombre initial du type 1 + 4 * K et uniquement dans ce cas il tirera des valeurs au hasard entre 1 et 3 et nous on s'arrange pour rester sur la série 1, 5, 9, 13, 17, 21, 25, 29, 33, ...

[Schraf]

Ma proposition pour la Ti-57 (en se basant sur l'algo Python) : Démo en vidéo

Code : Tout sélectionner

00 32 1 	STO 1		# Nb N d'allumettes en mémoire 1
01 22		x ≷ t		# Copie de N dans la mémoire 7
02 01		1		# Si N <= 1 la partie est finie
03 76		x ≥ t
04 51 4		GTO 4		# Label inexistant = clignotement
05 -34 7	INV SUM 7	# N - 1 en mémoire 7
06 22		x ≷ t		# Calcul de (n-1) % 4
07 45		÷
08 04		4
09 85		=
10 -49		INV 2nd Int
11 55		×
12 04		4
13 85		=
14 19		2nd C.t		# 0 dans Mémoire 7
15 66		x = t
16 61 1		SBR 1		# Tirage aléatoire
17 -34 1 	INV SUM 1	# N = N - nombre d'allumettes choisies par machine
18 36		Pause
19 33 1		RCL 1
20 65		-
21 81		R/S		# Affichage nb allumettes et attente coup joueur
22 85		=
23 71 		RST
24 86 1		Lbl 1		# Tirage d'un nb entre 1 et 3
25 33 1		RCL 1		# La graine est le nb d'allumettes restantes
26 -13		INV lnx		# exponentielle (pour avoir de fortes variations)
27 -49		INV 2nt Int	# Partie fractionnaire
28 55		×
29 03		3
30 85		=
31 49		2nd Int
32 75		+
33 01		1
34 85		=
35 -61		INV SBR

[Schraf]

Concernant l'aspect mathématique des situations gagnantes, je vous propose une petite démonstration par récurrence :

Montrons que la situation S(n) = 1 + 4 * n allumettes est gagnante pour nous :

- Si n = 0, S(0) = 1 et la situation est bien gagnante puisque notre adversaire devra retirer la dernière allumette.

- Supposons que S(n) soit gagnante et montrons que S(n+1) l'est également (principe de la récurrence) :

Il y a S(n + 1) = 1 + 4 * (n + 1) = 5 + 4 * n allumettes sur la table
Notre adversaire enlève q allumettes (q = 1, 2 ou 3)
A notre tour enlevons 4 - q allumettes (qui est également un chiffre entre 1 et 3)
Il reste sur la table S(n + 1) - 4 = 1 + 4 * n = S(n) allumettes qui est une situation gagnante. CQFD

[C.Ret]

Bien, voilà qui répond à la question de Andromede concernant le pourquoi et le comment de la stratégie programmée dans son code issue de la revue.

Code : Tout sélectionner

Situation	Gagnante	Meilleurs		Situation	Gagnante	Meilleurs
Initiale	suivante	coup			Initiale	suivante	coup
20		17		3			10		9		1
19		17		2			 9		9		0 (*)
18		17		1			 8		5		3			
17		17		0 (*)			 7		5		2
16		13		3			 6		5		1
15		13		2			 5		5		0 (**)
14		13		1			 4		1		3
13		13		0 (*)			 3		1		2
12		 9		3			 2		1		1
11		 8		2			 1		perdu

(*) A défaut de pouvoir passer son tours, jouer aléatoirement.
(**) Si vous arrivez ici c'est certainement que votre adversaire sait jouer. Donc, vous jouerez, mais quelque soit le tirage aléatoire, il y a de fortes chances que ce soit déjà perdu !



Mais, je me suis penché sur le petit programme utilisant le nombre d'or, et je n'ai pas réussi à faire le lien !

Qui prend la dernière gagne le nombre d'or.png (12 Kio) Vu 4210 fois

Dans ce petit programme, les règles sont plus proches du Jeu de Nims, chaque joueur pouvant prendre tout ou partie de l'un des deux tas d'allumettes ou éventuellement le même nombre d'allumettes dans les deux tas.

[C.Ret]

J'ai trouvé un bug dans ce petit programme. Une fois corrigé, il est bien plus difficile à battre;
Et j'ai compris d'où vient l'utilité du nombre d'or

Qui prend la dernière gagne le nombre d'OR (corrected).png (13.13 Kio) Vu 4205 fois

[Schraf]

Quelques explications en vrac sur l'apparition du nombre d'or dans le programme de l'OI HS n°77 en utilisant cette vidéo

Règle : il y a 2 tas d'allumettes (que nous appellerons paire) et chaque joueur peut retirer soit un nombre quelconque de l'un des 2 tas, soit le même nombre des 2 tas à la fois. Le gagnant est celui qui retire la dernière allumette.

On notera (X ; Y) les nombres d'allumettes des 2 tas avec X ≤ Y

Remarquons que :

- La paire (1 ; 2) càd 1 allumette pour un tas et 2 allumettes sur l'autre tas est gagnante pour nous. Que l'adversaire enlève 1 allumette du 1er tas, 2 allumettes du 2e tas ou 1 allumette de chaque tas, nous enlèverons la dernière allumette.

- Si la paire (X ; N) est gagnante alors la paire (Y ; N) avec Y > X ne peut pas être gagnante. En effet notre adversaire enlèverait le nombre nécessaire d'allumettes pour passer de Y à X et serait dans une position gagnante.

- Il ne peut pas y avoir 2 configurations gagnantes du type (X, X+N) et (Y, Y+N), càd avec la même différence entre le max et le min. En effet l'adversaire n'aurait qu'à enlever X - Y allumettes des 2 tas pour passer de (Y, Y+N) à (X, X+N).

- On peut déduire des 2 propriétés précédentes que les nombres entiers ne peuvent apparaitre qu'une seule fois (à part le couple (0,0) qui est la fin du jeu)

On obtient les positions gagnantes suivantes :

(0,0) : Fin du jeu, j'ai gagné
(1,2) : différence = 1
(3,5) : 3 est le plus petit nombre qui n'est pas encore apparu et la différence ne doit être ni 0 ni 1, d'où le 5
(4,7) : 4 est le + petit non apparu et différence 3
(6,10) : différence = 4
(8,13) : différence = 5
etc.

Il faut alors voir que les paires sont de la forme... ([nφ] , [nφ²]) où [...] désigne la partie entière et φ le nombre d'or.
Ensuite il montre que tous les entiers p peuvent être écrits sous la forme [nφ²] - [nφ] (on aura donc toutes les différences possibles entre les 2 tas)
Et que chaque entier n'apparait qu'une seule fois : L'hypothèse p = [mφ] = [nφ²] avec m ≠ n mène à une contradiction.

Je n'ai pas repris le programme en BASIC, mais j'imagine qu'à partir d'une position (X,Y) il cherche n tel que l'on puisse arriver à une position gagnante ([nφ] , [nφ²])

[Andromede]

Bonjour,
Vraiment très instructif . J'étudie actuellement chacune de vos explications et de façon minutieuse pour pouvoir les assimiler correctement

[Schraf]

Merci @Andromede, mon but est aussi de comprendre...

Version 2 en Python lorsqu'il y a 2 tas et que l'on utilise le nombre d'or, vous pouvez le tester ici par copier-coller :

Code : Tout sélectionner

from random import randint
from math import sqrt

def jeu():
    phi = (1 + sqrt(5)) / 2					# Nb d'or
    a, b = randint(20,100), randint(20,100)			# Nb d'allumettes par tas
    while a + b > 0:
        print("> {} dans A et {} dans B <".format(a,b))
        while True:						# L'humain choisit les 2 valeurs
            try:
                tasA = int(input("Tas A ? "))
                tasB = int(input("Tas B ? "))
                if tasA * tasB * (tasA - tasB) == 0: break
            except: continue
        a, b = a - tasA, b - tasB				# Nouveaux tas
        print("> {} dans A et {} dans B <".format(a,b))
        if a + b == 0: 
            print("Vous gagnez !")
            return
        t1 = min(a,b)			# On recherche la paire gagnante de nb d'or qui a comme
        n = abs(max(a,b) - t1)		# différence la même que les tas
        if int(n * phi) <= t1:		# Ce sera ok si le nb a enlevé est < au mini des 2 tas
            r = t1 - int(n * phi)
            print("Je retire {} des 2 tas".format(r))
            a, b = a - r, b - r
        else:				# Sinon on cherche la paire gagnante en partant du tas minimum
            n = 0
            while t1 not in [int(n * phi), int(n * phi * phi)]: n += 1	# Recherche de n
            r1, r2 = int(n * phi), int(n * phi * phi)	# Paire gagnante
            if a == r1 or a == r2:			# On cherche le tas où l'on doit ôter les allumettes
                print("Je retire {} du tas B".format(b - r2 - r1 + a))
                b = r2 + r1 - a
            else:
                print("Je retire {} du tas A".format(a - r2 - r1 + b))
                a = r2 + r1 - b           
    print("Je gagne !")

jeu()

Il manque la partie où c'est une situation gagnante pour le joueur, dans ce cas la machine s'obstine à jouer "Je retire 0 des 2 tas" pour rester elle-aussi gagnante, sacrée tricheuse quoi...

Comme ça j'ai envie de dire que c'est adaptable sur la TI-62 GALAXY mais bon...