Spin Foam

La caída de las lámparas

Noviembre 2, 2009 at 4:46 pm (informática, matemática, misc)

We want to figure out how strong our new super-strong light bulbs
are. We know that they will be break when dropped from the top floor
of this building (the 101st). We want to know the exact minimum floor
from which a fall will cause the light bulb to break. You’ll be given
two light bulbs for this task and we want you to do it with the
minimum number of trials.

(Extraído del blog de Louis Brandy.)

Permalink Dejar un comentario

Respuestas pendientes

Noviembre 1, 2009 at 8:19 pm (informática, matemática)

Un problema de sumas

El problema pedía encontrar un algoritmo subcuadrático para determinar si dos elementos en un vector de enteros con una suma dada. Si confiamos en el caracter O(1) de las tablas hash podemos obtener un algoritmo lineal aun más breve que el cuadrático mostrado anteriormente (y sin recurrir al code golfing ):

def sum1_n(s, v):
    d = {}
    for x in v:
        if s-x in d:
            return True
        d[x] = True
    return False

Si no confiamos en eso, puede hacerse en tiempo O(n log n) ordenando la secuencia y reemplazando las búsquedas en la tabla por búsquedas binarias (como sugirió Fer) o directamente escanear el vector ordenado con dos punteros desde los extremos (no es difícil determinar las reglas de avance).

Ahora pueden probar su suerte buscando algoritmos subcuadráticos para resolver 3SUM; es solo un poquito más difícil…

Circuitos hamiltonianos

Este otro problema pedía determinar si era posible encontrar circuitos hamiltonianos en grillas cuadradas con una cantidad impar de vértices. Para ver que esto no es posible, dividamos a los vértices de la grilla en dos clases de acuerdo al siguiente esquema:

División de los nodos del grafo en dos clases, indicadas por el color utilizado para representarlos.

Si recorremos un circuito en el grafo no es difícil convencernos de que en cada paso cambiaremos de clase de vértice. Ahora, en un circuito hamiltoniano la cantidad de pasos será impar, dándonos para el último vértice una clase distinta que para el primero. Como esto es incompatible con el hecho de que se trata de un circuito, es imposible encontrar un circuito hamiltoniano en grillas con una cantidad impar de vértices (no solo cuadradas!).

Permalink Dejar un comentario

Circuitos hamiltonianos

Octubre 8, 2009 at 5:54 pm (matemática, misc)

Un circuito hamiltoniano es un recorrido cerrado de un grafo que pasa por todos sus vértices una única vez. Si nos limitamos a grafos en forma de grillas cuadradas, podemos encontrar fácilmente un circuito en las grillas con una cantidad par de vértices siguiendo este esquema:

Circuito hamiltoniano en una grilla de 8x8 vértices.

Puede encontrarse un circuito de esta misma naturaleza en una grilla cuadrada con una cantidad impar de vértices? Cambia esto si se permiten grillas rectangulares?

La respuesta a este problema (y al anterior de sumas) en el próximo post…

Permalink Dejar un comentario

Números de Stirling de segunda especie

Octubre 1, 2009 at 4:46 pm (matemática)

Contar la cantidad de formas en que pueden distribuirse $n$ elementos en $k$ cajas es bastante simple, una vez que descubrimos el truco de pensarlo como asignarle un número de caja a cada elemento. Claramente esto nos da $k^n$ posibles formas. Si ignoramos el “etiquetado” de las cajas, claramente esto nos deja $k^n/k!$ formas.

Este problema se hace más difícil si agregamos la restricción de que ninguna caja puede permanecer vacía y, de hecho, recuerdo haber esquivado resolver este problema en más de una ocasión (y no soy el único ). Pero en Wikipedia encontré una solución elegante y, tal vez, lo suficientemente memorable para que la recuerde en caso de encontrarme nuevamente con este problema…

Denominemos

$\left\{\begin{matrix} n \\ k \end{matrix}\right\}$

al número de distintas formas en las que podemos distribuir $n$ elementos en $k$ cajas sin dejar ninguna vacía y sin distinguir entre cajas (o sea el número de distintas particiones de $\{1,2,...,n\}$ en $k$ subconjuntos). Entonces podemos dividir las formas de efectuar esta distribución en dos clases: las que ponen al elemento $n$ solo en una caja y las que no lo hacen.

Una vez situado el elemento $n$ en una caja, las distribuciones serán equivalentes a $n-1$ elementos en $k-1$ cajas. Por lo tanto, habrá

$\left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\}$

formas de efectuar la distribución dejando solo al elemento $n$ .

Por otro lado, si el elemento $n$ no se encuentra solo, el problema es equivalente a distribuir $n-1$ elementos en $k$ cajas sin dejar ninguna vacía y luego insertar el elemento $n$ en alguna de ellas (distinguibles por tener distintos subconjuntos de los elementos). En consecuencia habrá

$k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}$

formas de efectuar la distribución sin dejar al elemento $n$ solo en una caja.

En conjunto eso nos deja la relación de recurrencia

$\left\{\begin{matrix} n \\ k \end{matrix}\right\} = \left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\} + k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}$

para estas cantidades, denominadas números de Stirling de segunda especie.

Permalink Dejar un comentario

Una historia interesante

Septiembre 25, 2009 at 11:59 am (historia, ww2)

Via Steve Hsu, encontré una interesante entrevista a Daniel Kahneman. Me resultó particularmente interesante el siguiente fragmento (en aquel entonces vivía en una parte de Francia ocupada por los alemanes luego de 1940):

It must have been the fall of ‘41, when there was a curfew for Jews. We were also supposed to be wearing a yellow star, and there was a curfew which I think was 6:00 PM. I was in first or second grade and I’d gone to play with a friend and I was going home and I missed the curfew, I was late. And so, I turned my sweater inside out and walked home, and as I was coming close I remember the street was deserted and there was this German soldier walking towards me. He was wearing the black uniform and I knew that was not good. That was the uniform of the SS. We were walking towards each other and as we were coming close he sort of beckoned me, and of course I went there, and he picked me up and hugged me. I remember being terrified that he would see the Star of David inside my sweater. Then he put me down and took out his wallet and showed me a picture of a boy and gave me some money. That’s a formative memory because of what it meant about the complexity of things. I remember being very fascinated at the time by this and by stories of Hitler liking flowers and kissing babies. The complexity of evil was much on my mind as a seven- or eight-year-old.

Permalink Dejar un comentario

Un problema de sumas

Septiembre 16, 2009 at 4:12 pm (informática)

Sea v un vector formado por n enteros y sea s un número entero. El problema consiste en determinar de la forma más eficiente posible si existen dos elementos en v, v_i y v_j (i != j), tales que v_i + v_j = s.

Es simple hacerlo en tiempo cuadrático O(n²) mediante el algoritmo “de fuerza bruta”:

def sum1_nsq(s, v):
    for i in xrange(len(v)):
        for j in xrange(len(v)):
            if j >= i:
                break
            if v[i] + v[j] == s:
                return True
    return False

pero lo interesante es ver si puede mejorarse este tiempo…

Permalink 2 comentarios

P vs NP

Septiembre 9, 2009 at 4:30 pm (Uncategorized)

Por Erik Demaine en el MIT:

Permalink Dejar un comentario

Un problema de termos – Solución

Septiembre 7, 2009 at 5:28 pm (física, misc)

[Continuación de Un problema de termos]

Una suposición implícita al resolver esta clase de problemas es que el estado del agua en el interior del termo puede describirse solo mediante su cantidad y su temperatura. Esto implica un estado de cuasi-equilibrio, lo que es razonable si se tiene en cuenta que el termo forma una barrera térmica a la interacción con el medio.

Evaluemos primero entonces el caso en que el tiempo transcurrido tiende a infinito (en lugar de las cinco horas especificadas en el problema). La temperatura del agua en el termo tenderá a la temperatura ambiente en ambos casos, por lo que es lógico que la temperatura final será menor en el segundo caso respecto al primero (en el segundo caso se mezclará un 90% de agua a temperatura ambiente con un 10% de agua a 80 °C, mientras que en el primero se mezclará un 90% de agua a 80 °C con un 10% de agua a temperatura ambiente).

Para evaluar el caso general podemos hacer algunas simplificaciones “evidentes” a primera vista:

La capacidad calorífica del agua es constante.
El trabajo efectuado sobre el agua es despreciable.
La capacidad calorífica del aire contenido en el termo es despreciable.
La pérdida de calor a través de las paredes del termo crece monótonamente cuando la temperatura del agua sube.
El termo pierde calor mientras la temperatura del contenido sea mayor a la externa.

Una simplificación menos evidente es suponer que la velocidad de pérdida de calor no depende de la cantidad de agua contenida. Pero es razonable si tenemos en cuenta que la pérdida de calor depende solo de la temperatura de la pared interior del termo y que el interior del termo puede considerarse en equilibrio térmico con dicha pared.

Llamemos $q_1$ a la cantidad de calor perdida en el primer caso (10% de agua remanente) y $q_2$ a la cantidad de calor perdida en el segundo caso (90% de agua remanente). Si llamamos $T_{1f}$ y $T_{2f}$ a las temperaturas finales correspondientes, $M$ a la masa total de agua y $C_e$ a su calor específico, tendremos:

$T_{1f} = 0.1 \left( 80 - \frac{q_1}{0.1 M \cdot C_e} \right) + 0.9 \cdot 80$ y

$T_{2f} = 0.9 \left( 80 - \frac{q_2}{0.9 M \cdot C_e} \right) + 0.1 \cdot 80$ .

Simplificando:

$T_{1f} = 0.1 \cdot 80 - 0.1 \frac{q_1}{0.1 M \cdot C_e} + 0.9 \cdot 80$

$T_{1f} = 80 - 0.1 \frac{q_1}{0.1 M \cdot C_e}$

$T_{1f} = 80 - \frac{q_1}{M \cdot C_e}$

$T_{2f} = 0.9 \cdot 80 - 0.1 \frac{q_2}{0.9 M \cdot C_e} + 0.1 \cdot 80$

$T_{2f} = 80 - 0.9 \frac{q_2}{0.9 M \cdot C_e}$

$T_{2f} = 80 - \frac{q_2}{M \cdot C_e}$

Podemos ver que cual de las temperaturas sea mayor dependerá exclusivamente de cuanto calor se haya perdido y no de la fracción de agua remanente en el termo, excepto a través del efecto de esta fracción en las pérdidas de calor. El problema queda reducido entonces a determinar cual es la relación entre los valores de $q_1$ y $q_2$ .

Si llamamos $\dot{q}(T)$ al flujo de pérdida de calor del termo (dependiente por hipótesis solo de la temperatura), tendremos:

$q_1 = \int_0^{5\,hs} dt\,\dot{q}(T_1(t))$ y

$q_2 = \int_0^{5\,hs} dt\,\dot{q}(T_2(t))$ .

Si escribimos las ecuaciones diferenciales de las temperaturas,

$\dot{T_1}(t) = -\left(\frac{1}{0.1 M \cdot C_e}\right) \dot{q}(T_1(t))$ y

$\dot{T_2}(t) = -\left(\frac{1}{0.9 M \cdot C_e}\right) \dot{q}(T_2(t))$ ,

podemos observar que solo difieren en una constante multiplicativa. Si definimos $T_3(t) = T_2(9t)$ , podemos ver que

$\dot{T_3}(t) = \dot{T_2}(9t) \cdot 9 = -\left(\frac{9}{0.9 M \cdot C_e}\right) \dot{q}(T_2(9t)) = -\left(\frac{1}{0.1 M \cdot C_e}\right) \dot{q}(T_3(t))$ .

Como $T_3$ obedece la misma ecuación diferencial que $T_1$ y además cumplen con las mismas condiciones iniciales, podemos concluir que son idénticas. En consecuencia,

$T_1(t) = T_2(9t)$ .

Como ambas funciones son monótonamente decrecientes y como $9t > t$ para todo $t$ positivo, sabemos que

$T_1(t) < T_2(t)$ .

Ahora, de acuerdo con las suposiciones anteriormente realizadas, eso implica que

$\dot{q}(T_1(t)) < \dot{q}(T_2(t))$

y, en consiguiente,

$q_1 < q_2$ .

Finalmente, eso nos lleva a la conclusión supuesta en base a los resultados obtenidos bajo la condición $t \rightarrow \infty$ :

$T_{1f} > T_{2f}$ .

Permalink Dejar un comentario

Un problema de termos

Agosto 27, 2009 at 6:29 pm (física, misc)

[Este es un problema inspirado por experiencias reales... ]

Partiendo de un termo lleno con agua a 80 °C, consideremos los dos escenarios siguientes:

Se consume el 90% del contenido del termo, se deja el termo por 5 horas y luego se completa al 100% con agua a 80 °C.
Se consume solo el 10% del contenido del termo, se deja el termo por las mismas 5 horas y luego se completa al 100% nuevamente con agua a 80 °C.

En cual de lo casos la temperatura final del agua será mayor? Qué suposiciones deben realizarse para llegar a esta conclusión? (Solo las difíciles de justificar, no cosas como “la temperatura de la habitación debe ser menor a 80 °C”… )

Permalink Dejar un comentario