Frases

"Sólo hay 10 tipos de personas,
Las que saben contar en binario
y las que no."
Anónimo

miércoles, 30 de marzo de 2011

Nim

El Nim es un juego para dos personas que es muy interesante. Su origen es muy posiblemente chino.

Se juega, en su versión mas popular, con 12 monedas o piedras o cualquier objeto en 3 filas, una con 3 objetos, otra con 4 y otra con 5.

Las reglas son simples, los jugadores se alternan para quitar uno o más objetos, siempre que sea de la misma fila o hilera horizontal.

Quien toma la última moneda (o la última dependiendo de como quieran jugar) gana.
Después de un tiempo de jugarlo, cualquiera se da cuenta que siempre se gana si se dejan 2 filas o hileras con mas de una moneda y con el mismo número(por ejemplo, 2 hileras con 4 monedas cada una).

Cualquier jugador gana, también, si juega "racionalmente".
Al inicio, se hizo un descubrimiento sorprendente, el juego se puede jugar con cualquier número de hileras y monedas en cada hilera, y siguiendo una simple estrategia que involucra números binarios, uno puede ganar siempre.

Según Charles Leonard Bouton (quien le puso el nombre de Nim y halló la estrategia correcta para ganar), el juego está dividido en 2 clases de jugadas, "seguras" e "inseguras", si la posición después de un movimiento le deja al jugador una victoria garantizada, es considerada una jugada "segura". De lo contrario, es "insegura".

Toda posición "insegura" se puede volver "segura" con el movimiento apropiado, las posiciones "seguras" siempre se vuelven "inseguras" con cualquier movimiento.

Para asegurarse si una posición es "segura", el jugador debe tomar el número de objetos de cada hilera y pasarlos a números binarios, de modo que 3 objetos se convierte en 11. Luego, los suma a los números de las otras hileras. De modo que 3 hileras con 3 objetos cada una sumarían 33 (11 + 11 + 11).

Entonces, una posición es segura cuando la suma da un número donde todas las cifras sean pares o iguales a cero. En el ejemplo anterior, la posición es insegura, para hacerla segura se debe quitar una hilera entera.

De ésta manera, uno siempre podrá ganar este juego mientras nadie más sepa la teoría.