Al analizar algunos juegos relativamente
sencillos, podemos observar que es posible seguir una estrategia que nos
permite ganar si jugamos bien. El propósito de este artículo es modelar estos juegos
mediante la Teoría de Grafos, revisar las estrategias seguidas para ganar y
aplicarlas a otros juegos que puedan ser igualmente modelables. Para ello es
fundamental comprender el concepto de núcleo de un grafo, por lo que será
preciso conocer algunas definiciones básicas de la Teoría de Grafos.
Ideas básicas de la teoría
de grafos
Los conceptos fundamentales de la Teoría de Grafos los podemos
encontrar en multitud de libros y artículos, por ejemplo en (Bollobás, 1998).
Dibujar un grafo para resolver un problema es bastante común, y no
se precisa de conocimientos matemáticos. Un grafo es un dibujo como el de la
figura 1, y consta de vértices y de aristas que unen algunos de estos vértices.
Se pueden modelar mediante grafos multitud de situaciones, como una
red de carreteras que conectan ciudades, una red eléctrica, etc. En algunos
casos es necesario imponer un sentido a las aristas, por ejemplo, si se quiere
representar la red de las calles de una ciudad donde aparecen direcciones
únicas (Ver figura 2). Uno de los más famosos es el de los puentes de
Könisberg. Esta ciudad rusa que se encuentra a orillas del río Pregel, y que en
el siglo XVIII tenía siete puentes, sirvió de pretexto para un famoso problema
con grafos: se trataba de pasar por todos los puentes sin atravesar ninguno de
ellos dos veces.
Definición: Un grafo es un par G = (V, E), donde V es el conjunto de vértices
del grafo, siendo su cardinal |V| = n entero positivo, y E V x V son las
aristas del grafo (e = {x, y} = {y, x} es una arista, por lo que no existe
orientación).
Es importante destacar que en un dígrafo (o en un grafo) es posible que para dos vértices a y b haya
más de un arco (o arista) de la forma (a, b), es decir, es posible que se
repitan los arcos (o aristas). Sin embargo, para nuestro propósito, supondremos
que no se da esta situación.
Observemos el juego para
dos jugadores que se plantea a continuación:
El primer jugador dice un número entero del 1 al 3. El segundo
jugador suma al número dicho por su contrincante 1, 2 ó 3 y dice el resultado.
Entonces, el primer jugador sumará a este resultado 1, 2 ó 3 cantando el nuevo
resultado, y así sucesivamente. Gana el que primero diga 31. A continuación se
muestra el ejemplo de una partida: Basta jugar dos o tres partidas tratando de
analizar el juego para empezar a tener una idea clara de la estrategia que se
ha de seguir para ganar.
Lo que nos proponemos es
buscar un modelo matemático para este juego y ver las características de la
estrategia seguida para vencer, tratando de generalizarla para otros juegos que
puedan modelar de la misma manera. La base matemática de este modelo la
encontraremos en la Investigación Operativa, en particular, en la Teoría de
Grafos. Será fundamental el concepto de núcleo de un grafo, por lo que es
necesario, para formalizar los conceptos, disponer de algunas definiciones
elementales sobre grafos. No obstante puede resultar que en la práctica no sea
necesario representar explícitamente el juego como un grafo dirigido para
obtener una estrategia ganadora, si bien esta representación siempre será
posible.
Análisis de juegos
Sumar 31
El desarrollo y objetivo de este juego se ha explicado ya en la
introducción. Aunque no es necesario, el juego se puede modelar mediante el
grafo dirigido de la figura a continuaciòn. Los vértices son los números
naturales del 1 al 31 y los arcos salen del vértice n hacia los vértices n + 1,
n + 2 y n + 3, si 1 n 28. Del 29 salen arcos a 30 y 31, del 30 sale un único
arco a 31 y de 31 no sale ningún arco.
Es inmediato comprobar que el jugador que consigue decir el 27,
tiene todo a su favor para ganar, por lo que podríamos replantear el juego con
objetivo 27 en lugar de 31. Pero entonces, quien diga 23 será el más que
probable ganador del juego. Razonando de esta manera, vemos que los objetivos
parciales deben ser X = {3, 7, 11, 15, 19, 23, 27, 31}.
Observamos que las posiciones señaladas cumplen:
i)
Si un jugador dice un número
que no pertenece al conjunto X, el otro jugador siempre tiene la posibilidad de
decir uno del conjunto X mencionado. Por tanto es un subconjunto de vértices
absorbente.
ii)
Si un jugador dice un número
del conjunto X, el contrincante obligatoriamente dirá un número que no está en
dicho conjunto. En consecuencia es un subconjunto estable. Como hemos
comentado, un subconjunto de vértices estable y absorbente es el núcleo de un
grafo.
Así, podemos decir que el objetivo debe ser ocupar las posiciones
del núcleo, puesto que nuestro adversario saldrá obligatoriamente de estas posiciones
ganadoras y, a su vez, desde la situación que nos deje el contrincante, siempre
podremos acceder a ellas.
Observación: Sobre este juego se pueden hacer cuantas variaciones se desee. Por
ejemplo se puede jugar a que quien diga 31 pierde. También se puede fijar otro
número como objetivo y decidir cuánto se puede sumar en cada turno. Siempre
resulta sencillo encontrar el nuevo núcleo.
Como se pudo observar los
grafos y dígrafos se pueden aplicar para resolver cualquier juego, sin embargo
es importante mencionar que también se aplican en la vida cotidiana
