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!
No, esto no va del CONACYT ni nada por el estilo o tan doloroso. Sucede que la sociedad matemática de España está cumpliendo 100 años, y parte de la celebración incluye presentar un problema semanal, propuesto por un matemático español, en el periódico El País, y sortean (cada semana) entre los que respondan correctamente un paquete de libros.
Hoy voy a hablar de los primeros 3.
Problema 1.
El primer problema consiste en encontrar un camino que recorra la siguiente gráfica pasando por cada uno de los vértices, sin repetir ninguno y terminando en el punto de partida (esta condición no la hacen explícita pero es necesaria). En otras palabras, encontrar un circuito hamiltoniano para esta gráfica.
Problema 1: Hallar un circuito hamiltoniano para esta gráfica.
Yo traigo aquí el problema directo y al grano, pero en el video lo presentan con más motivación.
Después de intentarlo infructuosamente un rato, se sospecha que no existe dicho recorrido. De hecho, la solución que presentan es la solución típica de problema de olimpiada coloreando vértices, misma que yo encontré también (por cierto, el problema se parece mucho al problema 11 del capítulo 2 del libro de Engel…). Dicho sea de paso, esa coloración que proporcionan quiere decir que la gráfica del problema es una gráfica bipartita.
Hay que aclarar que determinar si existe un circuito hamiltoniano en general es mucho más complicado que determinar si existe un circuito euleriano (camino que pase por todas las aristas exactamente una vez). Para circuitos eulerianos nos basta y sobra el teorema de Euler:
(Euler) Una gráfica simple conexa posee un circuito euleriano si y sólo si no tiene vértices de grado impar.
Como todos los vértices excepto el 1 el 3 y el 8 tienen grado impar, no será posible recorrer la gráfica de forma que cada arista se use exactamente una vez.
Pero para caminos hamiltonianos la cosa se ve negra. No se conoce un teorema equivalente que permita determinar de una vez por todas cuándo una gráfica es hamiltoniana (de hecho, ese problema es NP-Completo).
La mayoría de los teoremas usuales sobre el tema son de la forma
Si esto pasa, entonces habrá un circuito hamiltoniano…
Revisando bibliografía me doy cuenta que casi no hay teoremas sobre gráficas que no sean hamiltonianas. En el libro de Capobianco encuentro uno que dice:
Teorema. Toda gráfica 2-conexa que no es hamiltoniana contiene una subgráfica theta.
Una gráfica theta es aquella donde todos los veŕtices tienen grado 2, excepto un par de ellos que tiene grado 3 (dibújalo y verás ;), y una gráfica es 2-conexa si borrar cualquier vértice no causa que la gráfica se vuelta disconexa.
La gráfica del problema, ciertamente es 2-conexa y la subgráfica formada por los vértices 2,6,8,7,3,9 es una subgráfica theta. Desafortunadamente el converso es falso: que existan subgráficas theta no quiere decir que no sea hamiltoniana. Por lo que no nos sirve para resolver el problema.
He visto varias soluciones en blogs a este problema, pero todos ellos pasan por considerar la gráfica bipartita (esto es, la coloración). Por cierto, combinando el criterio para determinar si una gráfica es bipartita o no, con la solución del problema obtendríamos este mini resultado trivial que generaliza el problema específico:
Si una gráfica simple con una cantidad impar de vértices no tiene ciclos impares, entonces no es hamiltoniana.
Y aprovechando, aquí está el problema de esta entrada.
Problema: Dada una gráfica simple con n vértices, ¿cuál es el número máximo de aristas que puede tener si sabemos que no tiene un ciclo hamiltoniano?
REFERENCIAS
Capobianco and Molluzo, Examples and Counterxamples in Graph Theory. North-Holland, 1978.
Miklós Bona, A Walk Through Combinatorics,2a ed. World Scientific 2006.
Problema 2.
El problema 2 o problema de la hormiga, es un problema mucho más interesante relacionado con probabilidades. Ese problema no lo resolví, pues de este problema me enteré por mi asesor cuando hablábamos de ciertas matrices de probabilidades que me acababa de enseñar (a causa de otro problema completamente distinto). De este problema voy a hablar más adelante en una nueva entrada.
Problema 3.
En este problema se pedía completar un cuadrado mágico multiplicativo. Específicamente, rellenar el cuadrado
* * *
* 15 *
* * *
donde cada asterisco es un número entero positivo distinto, de forma que la multiplicación de los números en cualquier fila, columna o diagonal, sea la misma.
Este ha sido el problema más sencillo, en mi opinión (no tomó más de 5 minutos), y es uno de esos problemas donde resolver algo más general resulta más sencillo que resolver el problema específico.
En realidad trabajar con los números directamente complica la situación puesto que uno se pierde haciendo tantas cuentas. Es más sencillo plantear el problema en términos de la estructura de
los factores primos, donde p=3, q=5 y se desea que en el centro aparezca el número pq.
Así, acomodando factores obtenemos que debe tener una estructura similar a
resultando en la solución
con la ventaja de que hemos encontrado una infinidad de cuadrados mágicos multiplicativos, asignando cualquier par de números distintos a p y q.
Otro camino de solución (aunque no he hallado una solución concreta) es construir cualquier cuadrado mágico (aditivo) donde el centro sea 1, y entonces se reemplaza cada entrada del cuadrado mágico por . Por leyes de los exponentes, esta sería otra solución.
Pero, como digo, no parece haber dichos cuadrados mágicos, de modo que si se prueba que (salvo simetrías) la solución general anterior es única, habríamos probado que no existen cuadrados mágicos aditivos y positivos donde el centro sea igual a 1
Problema 4
Bueno, hoy jueves 7 de abril se publica el cuarto reto matemático… y pueden enviar su solución para concursar por el paquete de libros hasta el lunes.
Agradecería que no pongan ninguna solución antes del martes, pero sí después (para intercambiar comentarios sobre lo que hayamos encontrado).
Actualización (15:34): Ando muy enfermo de gripe y apenas acabo de ver el cuarto problema pero no me duró la alegría pues lo he resuelto en un par de minutos. Claro que el pasar los últimos meses pensando en matroides, en algo me ha ayudado.
Hace unos días, vihart subió un video a youtube en el cual muestra diferentes cosas que hace con unas serpientes para armar.
Ahora, entre todas las cosas que dice, la parte que me interesa aquí está entre 0:45 y 1:30 donde plantea un par de problemas matemáticos relacionados.
El primero de ellos podría describirse así: considera una serpiente formada por 10 segmentos. Cada segmento forma un ángulo de 90º respecto al anterior. ¿Cuantas serpientes (lo que llama slithers) se pueden obtener?
Por ejemplo, si las serpientes están formadas por 4 segmentos, algunas posibles opciones serían las siguientes
Ejemplos de serpientes con 4 segmentos. La flecha indica la posición de la cabeza.
Inmediatamente surge el primer problema. ¿Cuando decir que dos serpientes son iguales? ¿Será cierto que la primera y la tercera serpiente del ejemplo son iguales?
Esa pregunta, al menos, la resolvemos usando un truco clásico, ilustrado en el video: codificar un problema combinatorio mediante palabras. En el video se muestra que cada serpiente corresponde a una serie de letras indicando su estructura (estando en inglés, pone L para izquierda, R para derecha).
Nosotros indicaremos con la I un giro a la izquierda y con D un giro a la derecha. Así, por ejemplo, las 3 serpientes del ejemplo corresponden a las palabras
IID, IDI, DDI.
En la primera, por ejemplo, al recorrer el primer segmento (horizontal) se hace un giro de 90º hacia la izquierda y por tanto se continúa hacia arriba; después del segundo segmento se gira hacia la izquierda nuevamente, quedando el camino apuntando hacia la izquierda; finalmente se hace un giro hacia la derecha y la cabeza termina apuntando hacia arriba. Esos giros los representamos como IID.
La otra regla implícita es que una serpiente no puede en ningún momento tocarse (por ejemplo, una instrucción III haría que la cabeza toque la cola (se forma un cuadrado), lo cual no es válido.
Para dejar completamente en claro el problema, ilustramos las 6 distintas serpientes que se pueden hacer con 4 segmentos:
Las 6 serpientes formadas con 4 segmentos
Observación: nota que la dirección inicial no importa realmente, sólo la forma de la serpiente. Por ello, para simplificar los dibujos, siempre he puesto el primer segmento horizontal y hacia la derecha (piensa en una cuadrícula…). Esto quiere decir que una serpiente la podemos girar, pero no podemos levantarla y reflejarla. Por eso, la segunda serpiente en ambas figuras es la misma: IDI, mientras que, aunque también es una escalera, la quinta DID es diferente, porque no se puede girar para hacerla coincidir con IDI.
El segundo problema es completamente similar, excepto que no se requiere que cada segmento forme un ángulo de 90º con el anterior, sino que se permite que varios segmentos avancen en la misma dirección; a estas variantes les llama snakes (y que aquí llamaremos víboras). Así, una víbora que no es serpiente podría ser:
Una víbora: derecha-avance-izquierda
En este caso tenemos tres posibilidades para movimiento: Derecha, Izquierda y Avanzar.
Problemas.
Entonces, tenemos los dos problemas planteados:
Determinar el número de serpientes con 10 segmentos.
Determinar el número de víboras con 10 segmentos.
Sin embargo, lo que me llamó la atención de este problema, planteado de pasada en apenas un minuto, es que tiene muchas matemáticas detrás, y es posible plantear muchas preguntas interesantes acerca del problema (algunas de las cuales hasta ahora desconozco la respuesta).
El primer paso siguiente es evidente para cualquiera que tenga sensibilidad para las matemáticas:
¿Cual es el número de serpientes con n segmentos?
¿Cual es el número de víboras con n segmentos?
En caso que no sea posible encontrar una fórmula cerrada ¿hay algún tipo de recurrencia? (Bueno, si la hay es muy probable que se puede encontrar también una fórmula cerrada usando el método de funciones generadoras)
Un problema intermedio para la resolución anterior es:
¿Cuales son las condiciones necesarias y suficientes para que una palabra sea una serpiente o una víbora? Es decir, encontrar una forma de decidir si una sucesión como IDDIDIDDDII es una serpiente o no (porque podría cruzarse a sí misma. Y de forma similar, una forma para decidir si una sucesión de letras forma una víbora válida.
Por otro lado, aunque son problemas muy parecidos, podría ser posible que uno problema tenga solución sencilla y el otro no.
Al intentar resolver el problema, es natural empezar a realizar casos pequeños. Sin embargo, después de unos cuantos segmentos el problema se hace tedioso manualmente. Esto crea nuevos problemas de otro estilo:
Elaborar un programa de computadora que liste (y por tanto cuente) todas las serpientes con n segmentos.
Elaborar un programa de computadora que liste (y por tanto cuente) todas las víboras con n segmentos.
Si te tomas unos minutos haciendo dibujos, observarás que puede haber muchísimas direcciones. Por otro lado, que los ángulos sean rectos y que los segmentos todos sean iguales, sugiere que las serpientes en realidad son caminos sobre un plano cartesiano:
Una serpiente es un camino reticular en el plano cartesiano
Inmediatamente se me ocurren dos problemas :
Determinar (sin necesidad de un dibujo) la posición de la cabeza a partir de una palabra. Por ejemplo la palabra IDDIDI termina en (4,-1). ¿Cómo se llega a esa conclusión sin dibujar? Nuevamente, tenemos un problema para serpientes y otro para víboras.
¿Cual es el menor rectángulo que contiene a la serpiente (víbora)? En la figura anterior es el rectángulo de 2×2 que tiene esquinas (0,0), (2,2). (Piensa en la menor caja en la que cabría la serpiente).
En ambos problemas asumimos que el primer movimiento es de (0,0) a (0,1), es decir, una unidad en la dirección x. (No era tan arbitraria la elección hecha arriba al dibujar las serpientes).
Finalmente, podemos obtener una nueva clase de problemas (y para éstas repetir todos los anteriores) si en vez de 90º indicamos que las serpientes tengan que formar un ángulo que sea múltiplo de 60º. Por ejemplo, una hexaserpiente podría ser algo como:
Una hexaserpiente, moviéndose sobre una retícula triangular
Yo creo que un buen problema matemático no sólo es aquél que es interesante resolver en sí mismo y ya, sino que al mismo tiempo permite formular muchas ideas nuevas, plantear nuevas preguntas, generalizaciones, variantes, etc.
Uno de los problemas clásicos y más sencillos sobre diseños es que no puedes cubrir con dominós un tablero de ajedrez al que le has quitado dos esquinas opuestas.
Como TODOS sabemos, esto no es posible porque las casillas que se quitan necesariamente tienen el mismo color, quedando cantidades distintas de cada tipo (y toda cubierta induce una correspondencia suprayectiva entre casillas negras y blancas.)
ENTONCES…
La pregunta que a mi alma esta noche atormenta es: ¿será cierto que retirando dos casillas arbitrarias de color diferente necesariamente queda un tablero que sí es posible cubrir con dominós? Y de no ser así ¿cual es la condición necesaria y suficiente en la posición de las dos casillas que se retiran para que el tablero que queda se pueda cubrir con dominós?
Actualización 27 febrero.
En realidad el problema resultó ser muy sencillo: sí, siempre se puede cubrir y el tablero puede ser de cualquier tamaño siempre y cuando tenga una cantidad par de casillas.
El nuevo problema (mucho más complicado) es encontrar condiciones necesarias y suficientes para que al quitar dos casillas blancas y dos casillas negras, el resto del tablero se pueda cubrir con dominós.
del cuadrado mágico por 
. Por leyes de los exponentes, esta sería otra solución.
Combinatórica 