Bonsoir,
c'est un jeu type Nim.
Si les deux joueurs connaissent les positions gagnantes celui qui choisit la position de départ perd toujours : si il choisit une position gagnante l'autre choisit de commencer, si il choisit une position perdante l'autre le laisse commencer.

Je sais bien mais il est nettement moins connu je pense en tout cas j'ai cherché exprès des articles dans ce but. Avant que tout le monde sache reconnaitre les positions gagnantes / perdantes et sache comment exploiter cet avantage, ça n'empêche pas de jouer.

C'est un peu le but de la manœuvre de les identifier en jouant avec un autre adversaire mais si tu préfères réfléchir seul pour nous expliquer ensuite ta stratégie, n'hésite pas.

L'objectif reste le même, trouver comment gagner !

Bonjour,
Je ne participerai pas.
Je vais quand même revenir sur le jeu de Marienbad qui est une
version fixe de ces jeux d'allumettes.(1 3 5 7)
Le film est sorti quand j'étais à la fac en 1961 et je me suis enrichi *
en gagnant  avec la méthode suivante:

a) je connais par coeur toutes les positions gagnantes.
b )je fixe un temps maximum :  30 secondes.
c) je laisse mon adversaire commencer tant qu'il ne me demande pas de le faire....et dans ce cas je gagne si le jeu dépasse le temps.


*quelques Nouveaux Francs.....

Bonjour,
c'est un peu contradictoire :

 Cliquez pour afficher

équivalent à retirer une seule allumette à chaque coup d'un jeu de Nim à nombre de tas variable,
ou deux à une extrémité : si on coupe en L-2, 1, 1 les deux morceaux de 1 sont éliminés,
le calcul des nombres de Grundy se fait de proche en proche par la méthode habituelle
et l'exploitation de ces nombres de Grundy se fait alors de la façon habituelle (par nim-addition ayant pour but d'obtenir 0 à chaque coup gagnant)

Bonjour mathafou, excellente idée de transformer en discret, ce sera peut-être plus parlant
Je suis en grande partie d'accord avec ton analyse (j'ai mis 3 morceaux de rubans pour ne pas m'embêter car on ne peut pas promettre qu'on aura 2 morceaux de rubans non plus si l'un d'entre eux fait moins de 1cm)
Mais je ne pige pas pourquoi tu dis qu'on n'enlève qu'une seule allumette en dehors des extrémités.

EX : longueur 10cm donc 9 coupes maximum à l'origine
Je peux couper 1+9 ce qui donne 1 ruban de 9 cm utilisable donc 8 coupes maximum
Je peux couper 1+1+8 ce qui donne 1 ruban de 8 cm utilisable donc 7 coupes maximum
Je peux couper 2+1+7 ce qui donne 2 rubans de 2cm et 7cm utilisables donc 1+6=7 coupes maximum
Je peux couper 2,5+1+6,5 ce qui donne 2 rubans de 2,5cm et 6,5 cm utilisables donc 2+6=8 coupes maximum

Pour transformer en discret :
- si est un entier alors on remplace par allumettes
- si n'est pas un entier on rempalce par allumettes où est la partie entière de
A chaque tour, on enlève 1 ou 2 allumettes et si il en reste plus qu'une, on sépare si on a envie le tas d'allumettes restants comme on veut.
Mais comme on a le choix d'enlever 1 ou 2 allumettes, c'est quand même plus compliqué que Grundy en revanche, on a le droit de faire des tas égaux. Après si tu veux simplifier le jeu pourquoi pas, je ne suis pas contre.

Pour moi (en discret)

Longueur de 0 ou 1 cm n'existent pas (0 ou 1 allumette)
si on reçoit cette configuration (de rien du tout) on ne peut pas jouer (!) ce sont des positions perdantes G(0) = G(1) = 0

Longueur de 2cm (2allumettes)
on ne peut que retirer 1 allumette (à un des deux bouts) ce qui donne 1 donc 0
la position de 2 cm est donc gagnante et G(2) = 1 (plus petit nombre entier différent des G(x) de toutes les positions que l'on peut atteindre à partir de L=2)

Longueur de 3 : donne 2 (on coupe 1cm éliminé au bout, reste 2cm)
ou 1+1 = rien (3 bouts de 1cm tous trois éliminés)
comme on est dans la variante discrète (longueurs entières) des bouts de 1.5 ; 1 et 0.5 ça n'existe pas
la position est donc gagnante puisque on peut aboutir à rien (deux morceaux de 1cm restants et le morceau de 1cm enlevé tous trois éliminés = rien)
G(3) = le plus petit absent de 0 et de G(2) = 1 donc G(3 )= 2

on continue ainsi de proche en proche
mais ensuite ça se complique par des transformations d'un ruban en deux rubans (d'un jeu en deux jeux en parallèle) de longueur > 1 strictement (2, en nombres entiers)
pour lesquelles on est amené à faire intervenir la "nim-addition" des nombres de Grundy

ainsi : L = 10 donne
L = 9 (on coupe 1cm à une extrémité éliminé)
L = 8 (on coupe 1cm à 1 cm de une extrémité, deux morceaux de 1cm éliminés)
deux rubans de L = 7 et L = 2
L= 6 et L = 3
L= 5 et L = 4
et symétries identiques

la valeur du jeu G(10) est donc le plus petit entier absent de la liste G(9), G(8), G(7)G(2), G(6)G(3), G(5)G(4)

dans laquelle est la "nim-addition" (addition en binaire sans retenue = ou exclusif bit à bit)
par exemple 13 = 2, 73 = 4 etc

et la valeur d'un jeu composé de plusieurs rubans est la nim-addition des valeurs de chacun des rubans (comme toujours à toutes les variantes du jeu de Nim)

tous ces calculs faits à la main sont un peu pénibles (et avec risque d'erreurs)
quand j'aurais du temps je modifierai le programme de calcul des G(n) d'un autre jeu du même genre programmé jadis (en JavaScript)
jeu des quilles
ici (les rubans) c'est différent car on ne peut faire "tomber deux quilles" / allumettes que uniquement à une extrémité :
retirer 2cm au milieu est illégal,
retirer 1cm à 1cm de une extrémité équivaut à retirer 2cm = 2 quilles / allumettes, seul cas où on peut en retirer 2

Ben en fait il me semble que ton jeu de quilles est exactement équivalent à ce que je propose (une fois discrétisée comme je l'ai expliqué) donc merci comme ça tout le monde peut s'entrainer, trop bien ! Magnifique boulot, vraiment

Je ne suis toujours pas convaincue par ton histoire de 1 quille, c'est le contraire, si tu ne joues que avec des longueurs entières, tu enlèveras toujours 2 quilles sauf si tu coupes à une extrémité.
C'est ce que j'ai voulu montrer avec mon exemple...
Raisonnons autrement pour se mettre d'accord, tu as une longueur de ruban et tu marques toutes les graduations qui vont correspondre à toutes les coupes possibles.
Si tu coupes à une extrémité tu n'utilises qu'une graduation mais tu peux couper n'importe où ailleurs et tu vas utiliser 2 graduations donc enlever 2 quilles.
D'accord tu ne t'en rends pas compte tout de suite mais si tu passes de 10 à 7+2 et bien il ne reste que 6 coupes possibles dans le premier ruban et 1 coupe possible dans le deuxième ruban
Soit en tout 7 coupes, exactement comme lorsque tu fais un ruban de longueur 8. C'est la faute aux intervalles, créer une nouvelle extrémité cache le problème mais ça diminue de fait le nombre de coupe possible donc de quilles.
Tu vois ce que je veux dire ?

non, ce n'est pas équivalent
car dans mon jeu de quilles je peux retirer deux quilles n'importe où et pas seulement à une extrémité
avec toujours cet exemple de 10 cm / 10 quilles
les quilles permettent d'obtenir aussi 5 + 3 (en faisant tomber deux quilles au milieu)
00000XX000

les rubans ne donnent que 6 + 3 ou 5 + 4 (un seul morceau de 1cm retiré)
000000X000
00000X0000

et on ne peut pas obtenir 5+3

ce n'est pas du tout le nombre de coupes qui compte
c'est quelles coupes précisément.

Ben ça, c'est normal, c'est comme j'ai écrit parcequ'il faut prendre si est un entier.
Donc si j'ai 11 cm je peux faire 10 coupes (ou faire tomber 10 quilles).
Avec mes 11 cm, je peux faire 6+1+4 et je jete le 1 donc j'ai un ruban de 6cm où je peux faire 5 coupes et un ruban de 4cm où je peux faire 3 coupes.
Exactement comme toi mais si tu veux que j'enlève une seule quille, c'est pas difficile, il me suffit de couper en dehors d'une longueur entière.

Une dernière tentative pour te convaincre :

On ne peut plus couper à partir de 1cm, c'est quand même bien normal que cela corresponde à 0 quille où on ne peut plus rien faire non plus.

Si j'ai un ruban de 2cm je ne pourrai couper qu'une seule fois quoi que je fasse, c'est gagnant tu l'as dis.
Tout comme si tu as une seule quille dans le bloc, tu n'arriveras pas à faire tomber les voisines (j'ai essayé et ton jeu ne le permet pas).

Si j'ai un ruban de 3cm je peux couper en 1+1+1 pour gagner directement mais si je joue "très mal" je peux faire 0,5+1+1,5 (ou 1+2 mais cela revient exactement au même) et mon adversaire va gagner.
Tout comme si tu as deux quilles, tu peux faire tomber les deux pour gagner directement mais si tu joues "très mal" tu peux ne faire tomber qu'une seule quille

Etc, etc

je pense que tu ne prends pas cette histoire de nombres de Grundy par le bon bout...
encore une fois ce n'est absolument pas le nombre de coupes réalisables qui compte.

(et enlever moins de 1 cm complique énormément le problème : on est alors dans R et pas dans N)

par contre pour les rubans c'est en fait équivalent à retirer toujours une seule allumette / quille au tas de L (et pas de L-1)

car g(1) = 0 et donc g(x)g(1) = g(x)

reprenons notre ruban 10 cm
on obtient
9 (1 cm retiré au bout)
8 et 1 dont la valeur est g(L-2)g(1) = g(L-2)
c'est exactement comme si on avait retiré 2cm au bout (le cm retiré et le 1cm jeté)
7 et 2
6 et 3
5 et 4

et donc au final du calcul g(10) = 3, position gagnante à condition de jouer en coupant en 6 et 3
car g(6) = 2 et g(3)= 2 donc la position combinée 6 et 3 vaut 22 = 0, position perdante donnée à l'adversaire

les valeurs de g(n) (par un programme de quelques lignes en Python)
[0, 0, 1, 2, 0, 1, 2, 3, 1, 2, 3, 4, 0, 3, 4, 2, 1, 3, 2, 1, 0, ...]

le programme Python pour calculer ces nombres de Grundy (du jeu des rubans)

g=[0,0]
# g[0] = 0 et g[1] = 0 car on retire les tas de 1
# le reste de la liste vide
max=20
for n in range(2,max+1) :
    # calcul de g(n)
    # vide la liste des valeurs
    v=[0 for k in range(max+1)] # largement  dimensionnée
    for k in range(0,(n-1)//2+1):
        # de 0 à E((n-1)/2] inclus
        # coupe en un morceau de n-k-1 et un morceau de k
        # valeur g((n-k-1) ou exclusif g(k)
        v[g[n-k-1]^g[k]]= 1 # marque cette valeur
    g.append(v.index(0)) # g[n] = première valeur pas trouvée
print(g)

Euh mathafou, c'est toi qui a décidé qu'on ne pouvait pas couper autre chose que des longueurs entières et pourquoi pas, c'est intéressant.

Ce que moi je dis c'est que le jeu initial que j'ai proposé correspond parfaitement à ton jeu des quilles et il me semble que je l'ai expliqué justement en faisant correspondre le nombre de quilles au nombre de coupes possibles.
Donc si pour moi c'est le nombre de coupes possibles qui comptent. Tu t'entêtes à me dire que je ne peux pas faire cette correspondance, c'est un petit peu exagéré non ?

Ben désolé mais moi avec 10cm, je joue 4,5+1+4,5 j'ai le droit.
Maintenant tu peux bien faire ce que tu veux je ferai systématiquement la même chose sur le ruban symétrique donc si tu peux jouer alors je peux jouer.
A priori, je vais gagner. Traduction en quilles, j'ai 9 quilles, je fais tomber uniquement la quille du milieu et je ferai toujours ta stratégie quoi que tu fasses.
A toi de jouer que ce soit avec des rubans ou des quilles, je te ferai la correspondance à chaque fois.

Je me répète mais pour moi le jeu des rubans avec des longueurs entières correspond exactement aux jeu des quilles où je retire 2 quilles à chaque fois sauf si je tape sur les extrémités où je ne retire qu'une quille.
Dans ton exemple pour 10cm cela correspond toujours à 9 quilles et je vais donc faire tomber 2 quilles vers le milieu pour avoir 5 et 2 quilles.
Si cela peut te faire plaisir de le noter 6 et 3 parce que cela correspond au nombre de Grundy, volontiers, je ne vais pas te contrarier pour si peu mais tu rajoutes juste du +1 partout, ça ne change rien à l'histoire.
Bien évidemment que 5 et 2 quilles correspondent à des longueurs de 6 et 3 cm, c'est ce que je dis aussi depuis le début, là dessus on est d'accord.

PS : je gagne systématiquement s'il y a un seul ruban de taille l>1 avec les règles d'origine à savoir le jeu des quilles tel que tu l'as défini toi aussi.
pour 4cm par exemple : 1,5+1+1,5 à toi ? Autrement dit pour 3 quilles, je fais encore tomber celle du milieu car je suis têtue

OK, OK ..
mais !

pour le jeu d'origine avec des longueurs non entières, la stratégie évidente est comme tu le fais remarquer bien plus simple que de couper en 6 et 3 cm ! (qui serait la seule et unique méthode de gagner avec des longueurs toujours entières)

L = 10 je retire tout simplement 1cm exactement au milieu 4.5 + 4.5 et je gagne par symétrie
et ceci est valable quelle que soit la longueur du ruban sans aucune complication

reste à voir ce que donne une telle "stratégie de paires" avec n rubans ...

On va finir par réussir à se comprendre
Moi je pense que pour le jeu d'origine, tu sais le résoudre justement parceque tu sais résoudre ton jeu des quilles...
A ton avis pourquoi je t'embête à te dire qu'on peut transformer l'un en l'autre ? Ce n'est pas pour le plaisir de faire ma mauvaise tête.

Exemple
3 rubans de longueur 3.5 ; 3 ; 1.2 cm
Je transforme en jeu des quilles donc 3 ; 2 ; 1 quilles

- Si je fais 3.5 ; 3 ; 0.2 cm (équivalent 3 ; 2 ; 0 quilles)
Alors tu vas répondre 2.5 ; 3 cm (équivalent 2 ; 2 quilles)
Et j'ai perdu car tu feras toujours le symétrique sur l'autre ruban comme 3cm se traite exactement comme 2.5cm
Mettons que je fais 1+1cm pour jeter mon ruban de 3cm alors tu fais 0.5+1cm pour jeter ton ruban de 2.5cm et mettons que je fais 0.5+1.5cm pour que mon ruban soit encore utilisable une fois alors tu fais 0.25+1.25cm pour que ton ruban soit encore utilisable une fois

- Si je fais 3.5 ; 2 ; 1.2 cm (équivalent 3 ; 1 ; 1 quilles)
Alors tu vas répondre 1.25+1.25 ; 2 ; 1.2 cm (équivalent 1 ; 1 ; 1 ; 1 quilles)
Et j'ai encore perdu, symétrie oblige

- Si je fais 3.5 ; 1+1 ; 1.2 cm (équivalent 3 ; 0 ; 1 quilles)
Alors tu vas répondre 1+1.5 ; 1.2 cm (équivalent 1 ; 1 quille)
Et j'ai encore perdu, symétrie oblige

- Si je fais 2.5 ; 3 ; 1.2 cm (équivalent 2 ; 2 ; 1 quilles)
Alors tu vas répondre 2.5 ; 3 ; 0.2 cm (équivalent 2 ; 2 quille)
Et j'ai encore perdu, symétrie oblige

- Si je fais 1.25+1.25 ; 3 ; 1.2 cm (équivalent 1 ; 1 ; 2 ; 1 quilles)
Alors tu vas répondre 1.25 ; 1.25 ; 2 ; 1.2 cm (équivalent 1 ; 1 ; 1 ; 1 quille)
Et j'ai encore perdu, symétrie oblige

- Si je fais 1+1.5 ; 3 ; 1.2 cm (équivalent 1 ; 2 ; 1 quilles)
Alors tu vas répondre 1.5 ; 1+1 ; 1.2 cm (équivalent 1 ; 0 ; 1 quille)
Et j'ai encore perdu, symétrie oblige

Dis moi mathafou la position 3 2 1 ne serait-elle pas une position perdante pour ton jeu de quilles ? Et bien tu vois c'est pareil pour la position des rubans.

le problème est que je ne suis pas convaincu du tout d'une telle équivalence avec des rubans de longueur > 4 ...

des rangées de quilles "équivalentes" de plus de 3 quilles, pour lesquelles on peut retirer deux quilles dans le milieu
ce qui n'a pas lieu si il y a a moins de 4 quilles équivalentes
cette possibilité dans le jeu de quilles qui n'a aucune équivalence dans le jeu des rubans fait que la stratégie est forcément différente si des longueurs > 4 (strictement)

Je sais bien que tu n'es pas convaincu et pourtant je ne lache pas l'affaire. Ruban de taille 5cm (ou 4.1cm je m'en fiche) ce qui correspond à 4 quilles
-4 cm (ou 3.1cm) ce qui correspond à 3 quilles
-1.5+2.5cm (ou 1.05+2.05cm) ce qui correspond à 1+2 quilles
-2+2cm (ou 2+1.1cm) ce qui correspond à 1+1 quilles car désolé mais on ne peut jouer qu'une seule fois dans chaque ruban de 2cm. Je ne comprends pas ton blocage à ce sujet, c'est toujours 2 quilles qu'on enlève quand on coupe sur des longueurs entières

Une démonstration formelle risque d'être casse-pied à écrire mais je n'ai aucun doute à ce sujet.
Donne moi, un exemple de ce que je ne peux pas faire, tu verras que je pourrai toujours retirer 2 quilles au milieu sans problème.

Bon, je me suis décidée à écrire une démonstration formelle de l'équivalence entre les positions gagnantes de mon jeu de ruban et les positions gagnantes de ton jeu de quilles.

Notations
Soit si est un entier et sinon avec la partie entière. On a la propriété connue que si est un entier.
On considère que est l'entier correspond au nombre de quilles dans le bloc et on a par définition ou autrement dit .

Soit le nombre total de quilles, on va raisonner par récurrence sur .

Initialisation
Si alors la somme se fait sur une seule quille et on peut en déduire que cela correspond à un ruban de longueur . Cette position est gagnante en un coup pour les quilles et pour les rubans (tu étais d'accord).

Supposons le résultat vrai pour et on coupe le ième ruban entre et avec par définition sinon on ne peut pas découper.

Cas 1) Obtenir un seul ruban
Si on coupe de sorte que ou . On obtient un seul nouveau ruban de taille et on aura autrement dit , on ne perd qu'une seule quille et par récurrence on peut conclure.

Si on coupe de sorte que ou . On obtient un seul nouveau ruban de taille et on aura , on perd deux quilles et par récurrence on peut conclure.

Cas 2) Obtenir deux rubans
Si on coupe au milieu tel que . On obtient deux nouveaux rubans de taille et . Donc le nombre de quilles correspondantes devient .

Cas 2.1) longueur non entière
Lorsque ni ni ne sont des entiers mais que est un entier alors


Lorsque ni ni ni ne sont des entiers alors

Dans tous les cas, on ne perd qu'une seule quille et par récurrence on peut conclure.

Cas 2.2) longueur entière
Lorsque est un entier mais n'est pas un entier on peut en déduire que n'est pas un entier et alors

Lorsque n'est pas un entier mais est un entier on peut en déduire que n'est pas un entier et alors


Lorsque est un entier et est un entier on peut en déduire que est un entier et alors

Dans tous les cas on perd deux quilles et par récurrence on peut conclure.

Désolé du pavé, j'ai fait au mieux, ce n'est vraiment pas ma tasse de thé ce genre de rédaction...