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

Quinto problema matemático de “El País”

Ayer salió el quinto problema matemático del periódico “El País”, conmemorando los 100 años de la fundación de la Real Sociedad Matemática Española.

En esta ocasión, se trata de un problema de palillos: hay unos palillos en la mesa y con ciertas reglas, se pueden ir retirando palillos de la mesa. El problema es determinar quién de los dos jugadores tiene una estrategia que le asegure el triunfo y cuál es esa estrategia.

En esta semana, son 2 problemas.

 A grandes rasgos: tienes 4 pilas de palillos, respectivamente con 5,5,4,5 palillos cada una. Dos jugadores por turnos toman palillos de la mesa y gana quien tome el último palillo.

  • En el primer problema, cada jugador puede tomar 1,2,3 palillos de la mesa (puede tomar palillos de varias pilas al mismo tiempo).
  • En el segundo problema, cada jugador puede tomar cualquier cantidad de palillos, pero sólo puede tomar palillos de una pila a la vez.
¿Cual de los dos jugadores tiene estrategia ganadora? ¿Cual es?
El primer problema me tomó un par de minutos, el segundo algo más de hora y media. Están realmente interesantes y las soluciones son muy bonitas, y recuerda que si envías tu solución al periódico participas en un sorteo de libros. ¡ánimo!