Bonjour,

Marrant comme jeu : ce soir je mets la table avec 3 verres et 4 assiettes .

J'ai l'impression que la règle générale est :

 Cliquez pour afficher

Il faut une position initiale (X,Y) telle que X ou Y est "forçable à 0" en un nombre pair de coups et que Y ou X est un autre nombre

 Cliquez pour afficher

Notons
P={2,4,6,8,9,10}  (les forçables à 0 en un nombre pair de coups)
I={1,3,5,7} (les autres)

Alors les situations initiales de types (X,Y) (ou de manière équivalente (Y,X)) avec XP et YI semblent être des positions gagnantes pour A.
Et évidemment, les situations initiales de la forme (0,X) avec X quelconque sont aussi gagnantes pour A.

Re,

En fait je me suis loupé avec mon 9, c'est plus simple que ça :

 Cliquez pour afficher

Il faut (X,Y) avec l'un pair et l'autre impair

 Cliquez pour afficher

Supposons X pair et Y impair.
* A joue pour que X devienne impair (toujours possible en enlevant 1 par exemple).
* B ne peut conserver X,Y impairs tous les deux donc après le coup de B, X ou Y sera impair et l'autre restera pair. Donc A se retrouve dans la même situation (pair,impair) mais avec des nombres plus faibles.
* En descendant, on finit avec (2,1), et c'est à A de jouer, qui fait (1,1)

Il me semble plus simple de parler de positions gagnantes ou perdantes plutôt que de parité du nombre de coup sinon on perd vite le fil . En effet une position (P , I) gagne et (I , I) perd , il reste donc à regarder le cas (P , P) .

Imod

Bonjour Imod

la lecture de cet enoncé me place en interrogation .......

Alain commence et retire 4 assiettes , Bernard prend 3 assiettes et le ou l'inverse et c' est fini puisque chacun peut  retirer uniquement des verres ou des assiettes d'une quantité divisant leur nombre sur la table ...  ou alors un truc m'echappe

Bonjour Flight

Je ne comprends pas ta question

On est dans un jeu qui peut s'apparenter à un jeu de Nim ( on retire à tour de rôle des allumettes dans différents tas ) . L'objectif est d'être le dernier à agir .

Dans l'exemple que j'ai proposé A gagne toujours s'il joue correctement ( contrairement au développement donné ) . Après il y a d'autres situations à envisager

Imod

Les positions (X;X) sont perdantes. En effet, après chaque mouvement, l'adversaire peut faire le même mouvement. Et on se retrouve dans une position (Y;Y) avec Y < X. Au final, on se retrouve à la position (0;0) qui est perdante car il n'y a plus de mouvement possible.

Il apparait que pour une position (X;Y) différente de (0;0). Soit G le plus grand diviseur commun à X et Y. La position (X;Y) est perdante si et seulement si X/G est impair et Y/G est impair.

Je n'ai pas de démonstration pour l'instant

 Cliquez pour afficher

import math


def main(n=65):
    print('  ' + ''.join(f'{y:2}' for y in range(n)))
    win = {}
    for x in range(n):
        for y in range(n):
            win[(x, y)] = (
                    any(not win[(x - x_, y)] and (x % x_ == 0) for x_ in range(1, x + 1))
                    or
                    any(not win[(x, y - y_)] and (y % y_ == 0) for y_ in range(1, y + 1))
            )
        print(f'{x:2}' + ''.join('  ' if win[(x, y)] else ' x' for y in range(n)))

    for x in range(n):
        for y in range(n):
            if x == 0 and y == 0:
                continue
            g = math.gcd(x, y)
            assert (not win[(x, y)]) == (x // g % 2 == 1 and y // g % 2 == 1)


if __name__ == '__main__':
    main()

Ok, j'ai une démonstration mais pour une réponse différente Mais normalement équivalente

Soit une position avec , impair et impair.

Cette position est perdante si et seulement si .

En effet, si , alors la position est de la forme .

Et si , alors la position ne peut pas être de la forme .
En effet, si , alors est impair  et on a la forme . Si , alors on a la forme avec .

En descendant, on fini par arriver à et le suivant arrive à . Et c'est le cas qui arrive à un 0, le cas ayant toujours un .

En espérant ne pas avoir fait trop de fautes ou typos. On est déjà aux petites heures du matin

Oui c'est ça LittleFox

Le plus difficile est de trouver la caractérisation des positions gagnantes avec le rôle prépondérant des facteurs 2 . Je n'ai pas encore regardé ce qui se passait si on ajoutait des cuillères à la vaisselle présente sur la table

Imod

Ajouter d'autres couverts est relativement simple en utilisant le théorème de Sprague-Grundy.

Avec n couverts on a n jeux équivalents.
Pour chaque couvert, on montre que le nombre de grundy de la classe de est simplement .

On montre comme précédemment, qu'on peut accéder à tout les n < m mais pas à n = m. On peut aussi accéder à la position 0. m est donc la plus petite position non atteignable.

Le nombre de grundy d'un ensemble de n couvert est le ou-exclusif du nombre de grundy de la position de chaque couvert.

Une position est gagnante si ce nombre de grundy est différent de 0.

Oui , ce que tu dis me parle . Je m'étais intéressé il y a un moment à des problèmes qui pouvaient se ramener à ce type de sommes :



Chacun à tour de rôle coupe un segment et tout ce qui n'est plus rattaché au sol disparait . On perd quand on ne peut plus jouer . Dans le cas général ce problème est extrêmement complexe  

Imod

Ça peut devenir compliqué en effet. Mais principalement parce que la représentation est compliquée.

Quelques simplifications:

- On peut considérer que le sol est un seul point.
- Le nombre de Grundy d'un cycle de longueur pair est 0 et 1 si impair.
- Le nombre de Grundy d'une chaine de segment est le nombre de segments.
- Le nombre de Grundy de graphes liés uniquement par le sol est le ou-exculsif de leur nombres de Grundy.
- Le nombre de Grundy d'un graphe séparable par un point unique est la somme du nombre de Grundy de la partie attachée au sol et de celui de la partie obtenue en remplaçant le point par le sol.

Avec ces simples règles on peut déterminer que:
- Le nombre de Grundy du second graphe est 1 (un cycle impair)
- Celui du 4eme graphe est 1 (une chaine de longueur 1)
- Celui du 3eme graphe est 2 (5 chaines de longueur 1 sur une chaine de longueur 1 sur un cycle pair = 1+1+0 = 2)

Il reste le premier graphe, il est plus compliqué à cause des segments partagés par plusieurs cycles qui empêchent de les séparer. Mais on doit pouvoir trouver une règle

D'accord , la ligne de sol peut se réduire à un point mais après l'imbrication des jeux devient vite inextricable à la main . Il y a sans doute moyen de résoudre ça récursivement via un robot mais c'est très certainement coton

Imod