Un juego de otra dimensión: Subconjuntos para llevar

El siguiente juego es un juego inventado por David Gale. Aún no se conoce si existe una estrategia ganadora para todos los casos, aunque sí se ha propuesto una conjetura que puede intuirse válida. Te recomiendo leer la entrada hasta el final, ya que aunque nada más empezar a leer pueda parecer un juego sobre matemáticas más, al final de la entrada verás su originalidad.

El juego está basado en la teoría de conjuntos. Un conjunto básicamente es una serie de elementos. Por ejemplo, el conjunto de los números pares sería: {2, 4, 6, …}. El conjunto de los números primos menores que 6 sería: {1, 2, 3, 5}. También podría existir el conjunto vacío, que no tendría ningún elemento. Podríamos poner infinitos ejemplos.

Asimismo, un subconjunto de un conjunto sería cualquier posible combinación de elementos que se pueden extraer de ese conjunto. Es decir, un conjunto A es un subconjunto de otro conjunto B si todos los elementos de A se encuentran en B. Tranquilo, que es muy sencillo.

Por ejemplo, el conjunto {1, 3}, el conjunto {5}, o el conjunto {1, 2, 5} serían subconjuntos del conjunto {1, 2, 3, 5}.

Veamos con otro ejemplo cuáles serían todos los posibles subconjuntos de un conjunto.

Tomemos el conjunto {1, 2, 3}. Todos sus posibles subconjuntos serían:

{1}, {2}, {3},  {1, 2}, {1, 3}, {2, 3}  y  {1, 2, 3}

Es decir, tendrá 7 subconjuntos. Pero el último subconjunto, el que contiene a todos los elementos del conjunto, no será válido para el juego, por lo que en adelante no lo tendremos en cuenta.

El nombre del juego, propuesto por David Gale, se llama “subconjuntos para llevar”. Y se juega de la siguiente manera.

En primer lugar, tomamos el conjunto finito de los números naturales, desde 1 hasta n. Sería el siguiente: {1, 2, …, n}. Jugarán dos jugadores, y consistirá en lo siguiente. Por turnos, cada jugador tomará un subconjunto de ese conjunto, con la condición de que, ningún subconjunto de los ya elegidos anteriormente, puede ser un subconjunto del nuevo subconjunto elegido. Es decir, para entendernos, los elementos de un mismo subconjunto ya elegido no pueden encontrarse en el subconjunto a elegir. El último jugador que acabe de eliminar subconjuntos gana.

¿Qué? ¿Cómo?

Que no cunda el pánico. Veámoslo con un ejemplo, que sigue siendo muy sencillo.

Tomemos el conjunto {1, 2, 3}. Tenía 6 posibles subconjuntos que podíamos elegir, y que habíamos descrito anteriormente, eran los siguientes:

{1}, {2}, {3}, {1, 2}, {1, 3} y {2, 3}

Imaginemos que el primer jugador elige el subconjunto {1}.

Es decir, ya no se podrá elegir ninguno de los subconjuntos que contengan los elementos del subconjunto elegido. Como en este caso, nuestro subconjunto sólo tiene el número 1, entonces ya no podremos elegir los subconjuntos {1, 2} y {1, 3}. Los tacharemos:

{1}, {2}, {3}, {1, 2}{1, 3}, {2, 3}

A continuación, el segundo jugador elige el subconjunto {2, 3}. En este caso este subconjunto no es subconjunto de ningún otro, por tanto sólo se eliminaría de la lista este.

{1}, {2}, {3}, {1, 2}{1, 3}, {2, 3}

Por último, el primer jugador deberá de nuevo elegir uno de los ahora dos conjuntos restantes, y el segundo jugador elegirá el que queda, ganando por tanto el juego.

Hemos realizado el juego para n = 3, con el que el conjunto inicial era {1, 2, 3}, y que, como vemos, resulta muy sencillo. Ahora bien, el juego se complica cuando n es un valor más alto.

¿Qué tiene este juego de original?

Pero antes de seguir, ¿qué tiene este juego de particular para resultar tan curioso? La gracia del juego es que no sólo es un juego relacionado con la teoría de conjuntos, si no que, curiosamente, este juego también puede representarse geométricamente (es decir, está a su vez relacionado con la topología, la rama de las matemáticas que estudia las propiedades de los cuerpos geométricos que permanecen inalterados ante diversos cambios).

Veámoslo:

Por ejemplo, el subconjunto, {1, 2} haría referencia a un segmento, en el que los vértices serían {1} y {2} y la arista sería {1, 2}.

El subconjunto {1, 2, 3}, haría referencia a un triángulo, en el que los subconjuntos {1}, {2} y {3} harían referencia a cada uno de sus vértices, los subconjuntos {1, 2}, {2, 3} y {3, 1} a cada una de sus aristas, y el subconjunto {1, 2, 3} a la cara, área, o interior del triángulo.

Asimismo, el subconjunto {1, 2, 3, 4} haría referencia a un tetraedro, en el que los subconjuntos {1}, {2}, {3} y {4}, harían referencia a cada uno de sus 4 vértices, los 6 subconjuntos formados por dos elementos, es decir, {1, 2}, {2, 3} y {3, 1}, {1, 4}, {2, 4} y {3, 4} harían referencia a cada una de sus 6 aristas, los subconjuntos {1, 2, 3}, {2, 3, 4}, {3, 4, 1} y {1, 4, 2} harían referencia a cada una de las 4 caras o triángulos del tetraedro y el subconjunto {1, 2, 3, 4} al volumen o interior del tetraedro.

(Recordemos que este último subconjunto, que contenía a todos los elementos del conjunto no era válido para ser elegido en el juego).

Por tanto, una partida, vista geométricamente para n = 4, es decir, para el conjunto {1, 2, 3, 4}, podría ser la siguiente (puedes hacer click en la imagen para ampliarla):

Como ves, siempre se eliminan los subconjuntos de mayor dimensión que contienen al subconjunto elegido.

Asimismo, puedes observar que también se podría jugar con su grafo asociado (observa en la imagen que el grafo sería el tetraedro visto desde arriba), teniendo en cuenta que la cara {2, 3, 4} sería una cara más:

El juego es equivalente. Si se eligiera, por ejemplo, el vértice o subconjunto {1}, habría que quitar las aristas {1, 2} y {1, 3} y las caras {1, 2, 3} y {1, 2, 4} que contienen ese vértice.

Para el caso de n = 4, en el que la figura resultante es un tetraedro, podríamos jugar incluso con figuras construidas con juegos de construcción, tipo geomag:

Como vemos en la imagen, este tetraedro estaría construido con todos los posibles subconjuntos del conjunto {1, 2, 3, 4}. Observa que cada pieza es un subconjunto. ¿Lo ves? Tendría los 4 vértices forman los 4 subconjuntos de 1 elemento, las 6 aristas forman los 6 subconjuntos de 2 elementos, y los 4 triángulos interiores forman los 4 subconjuntos de 3 elementos, por lo que, cada vez que se elige un subconjunto, podríamos ir quitando las correspondientes piezas (es decir, los correspondientes subconjuntos) que ya no podrían ser elegidos.

En este caso para n = 4, ¿Sabrías encontrar una estrategia para ganar? Un buen ejercicio a la hora de jugar con chavales de edades de cursos de ESO o Bachillerato a este juego podría ser plantearles si lograrían encontrar una estrategia ganadora para este juego en el caso en que n = 4. Piénsalo tú también antes de seguir.

Veamos.

Como en casi cualquier problema complejo, basta dividir el problema en otros problemas más sencillos que podamos fácilmente resolver, por lo que empecemos por los casos más básicos. Para las partidas en las que n tiene un valor bajo, es sencillo encontrar una estrategia ganadora para el segundo jugador.

Empecemos por la partida más básica:

Estrategia ganadora para n = 2

Tendríamos 2 subconjuntos disponibles: {1} y {2}. Al haber únicamente esos dos subconjuntos, ganaría el segundo jugador eligiendo el subconjunto contrario al primero.

Estrategia ganadora para n = 3

Tendríamos 6 subconjuntos disponibles: {1}, {2}, {3}, {1, 2}, {2, 3} y {3, 1}.

Si el primer jugador elige un subconjunto con un elemento (un vértice), eliminaría tres subconjuntos de esa lista (el vértice y las dos aristas que lo contienen). ¿Logras ver qué subconjunto debería elegir por tanto el segundo jugador para ganar? Para ganar, el segundo jugador podría elegir por tanto la arista restante y quedarían tan sólo dos subconjuntos (los dos vértices restantes), por lo que al igual que en el caso anterior para n=  2, el segundo jugador ganaría de nuevo.

Si el primer jugador inicialmente eligiera un subconjunto con dos elementos (una arista), solo se eliminaría de la lista dicho subconjunto. ¿Qué subconjunto debería elegir por tanto ahora el segundo jugador para ganar? Debería elegir el vértice que no estaba contenido en la arista elegida, eliminando así de la lista tres subconjuntos y quedando de nuevo tan sólo dos subconjuntos (los dos vértices restantes), por lo que al igual que en el caso anterior para n=2, el segundo jugador ganaría de nuevo.

Es decir, hasta ahora podríamos resumir la estrategia ganadora para el segundo jugador en elegir siempre el subconjunto complementario al elegido por el primero. Este subconjunto complementario estaría formado por todos los elementos que no se encontraban en el conjunto elegido.

Por ejemplo, si el primer jugador elige el subconjunto {1} el segundo elegiría el {2, 3}. O al contrario, si el primero eligiera el {1, 3}, el segundo jugador elegiría el {2}. Cuando queden dos subconjuntos, el complementario de uno será el contrario y viceversa.

Estrategia ganadora para n = 4

Ahora bien, para n = 4 la cosa se complica. El segundo jugador sigue contando con una estrategia ganadora, pero ahora esta estrategia no se basará siempre en elegir el subconjunto complementario, ya que podremos llegar a una situación en la que no se pueda elegir un subconjunto complementario.

En este caso, el subconjunto complementario de {1} sería {2, 3, 4}. El complementario de {2, 3} sería {1, 4}. Y cuando quedaran 3 elementos, el complementario se definiría al igual que en el caso anterior para el que n = 3.

En este caso, una vez resueltos los casos para los que n = 2 y n = 3, podríamos encontrar una estrategia ganadora para el segundo jugador buscando todos los casos posibles de jugadas, ,y llegando hasta uno de estos dos casos, que ya hemos resuelto. El juego podría comenzar de 3 formas distintas. El primer jugador podría elegir un subconjunto de 1 elemento (un vértice), uno de 2 elementos (una arista), o uno de 3 elementos (el interior de un triángulo). El segundo jugador, como hemos visto debería coger el subconjunto complementario. A partir de ahí, deberíamos valorar todas las posibles elecciones del primer jugador en cada caso, y cómo se desarrolla el juego, para lograr saber qué elección deberemos tomar en cada momento para ganar. Puedes intentar hallar estos casos y obtener la estrategia ganadora.

Pero a medida que el valor de n aumenta, este proceso es cada vez más complicado y su coste aumenta cada vez en mayor proporción, por lo que lo ideal sería poder encontrar una estrategia ganadora para todos los casos de n.

David Gale conjuntura que para todo valor de n, una buena estrategia en la primera ronda siempre es elegir el conjunto complementario al del rival. A partir de ahí puede darse que no exista un conjunto complementario en alguna ronda, por lo que esta estrategia no puede mantenerse.

¿Cómo se representaría el juego para n = 5? ¿Cuál sería su estrategia ganadora?

Hemos visto cómo se representaría el juego para valores de n <= 4. Ahora bien, ¿para n = 5 cómo podríamos representar el juego?

Si jugamos mediante la primera forma que describíamos en la entrada, es decir, escribiendo los subconjuntos resultantes y tachando los subconjuntos que ya no se pueden elegir a media que se van sucediendo las rondas, el juego es exactamente igual. Ahora bien, para representarlo gráficamente, la tarea se complica, porque en esta ocasión la figura que deberíamos representar es un pentacóron.

¿Cómo? ¿Qué es un pentacóron?

El triángulo es una forma geométrica en dimensión 2.

El tetraedro sería la forma geométrica análoga al triángulo en dimensión 3.

El pentacóron sería por tanto la forma geométrica análoga al triángulo y al tetraedro en dimensión 4.

Al igual que el tetraedro está formado por 4 triángulos, el pentacóron estaría formado por 4 tetraedros, y esta figura sería posible en un mundo con 4 dimensiones.

Puedes observar que en el triángulo y en el tetraedro cada vértice o punto está unidos mediante aristas con el resto de vértices. No hay dos vértices que no estén unidos. Por tanto, de igual forma podríamos representar el pentacóron, y el juego sigue siendo exactamente el mismo:

Si escribimos todos los subconjuntos posibles de este conjunto {1, 2, 3, 4, 5} obtendríamos 31 subconjuntos posibles. Los 5 de un elemento corresponderían a los 5 vértices, y los 10 conjuntos de 2 elementos corresponderían a las 10 aristas. Asimismo, hay 10 posibles subconjuntos de 3 elementos que corresponderían con las 10 caras de esta figura (¿Logras verlas todas en el dibujo?). Y por último, los 4 posibles conjuntos de 4 elementos forman los 4 tetraedros (Puedes observar que efectivamente, si eliges 4 aristas cualquiera, y eliminas el resto de la imagen, se forma un tetraedro).

Hay que estar atentos de que estos 4 subconjuntos que forman los tetraedros, que pueden pasar desapercibidos, también pueden, y finalmente deberán, ser eliminados.

Asimismo, al igual que el caso anterior, podríamos hallar una estrategia ganadora para el segundo jugador, valorando todos los posibles casos y partidas que podría tener el juego.

¿Cómo se representaría el juego para n >= 6?

Para n = 6, la figura correspondiente sería la figura análoga al triángulo, al tetraedro y al pentacóron, pero ahora en 5 dimensiones. Podríamos, al igual que hicimos para el caso anterior, construirla mediante su grafo, aunque jugar ahora geométricamente sería más complicado.

¿Cómo podríamos construirla? Como el conjunto que utilizaremos para el juego en este caso será el conjunto {1, 2, 3, 4, 5, 6}, y queremos obtener todos sus posibles subconjuntos, si representamos esta figura con 6 vértices, y unimos, al igual que en el caso anterior, todos los vértices entre sí, obtendríamos la representación de dicha figura. En ella estarán todos los subconjuntos posibles que se forman con el conjunto {1, 2, 3, 4, 5, 6}.

Por ejemplo, toda posible combinación de 3 vértices formará un triángulo. Toda posible combinación de 4 vértices formará un tetraedro. Y ahora, toda posible combinación de 5 vértices formará un pentacóron, la figura que dibujamos para el caso en el que n = 5.

Eso sí, a la hora de eliminar subconjuntos, los subconjuntos de 4 elementos y 5 elementos, que podrían pasar desapercibidos en la figura obtenida (correspondientes a tetraedros y pentacórones) también pueden, y finalmente deberán, ser eliminados.

El mismo proceso podríamos seguir para construir cualquier figura con > 6.

 

En definitiva, espero que estos últimos casos de representaciones en dimensiones mayores que 3 no hayan evitado que se logre entender el concepto del juego, que aun para valores de n bajos sigue siendo muy interesante.

Es un juego, desde luego MUY original, para el que, como hemos comentado más arriba, se ha conjeturado que el segundo jugador tiene siempre una estrategia ganadora para cualquier valor de n, pero aún está lejos de ser demostrada.

Si tienes alguna duda puedes dejarla en los comentarios.

 


Referencias:
Cómo cortar un pastel, Ian Stewart
Subconjuntos para llevar, Premios UAM ESO

 

Opt In Image
¡Suscríbete!
¿Quieres suscribirte gratis y recibir nuevas entradas y más? ¡¡Gracias!!

 

 

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *