Planar slink

Estuve la semana pasada en el Instituto Fields y asistí a una plática de Jack Edmonds, en la cual  planteó este problemilla. No se me ocurre una traducción aceptable de planar slink, así que no lo traduciré.

Versión 1.

Imagina que tienes una cuadrícula de m×n. Dos jugadores se turnan como sigue: el primer jugador escoge una casilla y cada uno elige sucesivamente una casilla contigua (unida por un lado) desocupada, como en este ejemplo:

Ejemplo de "slink" plano

Pierde el primer jugador que no pueda continuar.

La pregunta natural es: ¿Existe alguna estrategia ganadora para alguno de los dos jugadores? Si es así ¿cuál es?

De acuerdo con Edmonds, este problema está relacionado con apareamientos en gráficas bipartitas.  ¿Cual sería esta relación?

Por ahora lo dejamos aquí, en una entrada posterior hablamos del slink en gráficas planas arbitrarias

Anuncios

  1. Algunas obviedades (en un rectángulo de mxn).

    Si m=1 entonces
    * n par –> el gane es para el jugador B
    * n impar –> el gane es para el jugador A

    Si m=2 entonces…
    el jugador B siempre tiene estrategia ganadora.

    Si m=3, n=3, el primer jugador tiene estrategia ganadora…

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s