El juego de disparo de fichas es un juego de un jugador en un gráfico que se inventó alrededor de 1983 y desde entonces se ha convertido en una parte importante del estudio de la combinatoria estructural .
Cada vértice tiene el número de "fichas" indicado por su variable de estado. En cada disparo, se selecciona un vértice y uno de sus chips se transfiere a cada vecino (vértice con el que comparte un borde). El número de fichas en cada vértice no puede ser negativo. El juego termina cuando no es posible disparar.
Sea el gráfico finito G conexo y sin bucles , con vértices V = {1, 2,. . . , norte }. Sea deg( v ) el grado de un vértice y e( v,w ) el número de aristas entre los vértices v y w . Una configuración o estado del juego se define asignando a cada vértice un número entero no negativo s ( v ), que representa el número de fichas en este vértice. Un movimiento comienza seleccionando un vértice w que tenga al menos tantas fichas como su grado : s ( w ) ≥ deg( w ). Se dispara el vértice w , moviendo un chip desde w a lo largo de cada borde incidente hasta un vértice vecino, produciendo una nueva configuración definida por:
y para v ≠ w ,
Un estado en el que no es posible realizar más disparos es un estado estable . A partir de una configuración inicial, el juego avanza con los siguientes resultados (en un gráfico conectado).
Para juegos de disparo de chips finitos, los posibles órdenes de los eventos de disparo pueden describirse mediante un antimatroide . De las propiedades generales de los antimatroides se deduce que el número de veces que se activa cada vértice y el eventual estado estable no dependen del orden de los eventos de activación. [1]
Algunos juegos de disparo de fichas, conocidos como juegos de dólares , interpretan las fichas como dólares y los vértices como prestatarios y prestamistas de dinero. En la literatura destacan dos variantes del juego del dólar:
En este juego del dólar, se asignan valores enteros negativos (que representan la deuda) a algunos de los vértices del gráfico finito G. Un juego se considera ganable si existe un estado en el que todos los vértices pueden volverse positivos. [2] Se puede utilizar un análogo teórico de grafos del teorema de Riemann-Roch para caracterizar si un juego se puede ganar o no. [2] [3]
En una forma variante de disparo de fichas estrechamente relacionada con el modelo de pila de arena , también conocido como juego del dólar, un único vértice especial q se designa como el banco , y se le permite endeudarse, tomando un valor entero negativo s ( q ). < 0. Si cualquier otro vértice puede disparar, la banca no puede disparar, sólo recolecta fichas. Con el tiempo, q acumulará tantas fichas que ningún otro vértice puede disparar: sólo en ese estado, el vértice q puede disparar fichas a los vértices vecinos para "impulsar la economía".
Al conjunto de estados que son estables (es decir, para los cuales sólo q puede disparar) y recurrentes para este juego se le puede dar la estructura de un grupo abeliano que es isomorfo al producto directo de y al grupo sandpile (también conocido como grupo jacobiano o grupo crítico). El orden de este último es el número de árbol del gráfico. [4] [5]
