Du simple au double

 Niveau énigmesPartager :
			        
Du simple au double
Posté par 
Imod  18-02-20 à 18:42
 Bonsoir à tous 

Ces derniers temps on a proposé pas mal de problèmes d'allumettes , ils font partie de ceux que j'affectionne particulièrement car avec eux on ne sait jamais vraiment où l'on va .

Les variantes du jeu de Nim :  Wythoff , Grundy , Northcott , … sont souvent impressionnantes . 

J'ai passé des heures ( sans aboutir ) à essayer de comprendre comment faire des sommes de Nim avec le jeu du paysage .

Pourtant la règle est simple : on construit un décors en allumettes de façon à ce que chacune d'entre elles soit reliée ( parfois en plusieurs points ) à la ligne de sol . Le jeu se joue à deux , chacun retire à son tour une allumette et se débarrasse de toutes celles qui ne sont plus reliées au sol . Celui qui ne peut plus jouer a perdu .

 Quelles sont les positions gagnantes et les stratégies associées ????? 

Un problème moins ambitieux :

On a un tas d'allumettes que deux joueurs vont devoir vider .  Le premier en retire une ou deux et ensuite chacun à son tour va devoir retirer entre une allumette et le double du retrait précédent .

Celui qui ne peut plus jouer a perdu .

Si chacun joue au mieux , qui va gagner et comment ?

Amusez-vous bien 

Imod   
 Posté par 
trapanglere : Du simple au double  18-02-20 à 20:33
Bonsoir Imod,

Je ne suis pas sûr de comprendre...

Le premier jeu se joue-t-il en 2 ou 3 dimensions ? "ligne de sol" me fait penser à deux dimensions, mais alors je ne vois pas comment le fait de retirer une allumette peut en déconnecter d'autres du sol. Les allumettes restantes bougent-elles après qu'on en ait retiré une, comme au mikado ?

Pour le deuxième jeu, "entre une allumette et le double du retrait précédent" : n'importe quel nombre entre ces deux bornes ? ou bien est-ce l'un ou l'autre ? Si c'est l'un ou l'autre, le joueur peut-il choisir, ou bien ne peut-il prendre une allumette que quand il ne reste plus qu'une allumette en jeu?
 Posté par 
Imodre : Du simple au double  19-02-20 à 10:31
Bonjour Trapangle

Le jeu du paysage se joue dans le plan ( par exemple sur une feuille quadrillée ) .

Voici un exemple ( la ligne de sol est en vert ) :

Le retrait de l'allumette 2 n'occasionne aucun dégât mais celui de la 1 fait tomber le parasol au passage .

Pour le jeu du double on peut choisir toute valeur entre 1 et le double du retrait précédent .

Imod 
 Posté par 
matheuxmatoure : Du simple au double  19-02-20 à 18:07
bonjour

je pense que le sujet principal est "du simple au double"...

 Cliquez pour afficher
Si une position du jeu est représentée par le couple (a;n) où "a" est le nombre restant dans le tas et "n" le nombre d'allumettes qui ont été prises au coup précédent, on remarquera que :

(0;n) est une situation perdante

(1;n) et (2;n) sont des situations gagnantes

(a;n) avec 2na est une situation gagnante

je continue à chercher 
 Posté par 
matheuxmatoure : Du simple au double  19-02-20 à 18:18
suite 1...

 Cliquez pour afficher
je soupçonne que les situations perdantes sont celles du type

(a;n) avec a>2n et où "a" est un terme de la suite :

3 - 5 - 8 - 12 - 18 - 27 ....

définie par

u0=3

u1=5

un+2=un+1 + un - n
 Posté par 
matheuxmatoure : Du simple au double  19-02-20 à 18:30
suite 2 ...

 Cliquez pour afficher

en fait si on appelle (Fn) la suite de Fibonacci initialisée à F0=2 et F1=3, la suite (u) définie dans mon post précédent est uk=Fk + (k+1)
 Posté par 
matheuxmatoure : Du simple au double  19-02-20 à 18:44
suite 3 ...

 Cliquez pour afficher
pour résumer la stratégie...

on prend la suite de Fibonacci : 2 - 3 - 5 - 8 - 13 - 21 - 34 - ...

on ajoute à chaque terme son rang (le premier est de rang 1) :

on obtient la suite (P) : 3 - 5 - 8 - 12 - 18 - 27 - 41 - ....

pour gagner, il faut laisser à l'adversaire (hormis 0), un nombre p d'allumettes appartenant à cette suite, en en prenant n de telle façon que 2n<p

il me semble... 
 Posté par 
Imodre : Du simple au double  19-02-20 à 18:50
@Mateuxmatou

Le problème du double est bien celui que je propose et Il y a bien du Fibonacci là dessous .

J'ai évoqué le problème du paysage car comme la suite de Syracuse il a empoisonné mes années lycée et je vous refile le bébé comme un cadeau pourri  

Imod 
 Posté par 
Imodre : Du simple au double  19-02-20 à 18:53
Suite à la suite 3

Le plus intéressant est comme toujours de justifier .

Imod 
 Posté par 
matheuxmatoure : Du simple au double  19-02-20 à 18:54
Imod

 Cliquez pour afficher
et donc es-tu d'accord avec la stratégie proposée ?
 Posté par 
matheuxmatoure : Du simple au double  19-02-20 à 18:54
Imod

j'y travaille mais c'est un peu long à rédiger... ça viendra 
 Posté par 
Imodre : Du simple au double  19-02-20 à 19:00
Tant que je n'ai pas de preuve je ne peux rien confirmer ou infirmer ( je sais , je suis très ch... ) 

Imod

PS : tu es bien parti . 
 Posté par 
matheuxmatoure : Du simple au double  19-02-20 à 19:00
Imod

non non, t'as raison ! c'est le principe de base des mathématiques 
 Posté par 
matheuxmatoure : Du simple au double  20-02-20 à 12:05
Bon... on oublie tout ce que j'ai dit ! je me suis vautré ! on recommence 

 Cliquez pour afficher
si on note (a;n) la situation devant laquelle on se trouve où a est le nombre d'allumettes restantes et n le nombre que l'adversaire a pris le coup d'avant :

les (0;n) sont perdantes !

les (a;n) avec 2na sont évidemment gagnantes

et il semblerait que les autres perdantes (pour a>0) sont :

les (Fk ; n) où Fk est un terme de la suite de Fibonnaci (3-5-8-13-21...) et 2n<Fk

ainsi que les (Fk+3i ;1) où Fk est un terme de la suite de Fibonnaci (3-5-8-13-21...) et Fk < Fk+3i < Fk+1

bon, il reste à le démontrer !
 Posté par 
matheuxmatoure : Du simple au double  20-02-20 à 13:33
Bon c'est pas encore ça ... on va y arriver 
 Posté par 
matheuxmatoure : Du simple au double  20-02-20 à 21:31
cette fois cela me semble bon !

 Cliquez pour afficher
on considère la suite de Fibonacci : 1-2-3-5-8-13-21-...

la décomposition d'un nombre a en base de Fibonacci consiste à procéder comme avec les puissances d'un base classique : on cherche le plus grand inférieur, on le soustrait ... etc... (on démontre que tout nombre se décompose ainsi)

par exemple 17 = 13 + 3 + 1 = [100101]F

on remarquera que, par construction de la suite, il ne peut y avoir deux "1" consécutifs puisque la somme de deux termes consécutifs donne le terme suivant. 

Avec cette particularité, la décomposition est unique.

j'appelle f(a) le plus petit nombre de Fibonacci intervenant dans la décomposition.

par exemple f(17)=1 ; f(11)=3 ; f(21)=21 ...

Pour (a;n) une situation du jeu où a>0 est le nombre d'allumettes restantes et n le nombre pris par l'adversaire au coup précédent :

Cette situation est gagnante si et seulement si 2n  f(a) et le coup à jouer consiste à prendre f(a) allumettes dans le tas

Toutes les autres (en plus des (0;n) ) sont perdantes.

Démonstration à suivre mais je n'aurais pas le temps avant une semaine 
 Posté par 
Imodre : Du simple au double  20-02-20 à 22:41
C'est la bonne méthode et en effet la démonstration est un peu technique : prends ton temps 

Imod
 Posté par 
matheuxmatoure : Du simple au double  27-02-20 à 10:44
oui, la démonstration soignée est un peu technique à mettre en place ... je me contente ici d'en donner les grandes lignes et les pistes...

 Cliquez pour afficher
je reprends les notations du 20/02 à 21:31

un résultat important sur la suite de Fibonacci est que , avec F1=1 et F2=2, pour tout p  2, 

2Fp  Fp+1 > 2Fp-1

Soit G l'ensemble des situations (a;n) où 2n  f(a)

et P les autres

Si (a;n)est dans G avec f(a)=Fi

en prenant Fi allumettes dans le tas, on en laisse :

soit b=0 et l'adversaire a perdu

soit b tel que f(b)=Fj avec j  i+2

et puisque f(b) = Fj  Fi+2 > 2Fi

la situation (b;Fi) laissée à l'adversaire est dans P

Si (a;n) est dans P, avec a>0 ,  f(a)=Fi et 2n < Fi

remarquons que dans ce cas, i  3 puisque n  1

en base de Fibonacci, la décomposition de a se termine par un "1" suivi de (i-1) "0".

en prenant q allumettes, avec 1  q  2n < Fi l'adversaire nous en laisse b=a-q et la soustraction des q allumettes donne une décomposition de b telle que f(b) = Fj avec j < i

remarquons que si j=1 ou 2, il est évident que (b;q) est dans G

si j  3, pour obtenir a = b+q sachant que a se termine pour (i-1) zéros et b par (j-1)  zéros, avec j < i, il est nécessaire que q se termine par un "1" en position k, suivi de (k-1) zéros, avec k  j-1

pour l'établir il est plus simple de travailler pas contraposée.... si k <  j-2, la décomposition en Base de Fibonacci de b+q s'obtient en intercalant au moins un "1" dans les (j-2) zéros à droite de b et ne peut donner une suite de (i-1) zéros pour obtenir a.

donc : 2q  2Fj-1  Fj = f(b)

et donc quoi que joue l'adversaire, il laisse la situation (b;q) qui est dans G

CQFD comme on disait dans le temps 
  Posté par 
Imodre : Du simple au double  27-02-20 à 17:34
En effet ça a l'air de tenir la route 

J'avais procédé par récurrence sur le nombre de termes de la décomposition mais de toute façon ça nécessite quelques lemmes techniques .

La stratégie est facile à mettre en oeuvre par une machine , il suffit de choisir ( quand cela est possible ) , un nombre d'allumettes égal au dernier terme de la décomposition ( pas évident pour un humain étourdi ) . 

Imod