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!
Anuncios

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.

Envolvente

La envolvente a una familia de curvas es una curva que es tangente a todas ellas.

Ejemplo de envolvente

En la figura, la familia de curvas son líneas rectas azules, uniendo los puntos (a,0) con (0,10-a). La curva roja es tangente a todas ellas de forma simultánea (aunque a cada una en un punto distinto).

¿Cual es la ecuación de la curva roja?  (con prueba)

Snakes (parte I)

Snake, snake, snake, snake, snake, snake, snake, snake, snake, …

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:

  1. Determinar el número de serpientes con 10 segmentos.
  2. 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.

Mucha suerte con las serpientes.

Ah, y ¡feliz día π!

El problema de Catalan

El problema de Catalan consiste en determinar el número de formas Cn en que se puede calcular el producto de n factores ordenados, realizando las operaciones por parejas.

Por ejemplo, si n=4, el producto abcd puede calcularse de las siguientes cinco formas:

  • [(a\cdot b)\cdot c]\cdot d,
  • [a\cdot(b\cdot c)]\cdot d,
  • (a\cdot b)\cdot(c\cdot d),
  • a\cdot [b\cdot(c\cdot d)],
  • a\cdot[(b\cdot c)\cdot d].

Hay un bonito artículo en Wikipedia explicando cómo obtener una relación recursiva para calcular estos números:

C_n=\sum_{k=1}^{n-1} C_k C_{n-k}.

Que, como todos ya sabemos, es la recurrencia que genera los números de Catalan.

Ahora, es común definir los números de Catalan como el número de formas de recorrer una cuadrícula de n×n partiendo de la coordenada (0,0) hasta la (n,n) de manera que los movimientos permitidos sean a la derecha y hacia arriba y no se permite cruzar la diagonal. Por ejemplo

Media_httpuploadwikim_arnkk

(Imagen de Wikimedia Commons)

son las C4=14 formas de recorrer la cuadrícula de 4×4.

El problema planteado aquí es: establece una correspondencia entre las formas de poner paréntesis a n factores y las formas de recorrer la cuadrícula de n×n siguiendo las reglas mencionadas.

Bitácora del capitán: Sábado 26, 2:08 AM

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.

Mapeo logístico II

 

Tumblr_la6pe7qpu61qcc3y1o1_500

 

Continuando con la temática del mapeo logístico…

Mapeo logístico y conjunto de Mandelbrot

 

Tumblr_la625toxco1qcc3y1o1_1280

 

El mapeo logístico escondido en el conjunto de Mandelbrot.

OH MAI GOD.

Esto sí me ha hecho quedarme sin palabras, jamás de los jamases lo hubiera sospechado

Tarea sobre funciones generadoras

Del curso de matemáticas discretas.

Recuerden que esta tarea no es para entregar, es de práctica para el examen.

  1. Resuelve las recurrencias:
    1. a_n=5a_{n-1} + 2 para n\ge 1, con a_0=0.
    2. a_n = c a_{n-1} +b para n\ge 1, con a_0=0 y c,b constantes.
    3. a_{n+2} = 2 a_{n+1}- a_n para n\ge 0 y a_0=0, a_1=1.
  2. Para cada una de las siguientes sucesiones, encuentra de forma explícita la función generadora ordinaria y la función generadora exponencial.
    1. a_n=n.
    2. a_n=n^2.
    3. a_n=3^n.
    4. a_n = 5\cdot 4^n - 7\cdot 2^n.
  3. Si A(x) es la función generadora de la sucesión a_0, a_1,a_2, a_3, \ldots, ¿cual es la función generadora ordinaria de las sucesiones b_n?
    1. b_n = a_n + c.
    2. b_n= n a_n.
    3. 0,0,0,a_0,a_1,a_2,a_3,a_4,\ldots.
    4. a_0, 0,a_1,0,a_2,0,a_3,0,a_4,\ldots.
    5. a_5,a_6,a_7,a_8,a_9, \ldots.
    6. a_0, a_2, a_4, a_6, a_8,\ldots.
  4. Si F(x) es la función generadora exponencial de la sucesión a_0, a_1, a_2, a_3,\ldots, ¿cuales son las funciones generadoras exponenciales de las sucesiones en el inciso anterior?
  5. Si A(x) es la función generadora ordinaria \sum_{n\ge 0} a_n x^n. ¿Cual es la función generadora ordinaria de la sucesión
    a_0, a_0+a_1, a_0+a_1+a_2, a_0+a_1+a_2+a_3,\ldots?
  6. Demuestra que si p_{par}(n) es el número de formas de particiones de n donde todas las partes son pares entonces
    \sum_{n\ge 0} p_{par} (n) = \prod_{k\ge 0} \frac{1}{1-x}
    Por ejemplo, para n=10 las particiones con partes pares son  [10], [8,2], [6,4],[6,2,2], [4,4,2],[4,2,2,2],[2,2,2,2,2,] y por tanto p_{par}(10)=7.
  7. ¿Cual es el coeficiente de x^n en el desarrollo de \frac{1}{(1-x^2)^2} ?
  8. Usa el método de funciones generadoras para hallar una fórmula para:
    1. la suma de  los primeros n números consecutivos.
    2. la suma de los cuadrados de los primeros n números consecutivos.
      Sugerencia: Considera el problema 5.
  9. ¿Cual es la función generadora de la sucesión  1,  1/2, 1/3, 1/4, … ?
  10. ¿Cual es la función generadora de la sucesión h_n donde
    h_n = 1 + \frac{1}{2} + \frac{1}{3} +\frac{1}{4} + \cdots + \frac{1}{n}
    para n\ge 1 ?

Tarea Olímpica: Viernes 16 de julio

  • Una araña tiene 8 calcetines y 8 zapatos, numerados para cada una de sus patas. ¿En cuantos órdenes distintos puede ponerse los calcetines y los zapatos si no puede ponerse el zapato correspondiente una pierna sin antes ponerse el calcetín de la misma?
  • Un cajón tiene 100 calcetines rojos, 80 verdes, 60 azules y 40 negros. Si saca calcetines de uno en uno sin mirar, ¿cuantos tiene que sacar para asegurarse de tener 10 pares? (cada par está formado por dos calcetines de un mismo color, cualquiera que sea éste).
  • ¿De cuantas formas puedes escoger 5 elementos del conjunto {1,2,3,…,18} de forma que cualquiera dos de los escogidos tengan una diferencia de al menos 2?
  • Demuestra que si n es impar,  entonces la lista
    \binom{n}{1},\binom{n}{2},\binom{n}{3},\ldots,\binom{n}{\frac{n-1}{2}}
    contiene una cantidad impar de términos impares.
  • Prueba que si escoges 16 enteros distintos del conjunto {1,2,3,…100}, existen cuatro de ellos a, b, c, d tales que a+b=c+d.  Determina si esta cota es la mínima posible.
  • Manuel ha escogido 4 números del conjunto {1,2,3,4,5,6,7}. Si Manuel le dice a Dulce el producto de los 4 números, esta información no es suficiente para que Dulce pueda saber qué números son. ¿Cuanto vale el producto de los 4 números?
  • Sea k un número par. Demuestra que no es posible encontrar números positivos a_1, a_2,\ldots,a_k impares tales que 1=\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_k}.
  • Si n es un entero positivo, demuestra que 3^{2^n}+1 es par pero no divisible por 4.

Los primeros 5 problemas aparecen en el libro 102 Combinatorial Problems from the Training of the USA IMO Team, los demás en 104 Number Theory Problems, ambos de Titu Andreescu