El juego de disparar 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 .
Definición
Que el finito gráfico G ser conectado y loopless , con vértices V = {1, 2,. . . , n }. 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 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 tiene al menos tantas fichas como su grado : s ( w ) ≥ deg ( w ). El vértice w es despedido , moviendo un chip de w a lo largo de cada borde incidente a un vértice vecina, produciendo una nueva configuración definido 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 procede con los siguientes resultados.
- Si el número de fichas es menor que el número de aristas, el juego siempre es finito, alcanzando un estado estable.
- Si cada vértice tiene menos fichas que su grado, el juego es finito.
- Si el número de fichas es al menos el número de aristas, el juego puede ser infinito, sin llegar nunca a un estado estable, para una configuración inicial elegida apropiadamente.
- Si el número de fichas es más del doble del número de aristas menos el número de vértices, el juego siempre es infinito.
Juegos de dólar
Algunos juegos de disparar fichas, conocidos como juegos de dólares , interpretan las fichas como dólares y los vértices como prestamistas y prestatarios de dinero. En la literatura destacan dos variantes del juego del dólar:
Variante de Baker y Norine
En este juego de dólar, valores enteros negativos (que representan la deuda) se asignan a algunos de los vértices del grafo finito G . Se dice que un juego se puede ganar si existe un estado en el que todos los vértices se pueden convertir en positivos. [1] Se puede utilizar un análogo de la teoría gráfica del teorema de Riemann-Roch para caracterizar si un juego se puede ganar o no. [1] [2]
Variante de Biggs
En una forma variante de disparar fichas estrechamente relacionada con el modelo de la pila de arena , también conocido como el 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, el banco no puede disparar, solo recolecta fichas. Eventualmente, q acumulará tantos chips que ningún otro vértice puede disparar: solo en tal estado, el vértice q puede disparar chips a los vértices vecinos para "reactivar la economía".
El conjunto de estados que son estables (es decir, para los cuales solo q puede disparar) y recurrentes para este juego puede recibir la estructura de un grupo abeliano que es isomorfo al producto directo dey el grupo de la pila de arena (también denominado grupo jacobiano o grupo crítico). El orden de este último es el número de árbol del gráfico. [3] [4]
Ver también
Referencias
- ^ a b Baker, Matthew; Norine, Serguei (2007). "Teoría de Riemann-Roch y Abel-Jacobi en un gráfico finito" . Avances en Matemáticas . 215 (2): 766–788. doi : 10.1016 / j.aim.2007.04.012 .
- ^ Lamboglia, Sara; Ulirsch, Martin. "Del juego del dólar al teorema de Riemann-Roch" . Instantáneas de las matemáticas modernas de Oberwolfach . doi : 10.14760 / SNAP-2021-001-EN .
- ^ Biggs, Norman L. (25 de junio de 1997). "Chip-Firing y el grupo crítico de un gráfico" (PDF) . Revista de combinatoria algebraica : 25–45 . Consultado el 10 de mayo de 2014 .
- ^ wikidot. "Referencias chip-fire" . Consultado el 19 de mayo de 2014 .
- A. Björner, L. Lovász, PW Shor: Juegos de disparar fichas en gráficos. Archivo del European Journal of Combinatorics, Volumen 12 Número 4, julio de 1991, páginas 283–291 doi : 10.1016 / S0195-6698 (13) 80111-4 PDF
- A. Björner, L. Lovász: Juegos de disparar chips en gráficos dirigidos. Journal of Algebraic Combinatorics, diciembre de 1992, volumen 1, número 4, págs. 305–328 doi : 10.1023 / A: 1022467132614
enlaces externos
- Curso MIT 18.312: Combinatoria algebraica
- Weisz Ágoston: Un koronglövő játék. Szakdolgozat, ELTE TTK Bsc, 2014 [ enlace muerto permanente ]
- Encuesta de encendido de chips en el grupo de investigación Egerváry
- Juegos basados en la activación de chips (2010)
- The Dollar Game : video de Numberphile sobre la variante del juego de dólares de Baker y Norine.
- https://thedollargame.io/ : un juego basado en la variante del juego del dólar de Baker y Norine.