Un jeu basé sur les graphes — Les-mathematiques.net The most powerful custom community solution in the world

Un jeu basé sur les graphes

J'ai récemment vu quelqu'un recommander ce petit jeu qui se déroule sur des graphes : https://thedollargame.io/

Les règles sont simples, chaque sommet du graphe est étiqueté par un nombre entier, et le but du jeu est que toutes les étiquettes soient positives ou nulles. Pour cela, on peut cliquer sur un sommet, dont l'étiquette va diminuer du nombre de voisins de ce sommet, et chacun de ces voisins verra son étiquette augmenter de $1$. Ça devient vite assez difficile ;-)

Réponses

  • Fascinant !

    PS : Sais pas faire mieux aux 27 et 32.79940
  • Quelqu'un arrive à avoir 3 étoiles au niveau 32 ? Même en m'aidant de sage, qui produit une solution censée être optimale avec 94 clics, ça ne donne que 2 étoiles.
  • Math Coss, pour le 27 moi aussi je n'y suis pas arrivé sans sage, ainsi qu'au 9.

    Edit. Pour le 27 c'est parce que : il faut faire un truc d'un peu contre-intuitif. Regardes ta situation finale, et si c'est la même que la mienne tu devrait en comparant avec les situations précédentes voir que tu as en fait effectué un mouvement inutile.
  • Félicitations pour la programmation !

    Le script que j'ai fait résout le problèmes 9 mais pas le 27, du moins pas en moins de 5 minutes. Il faut dire qu'il est bien naïf : partant de la situation initiale, il clique sur tous les sommets systématiquement et il recommence avec les pondérations obtenues. Le problème, c'est de limiter l'univers des possibles. De façon optimiste, je n'explore pas les situations où la valeur absolue du plus grand poids n'est pas plus grande que dans la situation initiale (ce n'est pas pire qu'au début, quoi). Ça laisse beaucoup de choses à explorer et je ne sais pas si ça suffit...
  • On peut formuler le problème comme de l'optimisation linéaire en nombres entiers. Voici le code sage (nei veut dire neighbors) :
    def search_sol(init_state, nei, maxw=120):
      N = len(init_state)
      p = MixedIntegerLinearProgram()
      v = p.new_variable(integer=True, nonnegative=True)
      p.set_objective(-sum([v[k] for k in range(N)]))
      for k in range(N):
        w = - len(nei[k]) * v[k] + sum([v[n] for n in nei[k]])
        p.add_constraint(w+init_state[k] >= 0)
      p.add_constraint(sum([v[k] for k in range(N)]) <= maxw) # inutile en fait
      print(p.solve())
      for k in range(N):
        print(p.get_values(v[k]))
    

    Pour la solution du 27 :
    search_sol([-4,0,-2,-2,8,-2,3],[[1],[0,2,4,3],[1],[1,4,5,6],[1,3],[3],[3]])
    
    Pour la solution du 32 :
    search_sol([0,3,9,-3,6,3,-1,-5,0,-9],[[1],[0,2],[1,6,5,4,3],[2,4],[2,3],[2,7,9],[2,7],[6,5,8],[7,9],[5,8]])
    

    Pour le 27, on peut simplement explorer toutes les possibilités d'affectation des poids entre $0$ et $10$. Mais pour le 32, il faut aller jusqu'à 17 au moins, et avec 9 nœuds c'est trop lent, il faudrait probablement attendre plusieurs heures voire un jour entier.

    Tu as formulé ça comme l'exploration d'un graphe ?
  • Oui, c'est fascinant et très profond : théorie du potentiel sur les graphes, Riemann-Roch sur les graphes ...etc... J'en ai été assis sur le c.l il y a quelques années. Une manière de s'initier à RR de manière discrète ?
    Quelques pointeurs : http://www.kurims.kyoto-u.ac.jp/EMIS/journals/JACO/Volume9_1/m6g7032786582625.fulltext.pdf https://www.sciencedirect.com/science/article/pii/S0001870807001454

    Il me semble que j'avais commencé par le blog de Matthew Baker https://mattbaker.blog/2013/10/18/riemann-roch-for-graphs-and-applications/
  • Décidément, les programmes linéaires !

    La clé, que je n'avais pas vue (shame!), c'est que les clics commutent. Je me suis posé la question et j'ai décidé que ce serait trop beau et qu'il n'y avait pas de raison. C'est la raison pour laquelle j'ai cherché à explorer le graphe, de sorte à garder une trace de l'ordre des manipulations. (C'est un graphe orienté dont les sommets sont les pondérations possibles et les arêtes sont coloriés par le sommet qu'il faut cliquer pour passer de l'une à l'autre.) Eh bien, ça marche beaucoup moins bien !

    Sinon, un mot clé pointé par un collègue graphiste : déchargement.
  • Bonjour,

    Une idée non aboutie:

    Disons d'un sommet qu'il est bon si
    (son étiquette est strictement comprise entre son nombre de voisins d'étiquette $\geq 0$ et son degré)
    Ou exclusif
    (son étiquette est supérieure ou égale a son degré et il a (au moins) un voisin d'étiquette $< 0$).

    Sauf erreur,quand on clique sur un bon sommet la somme des valeurs absolues des étiquettes diminue.

    Reste à prouver que tant qu'il y a un sommet négatif... il y a un bon sommet!

    Amicalement

    Paul
  • Math Coss, il pointe vers quoi ce mot-clef "déchargement" ?

    depasse : Dans le graphe (1) -- (0) -- (-1) il n'y a pas de bon sommet. Au passage, c'est justement ce qui faisait que je ne trouvais pas la solution du niveau 27 : je cliquais sur un certain "bon sommet", ce qui me faisait en fait perdre un mouvement.

    Peut-on trouver un critère intéressant pour que le problème soit solvable ?
    La matrice de l'application linéaire qui aux nombres de clics sur chaque sommet associe les charges acquises par les sommets est la matrice laplacienne du graphe.
    Le graphe complet $K_4$ avec deux sommets à $1$, un sommet à $-1$ et un sommet à $0$, donne un jeu non solvable.

    Super, les références de Claude Quitté s'intéressent à cette question ! La manière dont le problème est posé dans l'article de blog (dernier lien du message de Claude Quitté) est un peu différente, mais en fait équivalente (pour la solvabilité, pas pour le nombre de mouvements). Pour le voir, on peut se servir du fait que cliquer une fois sur tous les sommets revient à ne rien faire. Pour cliquer "moins une fois" sur un sommet, on peut donc cliquer une fois sur tous les autres sommets.
  • (tu) Champ-Pot-Lion et merci de m'éviter de chercher vainement à démontrer que si il y a sommet négatif, il y a bon sommet.
  • $\def\Im{\text{Im}}$Puisque Champ-Pot-Lion a relancé le truc, je dis deux ou trois choses là-dessus. C'est un peu loin, soyez indulgent(e)s. On dispose d'un graphe connexe $G$ de sommets $V$. Une configuration sur $G$ est une fonction $V \to \Z$ ou encore un habitant de $\Z^V$. Il y a un opérateur symétrique (le Laplacien) $\Delta : \Z^V \to \Z^V$. Il y a 36 manières de le définir. Par exemple, en désignant par $Gv$ les voisins du sommet $v$ :
    $$
    \Delta(f)(v) = \sum_{w \in Gv} (f(v) - f(w)), \qquad v \in V
    $$
    Histoire de le voir, ce Laplacien : j'ai tiré un graphe connexe au hasard à $n = 6$ sommets et fait afficher la matrice d'adjacence et la matrice laplacienne.
    [color=#000000]
    > n := 6 ;
    > G, VG, EG := RandomConnectedGraph(n) ;
    > G ;
    Graph
    Vertex  Neighbours
    
    1       2 3 ;
    2       1 3 4 5 ;
    3       1 2 4 6 ;
    4       2 3 5 ;
    5       2 4 ;
    6       3 ;
    
    > AG := AdjacencyMatrix(G) ;
    > AG ;
    [0 1 1 0 0 0]
    [1 0 1 1 1 0]
    [1 1 0 1 0 1]
    [0 1 1 0 1 0]
    [0 1 0 1 0 0]
    [0 0 1 0 0 0]
    > 
    > Delta0 := LaplacianMatrix(G) ;
    > Delta0 ;
    [ 2 -1 -1  0  0  0]
    [-1  4 -1 -1 -1  0]
    [-1 -1  4 -1  0 -1]
    [ 0 -1 -1  3 -1  0]
    [ 0 -1  0 -1  2  0]
    [ 0  0 -1  0  0  1]
    > {Mineur(Delta0,i,j) : i,j in [1..n]} ;
    { 21 }
    [/color]
    
    La matrice laplacienne est notée Delta0 et est obtenue à partir de la matrice d'adjacence (notée AG) en remplaçant la diagonale (nulle) de AG par la suite des degrés (les lignes/colonnes de la matrice laplacienne sont indexées par les sommets du graphe). On voit que la somme de chaque ligne (ou de chaque colonne, la matrice est symétrique) est nulle. Et donc $\Im\Delta \subset \ker\Sigma$ où $\Sigma$ est la forme linéaire $\Z^V \to \Z$ définie par $\Sigma(f) = \sum_v f(v)$. Pour $\sigma$, on dit aussi le degré.
    En passant : le noyau de $\Delta$ est constitué des fonctions (sur les sommets du graphe) qui sont harmoniques (la valeur au centre est la valeur moyenne des valeurs voisines).

    Il y a un groupe abélien (fini) vachement important : c'est $\ker\Sigma /\Im\Delta$. Son cardinal est le nombre d'arbres recouvrants de $G$. On peut obtenir ce nombre en prenant n'importe quel mineur (convenablement signé) d''ordre $n-1$ de la matrice laplacienne. Ici, le nombre d'arbres recouvrant est 21 (le résultat du calcul des $n^2$ mineurs est l'ensemble réduit au singleton 21).

    Dans le jeu dollar-game, deux configurations sont dites équivalentes si leur différence est dans $\Im \Delta$. C'est cela le truc important. Il va donc falloir étudier $\Z^V /\Im\Delta$. Maintenant, au lieu d'utiliser la terminologie configuration (cela fait trop la personne qui joue au dollar-game), on dit diviseur. Cela fait plus snob mais c'est pareil.

    Je passe les détails (si vous voulez en savoir plus, consulter le site de Matt Baker ou m'envoyer votre numéro de carte bancaire par MP). Il se trouve qu'en fixant un sommet, disons $q$ , il y a une notion de diviseur $q$-réduit. Tout diviseur est équivalent à un et un seul diviseur $q$-réduit. Et il suffit de regarder la tronche du diviseur $q$-réduit pour décider, partant d'une configuration, si on peut l'amener dans le dollar-game sur une configuration $\ge 0$ sur tous les sommets.
    [color=#000000]
    > N := 5 ;
    > SomeConfigurations := [Vector(Q, [Random(-20,20) : i in [1..n]]) : dummy in [1..N]] ;
    > SomeConfigurations ;
    [
        (-13   6   2   6  -6  -6),
        ( -9   5   2  19   4 -12),
        ( -4 -14  -4  12   8 -10),
        (-19   7 -10   0  11   7),
        (  9  -5  -5 -20  -8 -10)
    ]
    > [Degre(c) : c in SomeConfigurations] ;
    [ -11, 9, -12, -4, -39 ]
    [/color]
    
    Ci-dessus, j'ai tiré $N=5$ configurations au pif. Et j'ai fait afficher leurs degrés (somme des composantes). Ce degré est important car il y a une notion de Riemman-Roch dans cette histoire de théorie du potentiel sur les graphes.

    Je vais réduire ces $N=5$ configurations par rapport au dernier sommet (n'importe quel sommet conviendrait).
    [color=#000000]
    > // On va s'appuyer sur le sommet numéro n
    > q := n ;
    > ReducedConfigurations := [ReducedDivisor(Delta0,c,q) : c in SomeConfigurations] ;
    > ReducedConfigurations ;
    [
        (  1   2   0   0   0 -14),
        (1 2 0 0 0 6),
        (  0   1   0   0   1 -14),
        ( 0  0  0  0  0 -4),
        (  0   0   0   0   0 -39)
    ]
    [/color]
    
    Par définition, chaque configuration $q$-réduite est $\ge 0$ en dehors des sommets de $q$. On le voit ici (ce n'est pas la propriété qui caractérise les diviseurs $q$-réduits). Il n'y a plus qu'à interroger le signe de la composante en $q$. Ici la dernière. On voit que la dernière composante est $< 0$ sauf pour la deuxième configuration où cette composante vaut 6. Donc la deuxième configuration, je veux dire diviseur, peut être amené sur un diviseur effectif (ayant toutes ses composantes $\ge 0$, diviseur effectif, pareil, cela sonne bien). Les autres diviseurs, niet.

    Enfin, il y a des diviseurs réduits spéciaux relativement à un sommet (ici le dernier sommet) : ce sont ceux de somme nulle (de degré nul). Il y en a autant que le nombre d'arbres recouvrants), à savoir ici 21.
    [color=#000000]
    > ReducedDivisors(G) ; // relativement au dernier sommet
    [
        (0 0 0 0 0 0),
        ( 0  0  0  0  1 -1),
        ( 0  0  0  1  0 -1),
        ( 0  0  0  1  1 -2),
        ( 0  0  0  2  0 -2),
        ( 0  1  0  0  0 -1),
        ( 0  1  0  0  1 -2),
        ( 0  1  0  1  0 -2),
        ( 0  1  0  1  1 -3),
        ( 0  1  0  2  0 -3),
        ( 0  2  0  0  0 -2),
        ( 0  2  0  0  1 -3),
        ( 0  3  0  0  0 -3),
        ( 1  0  0  0  0 -1),
        ( 1  0  0  0  1 -2),
        ( 1  0  0  1  0 -2),
        ( 1  0  0  1  1 -3),
        ( 1  0  0  2  0 -3),
        ( 1  1  0  0  0 -2),
        ( 1  1  0  0  1 -3),
        ( 1  2  0  0  0 -3)
    ]
    [/color]
    
    Ce que j'en dis : je trouve que la théorie du potentiel et Riemann-Roch sur les graphes, c'est vraiment joli et accessible à tout le monde. Aucune connaissance préalable (enfin presque). Il faut juste déjouer les définitions ...etc... Nous savons tous comment sont faits les articles actuellement. Mais qu'est ce qui m'arrive ? Suggestion : consulter le site de Matt Baker et ensuite les divers papiers. J'ai étudié cela il y a quelques années et j'ai constaté à un moment donné, qu'il y avait eu des généralisations : cf par exemple, Postnikov & Shapiro ``Trees, Parking functions, syzygies, and deformations of Monomial ideals'' in https://arxiv.org/abs/math/0301110. J'ose poser une question : le Postnikov, c'est pas celui des tours de Postnikov ? Boris Shapiro, je vois qu'il est né en 1967 et a travaillé sous la direction de Vladimir Arnold.

    Des volontaires pour faire mumuse avec le papier de Postnikov/Shapiro ?
  • A propos des Postnikov. Aucun rapport. Celui de la topologie algébrique et différentielle se nomme Mikhail (1927-2004) https://fr.wikipedia.org/wiki/Mikhail_Postnikov.
    L'autre : Alexander, advisor Richard Stanley http://www.genealogy.ams.org/id.php?id=18054, Thesis: Enumeration in Algebra and Geometry.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!