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!

Los problemas matemáticos de El País

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

\begin{pmatrix} p& p^2q^2 & q \\ q^2 & pq & p^2 \\ p^2q & 1 & pq^2 \end{pmatrix}

resultando en la solución

\begin{pmatrix} 3 & 225 & 5 \\    25 & 15 & 9\\    45 & 1 & 75    \end{pmatrix}

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 x del cuadrado mágico por 15^x. 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.