Thursday, June 23, 2011

Desigualdades y bolas de colores

Hace unos dias atras, mi profesor de entrenamientos para olimpiadas, Dorval Carias, publico un estatus en Facebook que me hizo sonreir de inmediato y me regreso a mis epocas de entrenos:

$(1+1/x)(1+1/y)(1+1/z) \geq 64 \quad \text{donde } x+y+z=1$

es una expresion bonita con la que se puede jugar un poco si no se tienen herramientas fuertes para demostrarla, y eventualmente es posible obtener una solucion elemental. Usando tecnicas un poco mas sofisticadas, es posible mostrarla utilizando la desigualdad de Jensen (posiblemente la forma mas elegante de mostralo), o bien, sumas simetricas y dominacion de una expresion sobre la otra. Incluso es posible utilizar algun argumento tipo AM-GM (como es usual en desigualdades) o tambien tecnicas como suavizamiento, entre otras. Sin embargo todas estas tecnicas prueban la desigualdad, mas no dan una explicacion del porque tiene esta forma, como diria Erdös, una bonita prueba deberia dar una manera de entender el problema, no solamente dar una demostracion.

A primera vista, el 64 con el cual se compara la expresion es un tanto misterioso, sin embargo luego de analizar por un poco de tiempo la desigualdad se puede observar que $64=4^3$ (algo impresionante la verdad) y es posible in un poco mas alla y notar que $64=(3+1)^3$, lo cual suena un poco mas razonable.

Luego de esta primera aproximacion al problema, es habitual tratar de simplificarlo un poco mas para entender lo que pasa. Resulta ser que el problema equivalente con dos variables es

$(1+1/x)(1+1/y)\geq 9$

con $x+y=1$, el cual no da muchas mas pistas que el problema original en tratar de buscar una razon para la desigualdad.

Si hacer el problema mas facil no funciona ¿porque no hacerlo mas dificil?

La forma general del problema seria

$\prod_{i=1}^n (1+1/x_i)\geq (n+1)^n$

con

$\sum_{i=1}^n x_i=1$

Algunas veces un cambio de notacion simplifica mucho un problema, y si no lo hace, al menos da un poco mas de intuicion sobre como atacarlo. Este puede ser uno de dichos casos. Usemos variables $p_i$ en lugar de $x_i$, entonces al mirar la condicion

$\sum_{i=1}^n p_i=1$

¿que es lo primero que viene a la mente? ¡Probabilidades!

Tal vez alguna interpretacion probabilistica o combinatorica pudiera resultar interesante.

Supongamos que tenemos $n$ cajas con bolas de $n$ colores distintos. Sea $p_i$ la probabilidad de sacar una bola de la caja $i$ luego de vaciar todas las cajas en un contenedor comun.

Teniendo las bolas en las $n$ cajas separadas, enumeremos las bolas en cada caja por separado. Consideremos ademas, una bola extra sin color y averiguemos el numero de formas de elegir $n$ bolas de la siguiente manera:

podemos elegir la $i$-esima bola de la $i$-esima caja o bien, elegir la bola comodín

Un pequeño problema con esta interpretacion es que no tenemos el numero total de bolas, sin embargo la probabilidad $p_i$ puede dar un indicio de esto.

Si la probabilidad de elejir una bola de la caja $i$ es $p_i$, eso significa que aproximadamente 1 de cada $\lfloor 1/p_i \rfloor$ bolas en total son de color $i$. Por lo tanto, para una bola de color $i$ en total existen solo $\lfloor 1/p_i \rfloor$ en total, por lo que podemos suponer que en la caja $i$ hay $\lfloor 1/p_i \rfloor$ bolas. (Notese que al hacer esto, las bolas se vuelven pesadas y no hay una probabilidad uniforme, sin embargo esto no es ningun problema)

Por lo tanto, el numero de formas de elegir las $n$ bolas de la manera descrita anteriormente

$\prod_{i=1}^n (1+\lfloor 1/p_i\rfloor)$

Ahora, definamos una segunda manera de elegir bolas

elegir $n$ bolas de cualquiera de las $n$ cajas o la bola comodín, sin importar la numeración

claramente el numero de formas de hacer esto es

$(n+1)^n$


Por ultimo, al notar que la primera manera de elegir bolas incluye orden y la segunda no, se puede decir que la desigualad se cumple.

Puede ser que esta explicación no sea elegante ni corta ni ingeniosa, sin embargo ayuda a entender un poco mas la naturaleza de la desigualdad, su forma y su relevancia.




Monday, June 20, 2011

Hackers of Nature

Almost two years ago, my friend Antonio Juarez invited me to join him in his adventure of moving from Austin to Pittsburg. It had been so long time since I spent time with him since we were back home, and as usual, the trip was full of wierd things and crazy conversations ranging from philosophy to deeping cookies in various kinds of beverages.



About two weeks ago, I attended a conference about quantazation and I had a really nice talk with one of the participants, and part of it made me remember one of our many interesting conversations with Antonio.


As natural in a quantazation conference, discussion between mathematical and physical points of view arose everywhere, and here is when I remember what I once said to Antonio, that my appreciation of how a physicist views his job can be thought as follows:



Physicsts are like hackers. What he does is grab an already built software that does something (nature), starts playing around with the inputs and then analyzing the outputs. Then with this information, what he does is to make his own programs that emulates the original one, in other words, tries to figure out what was the original code for the original software.



Then the evolution of theories in physics is like upgrading the code, improving bugs, extending the range of the input variable, and sometimes, make it more user friendly. If God built up mathematica, physicists build sage.


No wonder lots of physicists like Linux.


And mathematicians? Probably they are like apple, they don't care about the other programmers, they only do stuff, even if no body is going to use it, but at the end, every body is got an iPhone.