La caída de las lámparas
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.)
Respuestas pendientes
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!).
Circuitos hamiltonianos
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:
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…
Números de Stirling de segunda especie
Contar la cantidad de formas en que pueden distribuirse elementos en
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
posibles formas. Si ignoramos el “etiquetado” de las cajas, claramente esto nos deja
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
al número de distintas formas en las que podemos distribuir elementos en
cajas sin dejar ninguna vacía y sin distinguir entre cajas (o sea el número de distintas particiones de
en
subconjuntos). Entonces podemos dividir las formas de efectuar esta distribución en dos clases: las que ponen al elemento
solo en una caja y las que no lo hacen.
Una vez situado el elemento en una caja, las distribuciones serán equivalentes a
elementos en
cajas. Por lo tanto, habrá
formas de efectuar la distribución dejando solo al elemento .
Por otro lado, si el elemento no se encuentra solo, el problema es equivalente a distribuir
elementos en
cajas sin dejar ninguna vacía y luego insertar el elemento
en alguna de ellas (distinguibles por tener distintos subconjuntos de los elementos). En consecuencia habrá
formas de efectuar la distribución sin dejar al elemento solo en una caja.
En conjunto eso nos deja la relación de recurrencia
para estas cantidades, denominadas números de Stirling de segunda especie.
Una historia interesante
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.
Un problema de sumas
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, vi y vj (i != j), tales que vi + vj = s.
Es simple hacerlo en tiempo cuadrático O(n2) 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…
Un problema de termos – Solución
[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 a la cantidad de calor perdida en el primer caso (10% de agua remanente) y
a la cantidad de calor perdida en el segundo caso (90% de agua remanente). Si llamamos
y
a las temperaturas finales correspondientes,
a la masa total de agua y
a su calor específico, tendremos:
y
.
Simplificando:
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 y
.
Si llamamos al flujo de pérdida de calor del termo (dependiente por hipótesis solo de la temperatura), tendremos:
y
.
Si escribimos las ecuaciones diferenciales de las temperaturas,
y
,
podemos observar que solo difieren en una constante multiplicativa. Si definimos , podemos ver que
.
Como obedece la misma ecuación diferencial que
y además cumplen con las mismas condiciones iniciales, podemos concluir que son idénticas. En consecuencia,
.
Como ambas funciones son monótonamente decrecientes y como para todo
positivo, sabemos que
.
Ahora, de acuerdo con las suposiciones anteriormente realizadas, eso implica que
y, en consiguiente,
.
Finalmente, eso nos lleva a la conclusión supuesta en base a los resultados obtenidos bajo la condición :
.
Un problema de termos
[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”…
)
Tesis defendida!
El jueves pasado hice la defensa de la tesis, por la que había comenzado este blog hace ya más de dos años. Pueden bajarla desde la página del repositorio de tesis de grado de la Facultad.
A continuación algunas fotos después de la defensa:



