¿En qué consiste?
El Pick a Perro (de ahora en adelante usaré este, aunque el del cerdo es igual simplemente cambiando los perritos por cerditos) es un juego que se juega con una serie de cartas de un perro que puede variar en una serie de características.
El perro tiene 5 características que pueden variar:
- El color del perro (Negro o Carne)
- Palomitas (Si las tiene o no)
- El tamaño (Pequeño o Grande)
- Los Brazos (Se le ve uno o ambos)
- Las gafas (Lleva o no)
Estas son las únicas 5 características que hay y en cada caso son sólo esas 2 posibilidades las que hay.
Al comienzo del juego se reparte una carta a cada jugador la cual se pone bocabajo. Se colocan también una serie de cartas bocarriba delante de los jugadores.
Todos a la vez levantan su carta y su objetivo es coger una carta que sea exactamente igual que la que acabas de levantar o que sólo difiera en 1 característica. Digamos que la carta que tenías boca arriba era una carta A y has encontrado una B que satisface esto. Una vez has cogido B la colocas encima de A y repites el proceso montando una cadena de perros que difieren a lo sumo en una cosa.
En la imagen tenéis un par de ejemplo de posibles cadenas. Una vez crees (todo esto hay que hacerlo rápido por eso puedes no estar seguro) que no hay ninguna que difiera en a lo sumo 1 característica de tu última carta lo anuncias públicamente y cada jugador cuenta el número de cartas que ha cogido y el que ha parado la ronda se lleva una carta de bonificación. Caso de haber alguna que sí habría poder cogido pierde todas sus cartas.
Ahora se hace otra ronda cogiendo cada jugador una carta que pone bocabajo delante suya, colocando cartas en el centro. Así sucesivamente hasta que se termine toda la baraja y el jugador que más cartas haya recogido es el ganador😃
Unas cuantas preguntas matemáticas que me surgieron mientras jugábamos eran:
¿Cuántas cartas distintas ahí?
¿Sería posible que un mismo jugador consiguiera todas las cartas?
¿Cuál es el mayor número de cartas que podría haber sobre la mesa y que no pudiera coger ninguna?
¿Cuál es el mayor número de cartas que podría haber sobre la mesa y que todas se diferenciaran en 2 características o más, es decir, que no se podrían coger juntas?
La primera es bastante fácil, al haber 5 características distintas y 2 posibilidades en cada caso tendremos 2^5 = 32 posibles cartas. De hecho, si alguna vez jugáis al juego veréis que tiene 96 cartas, es decir 3 de cada tipo.
Vamos con la segunda, partiendo de tu carta, ¿es posible conseguir todas las de la mesa?
Vamos a usar algo que a los matemáticos nos encanta y son los grafos. Vamos a imaginar las cartas sobre la mesa junto a la tuya y dibujamos una línea entre dos cartas si y solo si solo difieren en 1 característica o son la misma.
Es decir, las cartas son los vértices del grafo y tenemos líneas entre aquellas cartas que difieren a lo sumo en 1 característica. Se trata ahora de empezando en nuestra carta y siguiendo las líneas de poder cogerlas todas.
Para entendernos mejor vamos a poner un ejemplo de todo esto, pero vamos a empezar a abstraernos del juego y tratarlo con otra notación.
Vamos a representar las cartas como una quintupla (5 números) que representarán cada una de las características del perro. Ya que en cada característica hay solo 2 posibilidades podemos representar esto con un 0 o 1.
Es decir, una posible carta será el (0,0,0,0,0) o el (0,1,0,1,0) y una vez representadas así dos cartas se pueden coger juntas, a lo cual nos referiremos en adelante a estar conectadas si y solo si solo cambian como mucho en una componente y en tal caso dibujamos una línea entre ellas.
Por ejemplo aquí nuestra carta sería el (0,0,0,0,0) y el resto de cartas son los otros puntos indicados. Hemos dibujado las líneas entre ellos según corresponde. La pregunta ahora es ¿Es posible pasar por todos los puntos una sola vez empezando desde nuestra carta moviéndonos por las líneas?
En nuestro caso es bastante fácil ver que no ya que el cuadrado del principio hará que si queremos pasar por todas las cartas de este no podamos ir al resto de cartas y si salimos del cuadrado ya no podemos volver :(
Lo que hemos hecho tiene un nombre y es ver si este grafo es Hamiltoniano, en este caso no. Un grafo se dice Hamiltoniano si se pueden recorrer todos sus vértices (puntos) sin repetir ninguno de ellos. En nuestro problema necesitamos algo más complicado pues necesitamos además que podamos empezar desde nuestra carta (punto).
Pues estamos jodidos, resulta que encontrar si un grafo es Hamitoniano y describir ese recorrido Hamiltoniano es NP difícil, esto quiere decir que no hay una manera eficiente computacionalmente de hallarlos. De hecho si encuentras una entonces te podrías llevar 10000000€. Más info sobre algunas condiciones necesarias y suficientes para que un grafo sea Hamiltoniano y lo que es un problema NP completo aquí: https://es.wikipedia.org/wiki/Camino_hamiltoniano
Bueno, vamos a ver si hay más suerte con las otras 2 preguntas. Si yo tengo una carta por ejemplo el (0,0,0,0,0) las únicas que puedo coger son o ella misma, o las otras 5 cartas que salen de cambiar una de las componentes (es decir, modificar una de las características).
Luego máximo podemos tener aparte de nuestra carta 32-5-1 = 26 luego 25 cartas aparte de la nuestra sin que podamos coger ninguna (Lo cual es casi imposible pero bueno). Además, como en la baraja hay 3 de cada carta realmente podríamos tener hasta 75 cartas aparte de la nuestra sin que podamos coger ninguna (En ese caso lloras simplemente)
Esto es increíblemente improbable, es mucho más fácil que te toque el euromillones.
Y vamos a la última pregunta; ¿Cuál es el número máximo de cartas distintas que podemos tener sin que haya 2 que difieran en 1 sola cosa?
Vamos a usar algo de teoría de códigos para ver que podemos poner al menos 16 cartas y luego vamos a ver que dicha solución es óptima.
Volvamos a la forma que teníamos antes de expresar las cartas como una quintupla de 1s y 0s.
Para definir lo que es un código necesitamos un alfabeto que en nuestro caso va a ser los 0s y 1s y un conjunto que es el espacio de una cierta dimensión de nuestro alfabeto, en nuestro caso será el de dimensión 5 al tener 5 componentes la forma en que describimos nuestras cartas. A los elementos de este conjunto les llamamos palabras. Nuestro conjunto son todas las posibles quintuplas de 0s e 1s y las palabras cada uno de estos elementos.
Un código no es más que un subconjunto de este conjunto que hemos definido, es decir, algunas de las palabras que están incluidas en nuestro conjunto (un subconjunto de nuestras 32 cartas; es decir, que cojamos algunas de las 32 cartas). Y ahora vamos a definir lo que se conoce como la Distancia de Hamming; pero antes, ¿Qué es una distancia en términos matemáticos?
Todos sabemos que del 1 al 3 hay 2 unidades y la distancia entre dos número reales, pero cuando estamos en otros conjuntos la cosa es más complicada, realmente en mates una distancia es simplemente una función que dados 2 elementos (x,y digamos) de un conjunto les asigna un número (distancia) cumpliendo las siguientes cosas lógicas para elementos cualesquiera x,y e z:
d(x,x) = 0 (Tu estás pegado a ti mismo)
d (x,y) = d(y,x) (No puede ser más distancia la ida que la vuelta)
d(x,z) ha de ser menor o igual que d(x,y) + d(y,z) (Si entre 2 puntos quiero pasar por un tercero no puede ser que ahora tarde menos)
Todo esto es muy lógico, ahora tenemos que pensar una distancia para nuestro conjunto (las cartas, es decir las quintuplas de 0s e 1s) que cumpla esto. Lo más lógico y que nos sirve es que la distancia entre dos quintuplas es el número de componentes distintas.
Para que nos entendamos, el número de cosas del perro que cambian de una carta a otra
Una vez ya tenemos la distancia hay un concepto muy importante en teoría de códigos que es la distancia mínima. Esto nos da una idea de dados los elementos de un código como de separados están los elementos. La distancia mínima es el mínimo de las distancias entre los elementos de nuestro código.
Por ejemplo digamos que nuestro código es el (0,0,1,1,0), (0,1,1,0,0), (0,0,0,0,1), (0,1,0,0,0) en este caso la distancia mínima es 2. Es bueno que la distancia mínima no sea muy baja ya que normalmente lo que queremos con estos elementos del código que se llaman palabras es transmitirlas a otra persona y se pueden producir errores. Si por ejemplo no hay 2 palabras a distancia 1 podremos cometer un error y no se confundirá con otra palabra, simplemente sabremos que lo que nos ha llegado está mal.
¿Y qué tiene que ver esto con nuestro problema? Pues simplemente se trata de ver cuantos elementos tiene el mayor subconjunto de elementos de nuestro conjunto de palabras tal que la distancia mínima sea 2 ya que entonces no tendremos 2 palabras a distancia 1 que son las cartas que están relacionadas al solo diferenciarse en una característica. Es decir, el mayor código dentro de
Vamos para ello a hacer algo análogo a lo que se hace en el DNI para detectar errores; aquí, lo que se hace es que dados los números del DNI la letra se calcula según el resto del número al dividirlo entre 23. Como 23 es primo y se puede razonar si cambias cualquiera de los dígitos de tu DNI cambiará también la letra. Con lo cual no existen 2 DNIs a distancia 1 y la distancia mínima es (al menos) 2; esto sirve para detectar si te has equivocado al escribir tu DNI.
Pues el mismo razonamiento vamos a aplicar aquí; vamos a coger como primeros 4 elementos de la quintupla los que nos de la gana y el quinto va a ser el resto de la suma de estos al dividirlo entre 2, o para que sea más fácil 0 si hay un número par de 1s y 1 si hay un número impar.
Al igual que con el DNI si cambiamos alguno de las componentes nos cambia la última luego tenemos un código con distancia mínima 2 y por tanto no habrá ninguna 2 cartas que difieran en solo 1 características. Hemos conseguido ya que las primeras 4 componentes son libres colocar por tanto tenemos 2^4 = 16 cartas distintas de las que no hay ninguna pareja que difiera en solo 1 característica.
Ya hemos visto que podemos poner 16 cartas de forma que se satisfaga lo que queremos. Pero, ¿Es 16 el máximo? Vamos a ver que sí
Vamos ahora con nuestra notación de quintuplas para las cartas y vamos a colorearlas todas (Ahora estamos trabajando con todas las posibles cartas). A cada quintupla (carta) le vamos a asignar un color de forma que si dos cartas están a distancia 1 (difieren en 1 sola característica) entonces han de tener colores distintos.
Digamos que la carta (0,0,0,0,0) es roja, entonces todas las cartas que están a distancia 1 (las 5 con un 1 en alguna componente y 0 en el resto) han de ser de otro color, digamos verde. Razonando análogamente las quintuplas con 2 1s podrán volver a ser de color rojo (están a distancia 2 del (0,0,0,0,0) luego no hay problema) las de 3 1s pueden ser verdes y así hemos coloreado todas las cartas según el número de 1s usando solo 2 colores (esto se conoce como que el grafo es bipartito).
Si ahora queremos coger un código tal que la distancia mínima sea 2 todos las palabras del código habrán de tener el mismo color pues si no tendríamos 2 que estuvieran a distancia 1. Y hay la misma cantidad de palabras rojas que verdes ya que por cada palabra roja obtenemos una verde simplemente cambiando los 0s por 1s y viceveresa (Como el número de componentes es impar uno tendrá un numero par de 1s y otro un número impar)
Por tanto hay 16 palabras rojas y 16 verdes luego el máximo conjunto que podemos coger es el que indicamos arriba y hemos resuelto nuestro problema😊
El razonamiento que hemos usado sirve para cualquier número impar de componentes, es decir, si tenemos un juego en el que los perros tuvieran k con k impar características el número máximo de cartas que podríamos poner sería 2^(k-1)
En el caso par también se tiene aunque para probarlo tendríamos que hacerlo de otra forma, primero viendo que se puede colorear también con 2 colores que sería igual y luego en este caso no nos valdría lo de cambiar los 1s por 0s y viceversa pero podríamos considerar para cada carta la que resulta de cambiarle la primera componente la cual es de otro color (de hecho, este argumento nos hubiera valido también antes) y tendríamos que hay la misma cantidad de cartas rojas que verdes de nuevo y que el máximo de cartas que podamos colocar sin que ninguna pareja se pueda coger siguiendo las reglas del juego sería 2^(k-1)
¡Muchísimas gracias por haber llegado hasta aquí y espero que os haya gustado!
Honestamente, es la primera vez que hago un artículo de este calibre (que en verdad no es mucho pero bueno) y pido disculpas por los fallos y si hay cosas que no se entiendan (preguntad lo que haga falta en comentarios o a culturamates@gmail.com)
Creo que hemos visto que hay matemáticas en todos lados, incluyendo este juego de mesa. Tristemente esto no nos ayudará a ganar pero bueno, no se puede tener todo en esta vida.
