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

Tarea cálculo 3 

No he podido subir los archivos (ya los tengo) porque son grandes y se cancela la subida a la mitad. Sigo intentando…

 

Finalmente ya se pudo:

Es rtnemlaee itnatirre

Reciclado de una entrada vieja que escribí hace mucho.

Sucede muchas veces que la gente escucha algo que le llama la atención y lo repite constantemente. Y lo repite sin detenerse a pensar si en realidad es cierto.Hablo de una noticia vieja (la he visto hace ya más de un año, pero hoy mismo día me la he topado dos veces), que cuando la ví, me llamó mucho la atención. Y básicamente dice algo así.

Cietra unversdiad ineglsa dsecubrio que si al escrbiir las palaabrs, la pirmera y la ulitma lertas etsán en su lgaur , no improta el oerdn de las dmeas, uno peude leer “calramnete”…

Cierta universidad inglesa descurió que si al escribir las palabras, la primera y la última letras están en su lugar no importa el orden de las demás, uno puede leer “claramente” las palabras sin necesidad de mucho esfuerzo, ya que el cerebro procesa por “palabras” en lugar de letra por letra.

Nunca he escuchado que digan cuál es la universidad, ni nadie que me lo cuenta en realidad ha leído tal artículo. Sin embargo, con una demostración similar a la anterior, todo mundo queda convencido.

¿Será? Pues… ¡NO!
La afirmación es incorrecta y tiene su trampa. Cabe aclarar que ninguna de las personas que me mencionan tal hecho lo hace de mala fe, ya que viene acompañada de “eivdnceia”. Así que ellos no están conscientes de la pequeña trampa que a ellos mismos les han jugado.

La afirmación es esta:
Basta que la primera y la última letra estén en posición, sin importar el orden de las demás, para que podamos reconocer “en segiuda” la palarba.
Bueno, si quiero probar que la afrimacóin es falsa, dbereía de dejar de dar eejmpols de que sí funciona.

Y sin más preámbulos…. regresar al título. ¡¡No es tan sencillo de leer!! A pesar de que la primera y la última letra están en su lugar. La pequeña trampa es que en todos los ejemplos que se han dado de muestra, las letras dseordneadas, en realidad no estaban tan desordenadas.

La afirmación sólo es cierta si el grado de desorden de la palabra es pequeño. Uno puede preguntarse cómo es que uno puede medir qué tan desordenada está una palabra, y la respuesta la sugiere el curso básico de teoría de grupos, ya que una palabra desordenada es, a final de cuentas, una permutación de sus letras. Y como toda permutación se puede expresar como producto de transposiciones, se tiene un número mínimo de transposiciones necesarias para obtener esa permutación, etc…

Así que el desorden de las letras “de enmedio” sí importa. Claro que dí muchos ejemplos que sí funcionan, y hasta ahora sólo he dado uno que no, bien podría ser la excepción. Por lo que aquí van otros ejemplos:

  • Cdnauo dtrepseó, el diruasonio taívadoa ebatsa allí
  • ¿Cmoo eacilpxr un mrgalio en un mdnuo ddnoe tdoo tneie enoicacilpxn?
  • Doreitucsin ptnemasorgilee puqroe Aromy sainetsoa que mar y amar no se paidon uazilitr para una rmia
  • Y así vomas atnalede, betos que ramen crtnoa la ctneirroe, itnemetnasecne asodartsarrs hicaa el pdasao
  • Los aonmuls doreidicen caibmar la fhcea de la eugertna
  • Asetige aetns de usrase
  • El ptneicae dtrepseó htneirbmao
  • La eidepolcicna lerbie
  • Nsetoe que en cada lenia, la rlgea se clpmue

Sí, en cada ejemplo la regla se cumple, la primera y la última letra están en posición, mientras que todas las demás están revueltas. Pero en mis ejemplos, los desórdenes no son pequeños (una o dos letras incorrectas), sino que he maximizado el número de inversiones (es decir, el mayor desórden posible) con las letras de enmedio, pero el resultado ya no se puede leer tan fácil como si estuvieran escritas correctamente, como decía la afirmación.

Claro que todos los ejemplos fueron construidos con un método, (que no es difícil de descifrar), y que conociendo el método se pueden leer los ejemplos con relativa facilidad, pero lo importante es que no se pueden leer casi igual de rápido que si estuvieran correctamente.

También hay que tomar en cuenta que en el inglés (el lenguaje original del estudio), la mayoría de las palabras son de una o dos sílabas, mientras que en español, frecuentemente aparecen palabras de 2, 3 o 4 sílabas. Y claro, si hay menos letras, el desorden posible es menor (aunque también hay contraejemplos a la afirmación en inglés, pero esa es otra historia).

Así, la afirmación correcta es:

Si en una palabra, la primera y la última letra se dejan en su posición, y las demás letras se cambian ligeramente de su posición, es posible entender la palabra sin mucho esfuerzo.

Eso ya no es tan impresionante ¿verdad? Y suena un poco tonto armar tanto alboroto por algo que es un tanto evidente. 🙂

Como postdata  ¿sabías que la palabra crédulo no está en el diccionario?:

Gradientes y curvas de nivel con SAGE

Este es el archivo para la práctica en SAGE que se discutirá en clase sobre gradientes y curvas de nivel:    DESCARGA

RSK correspondence in SAGE

SAGE has a function to perform Robinson-Schensted algorith on a permutation. However it lacks the Robinson-Schensted-Knuth generalization that gives the bijection between nonnegative integer matrices and pairs of semistandard Young tableau.

After waiting a long time hoping someone would implement it, I needed it to do some checks related to my thesis, so I took RS code and adapted it. Posting here so it won’t get lost.

from itertools import izip
from bisect import bisect
def RSK(M):
    """ Implementation of the Robinson-Schensted-Knuth algorithm 
        for non negative integer matrices, based on the Robinson-Schensted implementation for Permutations 

    
    """
    # M is the matrix corresponding to the pair of tableau (P,Q)

    # First we create the double-row array
    upperrow = []
    lowerrow = []
    for r in range(M.nrows()):
        fila = M[r]
        for c in range(len(fila)):
            for k in range(M[r][c]):
                upperrow.append(r+1)
                lowerrow.append(c+1)
    p = []       #the "insertion" tableau
    q = []       #the "recording" tableau

    # We proceed to do bumping algorithm on lower row
    # and recording places on upper row
    for a,b in izip(upperrow, lowerrow):
        for r,qr in izip(p,q):
            if r[-1] > b:
                y_pos = bisect(r,b)
                b, r[y_pos] = r[y_pos], b
            else:
                break
        else:
            r=[]; p.append(r)
            qr = []; q.append(qr)
        
        r.append(b)
        qr.append(a)
    return [Tableau(p), Tableau(q)]

Example.

Perform the RSK correspondence on  matrix
\begin{pmatrix} 1&0&2 \\ 0&2&0 \\ 1&1&0 \end{pmatrix}

Me= Matrix( [[1,0,2],[0,2,0],[1,1,0]] )
RSK(Me)

[[[1, 1, 2, 2], [2, 3], [3]], [[1, 1, 1, 3], [2, 2], [3]]]

gives the pair of tableau
P:

1 1 2 2
2 3
3

and
Q:

1 1 1 3
2 2
3

Snakes (parte II)

Bueno, resulta que, el  aparentemente simple e inocente problema de las serpientes en realidad es un problema abierto en el área de combinatoria enumerativa.

Antes de plantear el problema que me interesa ahora, primero tengo que platicar cómo no se resuelve el problema de las serpientes.

Lo más natural al intentar resolver el problema es hacer algunos casos pequeños para darse una idea del comportamiento de la sucesión.

Serpientes, con su codificación

Como se sugirió en la entrada anterior, cada serpiende queda codificada por una sucesión de letras, indicando hacia dónde se hacen los giros.  Tabulando las cantidad de serpientes para cada longitud  tenemos:

1, 2, 4, 6, 10, 16, 26,…

Salvo los dos primeros términos, cada uno es igual a la suma de los dos anteriores, como en los números de Fibonacci. De hecho, salvo el primero todos son el doble de un número de Fibonacci. Vamos a denotar por s(n) el número de serpientes de longitud n y por f_n al n-ésimo número de Fibonacci. Conjeturamos entonces:

s(n)=2 f_n.

Fijándonos en las palabras que codifican cada serpiente, si I es un giro hacia la izquierda y D un giro para la derecha, entonces la lista de serpientes comienza como:

  • n=1. Sólo hay una palabra, vacía.
  • n=2. Hay 2 palabras, indicando los dos posibles giros:  I, D.
  • n=3. Las palabras posibles son II, ID, DI, DD.
  • n=4. Las palabras válidas son IID, IDI, IDD, DII, DID, DDI.  Nótese que III, DDD no son palabras váldias pues hacer 3 giros consecutivos en la misma dirección regresa al punto inicial y por tanto la serpiente se tocaría a sí misma.
  • n=5. Las palabras aquí son IIDI, IIDD, IDII, IDID, IDDI, DIID, DIDI, DIDD, DDII, DDID.

Unos casos más podrían convencernos que las serpientes corresponden a palabras donde no hay 3 símbolos consecutivos iguales.

Ahora, antes de seguir hay que aclarar que la descripción anterior sólo es corecta hasta n=11, porque a partir de entonces hay serpientes no válidas que no tienen 3 símbolos seguidos. Por ejemplo:

  • IDIIDIIDIID no es una serpiente válida, pues termina en el punto inicial y por tanto se corta a sí misma.

IDIIDIIDIID no tiene 3 símbolos iguales consecutivos

Esto quiere decir que la descripción simple que conjeturamos para las serpientes no es la correcta. De hecho, tampoco es cierta la conjetura de que el número de serpientes siempre es el doble de un número de Fibonacci (y precisamente a partir de n=12 falla la conjetura.

¿Cual es entonces la sucesión real de número de serpientes? ¿Porqué los primeros términos de la sucesión están relacionados con los números de Fibonacci?

Para calcular los valores reales de la sucesión usamos la computadora para generar todos los caminos hasta cierta longitud. El siguiente programa, en el lenguaje de programación Ruby genera todas las posibles serpientes y muestra la sucesión asociada.

#! /usr/bin/ruby
# coding: utf-8

def dir(q,p)
	#   dirección de p-->q
	v=[q[0]-p[0],q[1]-p[1]]
	if v == [0,1]
		return :N
	elsif v==[0,-1]
		return :S
	elsif v==[1,0]
		return :E
	elsif v==[-1,0]
		return :W
	end
end

def mueve(x, d)
	if d == :N
		return [x[0], x[1]+1]
	elsif d == :S
		return [x[0], x[1]-1]
	elsif d == :E
		return [x[0]+1,x[1]]
	elsif d == :W
		return [x[0]-1,x[1]]
	end
	return [x[0],x[1]]
end

def gira(d, c)
	#puts "girando #{d}"
	if c == 1  # giro positivo
		if d == :N
			return :W
		elsif d == :W
			return :S
		elsif d == :S
			return :E
		elsif d== :E
			return :N
		end
	elsif c== -1   #giro negativo
		if d == :N
			return :E
		elsif d == :E
			return :S
		elsif d == :S
			return :W
		elsif d == :W
			return :N
		end
	end
end

def recorre(s)    # Esta función "recorre" una cadena y regresa falso si se corta a sí misma
	puntos=[[0,0],[1,0]]
	s.downcase!
	s.each_char{ |c|
		p=puntos[-2]
		q=puntos[-1]
		diractual = dir(q,p)
		if c == "d"
			newdir=gira(diractual, -1)
		elsif c=="i"
			newdir=gira(diractual, 1)
		elsif c=="a"
			newdir = diractual
		end
		a=puntos[-1]
		b=mueve(a,newdir)
		if puntos.include?(b)
			return false
			break
		else
			puntos << b
		end
	}
	return s
end

def main       #Aquí generamos todas las serpientes
levels=[""]
print "1"
0.upto(20){ |n|    #Iteramos sobre todas las longitudes
	past=levels
	new=[]
	past.each{ |s|      # Y para cada una de longitud n-1, intentamos extenderla
		if recorre(s+"i") then new << s+"i" end
		if recorre(s+"d") then new << s+"d" end
		#if recorre(s+"a") then new << s+"a" end   # Activar esta línea para permitir avanzar sin girar
	#puts "level #{n} genera #{new}"
	}
	print ", #{new.length}"     # Finalmente mostramos cuántas hubo en ese nivel
	levels = new
}
end

main

El resultado de correr el programa es

1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 282, 452, 724, 1160, 1842, 2936, 4688, 7480, 11844, 18826, 29956

que difiere de la sucesión de dobles de Fibonacci a partir de la posición 12.

1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422

Podemos consultar datos sobre la segunda sucesión en la base de datos OEIS

SAGE: Práctica 1

Este es el archivo de la primera sesión de práctica con SAGE: Práctica 1 .

Para abrirlo, entra a tu cuenta de SAGE (ya sea en tu computadora o en la versión en línea) y usa el enlace upload.

El enlace upload sirve para añadir el archivo a tu cuenta

Luego indica el archivo que descargaste al inicio

EPIC WIN!!!!

Cualquier duda, la pueden dejar ahí abajo o a mi correo ¿lo apuntaron, verdad?

Parábola origámica

Fractales en Google

Minientrada.

Hoy descubrí que Google tiene un experimento para mostrar fractales mediante JavaScript y HTML5.

http://juliamap.googlelabs.com

Fractales en Google

Polinomios que cuentan

Imagina que queremos contar de cuantas formas se puede contar de cuantas formas se puede obtener 8 al tirar un par de dados. Uno puede realizar el clásico diagrama de coordenadas

Y concluir que hay 5 formas de obtener el 8.  Con el mismo diagrama, podemos encontrar el resultado f(k) para cualquier suma k:

f(2)=1, f(3)=2, f(4)=3, f(5)=4, f(6)=5, f(7)=6, f(8)=5, f(9)=4, f(10)=3, f(11)=2, f(12)=1.

Pero ¿qué pasa si queremos tirar tres dados? ¿cinco dados? ¿20 dados? ¿m dados? Ya no es práctico usar la representación de coordenadas, necesitamos un nuevo modelo.

Consideremos sólo un dado. ¿De cuantas formas podemos obtener el valor k? Pues de 1 forma si k=1,2,3,4,5,6  y 0 de cualquier otra forma.  Vamos a codificar todos los resultados posibles en una única expresión:

a+a^2+a^3+a^4+a^5+a^6

Donde los exponentes representan los valores de los dados y los coeficientes (todos 1) representan el número de formas de obtener esos valores.  Así, por ejemplo,  a^3 = 1a^3 indica que sólo hay 1 forma de obtener a^3.

Ahora, si tenemos dos dados, pues son dos polinomios a considerar:

(a+a^2+a^3+a^4+a^5+a^6)(a+a^2+a^3+a^4+a^5+a^6)

Hacemos la multiplicación y el resultado es…

a^2+2a^3+3a^4+4a^5+5a^6+6a^7+5a^8+4a^9+3a^{10}+2a^{11}+a^{12}.

Los coeficientes son precisamente el número de formas de obtener el exponente al tirar dos dados.  De hecho, el coeficiente de  a^k en el desarrollo de (a+a^2+a^3+a^4+a^5+a^6)^m es el número de formas de obtener el valor k al tirar m dados y con esta información podemos encontrar el valor exacto.

Observamos que a+a^2+a^3+a^4+a^5+a^6 es una serie geométrica, por lo que

a+a^2+a^3 +a^4+a^5 +a^6 = a \left( \frac{1-a^6}{1-a} \right)

y por tanto

(a+a^2+a^3+a^4+a^5+a^6)^m=a^m(1-a^6)^m(1-a)^{-m}

Ejemplo.

¿De cuántas formas se puede obtener 15 al tirar 8 dados?

El resultado es el coeficiente de a^{15} en  a^8 (1-a^6)^8 (1-a)^{-8}. Es decir, es el coeficiente de a^7 en (1-a^6)^8 (1-a)^{-8}.  Usando el teorema del Binomio (primero para exponentes enteros y luego para exponentes negativos) tenemos

(1-a^6)^8 (1-a)^{-8} = \left(\sum_{j=0}^8 {8 \choose j}(-a^6)^j\right)\left(\sum_{j\ge 0}{j+7 \choose 7}(-a)^j\right),

y al desarrollar, los términos que contienen a^7 son:

\binom{8}{0}\cdot \binom{14}{7}(-a)^7 + \binom{8}{1}(-a^6)\cdot \binom{8}{1}(-a),

con lo que concluimos que el número de formas de obtener 15 al tirar 8 dados es

{14\choose 7} - 64 = 3368.

Reflexiones.

Entre las cuentas, puede perder uno de punto de vista la idea central: estamos representando una sucesión de varios valores (formas de tirar un dado) mediante un solo objeto algebraico (un poliomio), y manipulaciones con este objeto nos dan información acerca de la combinatoria del problema.

El método puede modificarse para resolver problemas similares (por ejemplo, si quisiéramos saber de cuántas formas se puede obtener 30 al tirar 3 dados normales y dos dados en forma de icosaedro, intentaríamos encontrar el coeficiente de a^{30} en el desarrollo de

(a+a^2+a^3+a^4+a^5+a^6) ^3 (a+a^2+a^3+\cdots+a^{20})^2

Este es un caso particular del método de funciones generadoras, en el que una serie de potencias representa una cantidad (posiblemente infinita) de valores de una sucesión.

Bibliografía.

  • Aigner, Martin. A Course in Enumeration. Graduate Texts in Mathematics, 238. (2007)
  • Bona, Miklós. Introduction to Enumerative Combinatorics.  McGraw Hill Higher Education. (2007)
  • Camina and Lewis. An Introduction to Enumeration.  Springer Undergraduate Mathematics Series. (2010)