Un jeu basé sur les graphes

Fascinant !

PS : Sais pas faire mieux aux 27 et 32.

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.

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 ?

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.

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.

$\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 ?