Para practicar la puesta en práctica de las recomendaciones de Douglas Crockford respecto a como programar en JavaScript, me decidí por hacer una demostración en SVG del famoso "Arnold's Cat Map". Este mapeo consiste simplemente en aplicar repetidas veces a las coordenadas de un conjunto de puntos inicial la transformación
(x, y) → (x + y, x + 2y) mod 1 .
El "mod 1" es lo que indica que trabajamos sobre el toroide ℝ2/ℤ2.
Si bien el mapa aplicado a valores reales es caótico y mezcla fuertemente el conjunto de puntos, se observa un fenómeno de recurrencia en las variantes discretas del problema (tal como la implementada). Para este caso particular en el que la imagen es de 32 X 32 pixels, la recurrencia se observa en el paso 24.
Nota de implementación: la imagen fue tomada de Wikipedia y editada y transformada a formato "JSON" utilizando PIL.
Mostrando entradas con la etiqueta matemática. Mostrar todas las entradas
Mostrando entradas con la etiqueta matemática. Mostrar todas las entradas
domingo, 28 de diciembre de 2008
lunes, 22 de diciembre de 2008
Porqué los espejos intercambian derecha e izquierda?
Se cree comúnmente que los espejos "intercambian la derecha y la izquierda". Por ejemplo, la imagen especular de una persona diestra escribirá, aparentemente, con la mano izquierda. Esto nos llevaría a pensar que el espejo trata en forma diferente a las direcciones horizontales que a las direcciones verticales (porque no observamos que el espejo invierta "arriba y abajo").
Pero esto no es lo que en realidad "el espejo hace". La reflexión invierte las posiciones en la dirección perpendicular al espejo. Es por alguna razón psicológica que esto se observa como una rotación de 180° alrededor de un eje vertical compuesta con una inversión de derecha e izquierda.
La razón que se me ocurre para esto es que inconsciente observamos al reflejo como otra persona física; como físicamente las personas pueden rotarse pero no reflejarse, la visualizamos como una versión rotada de nosotros mismos con sus lados derecho e izquierdo intercambiados.
Pero esto no es lo que en realidad "el espejo hace". La reflexión invierte las posiciones en la dirección perpendicular al espejo. Es por alguna razón psicológica que esto se observa como una rotación de 180° alrededor de un eje vertical compuesta con una inversión de derecha e izquierda.
La razón que se me ocurre para esto es que inconsciente observamos al reflejo como otra persona física; como físicamente las personas pueden rotarse pero no reflejarse, la visualizamos como una versión rotada de nosotros mismos con sus lados derecho e izquierdo intercambiados.
Esto plantea la pregunta de porqué visualizamos una reflexión derecha/izquierda pero no la reflexión adelante/atrás. Si bien no se me ocurre una respuesta directa a esta pregunta, probablemente se deba a la cuasi-simetría externa de las personas respecto al intercambio derecha/izquierda.
domingo, 14 de diciembre de 2008
La subasta del dólar
Desde el punto de vista formal se define a un juego como un conjunto de jugadores, cada uno de los cuales dispone de una serie de posibles acciones a tomar, y una forma de determinar cuanta recompensa recibe cada uno de los jugadores en base a las acciones que eligen todos ellos. Este formalismo no solo puede modelizar juegos como el ta-te-ti o el ajedrez, sino que puede aplicarse al análisis de situaciones hipotéticas tales como el conocido "dilema del prisionero".
Uno de los juegos que fueron definidos de este modo es el conocido como la "subasta del dolar" y fue creado por Martin Shubik en 1971 para dar un ejemplo simple del conocido proceso de escalada en los conflictos. El juego es muy simple: se subasta un dólar entre dos jugadores pero ambos deben pagar sus ofertas, lo que altera radicalmente el desarrollo de la subasta.
Supongamos que la oferta mínima y el incremento mínimo de las ofertas se establece en 0.05. Entonces, a primera vista, parece un excelente retorno ofrecer 0.05 a cambio del dólar; pero también lo será para el otro jugador ofrecer 0.10 y así el proceso puede seguir hasta que las ofertas hasta 0.95. Pero la fase más interesante ocurre a partir de este momento...
Supongamos que el jugador "A" hizo la última oferta de 0.95 después de que "B" hubiera ofrecido 0.90. Entonces "B" tiene dos opciones: puede aceptar perder 0.90 o puede ofrecer 1.00 y "salir hecho". El mismo análisis puede hacerlo "A" en caso de realizar "B" su oferta de 1.00: puede perder 0.95 u ofrecer 1.05 y perder 0.05... Esto lleva a una competencia en la que las pérdidas son potencialmente ilimitadas.
Uno podría pensar que este juego carece de relevancia práctica en si y que solo interesa como modelo de otras competencias que suceden en la realidad, pero eso sería incorrecto. Pueden verse más detalles acerca de Swoopo y su modelo de negocios en múltiples sitios. Quién dice que la teoría de juegos no es redituable? :-D
Uno de los juegos que fueron definidos de este modo es el conocido como la "subasta del dolar" y fue creado por Martin Shubik en 1971 para dar un ejemplo simple del conocido proceso de escalada en los conflictos. El juego es muy simple: se subasta un dólar entre dos jugadores pero ambos deben pagar sus ofertas, lo que altera radicalmente el desarrollo de la subasta.
Supongamos que la oferta mínima y el incremento mínimo de las ofertas se establece en 0.05. Entonces, a primera vista, parece un excelente retorno ofrecer 0.05 a cambio del dólar; pero también lo será para el otro jugador ofrecer 0.10 y así el proceso puede seguir hasta que las ofertas hasta 0.95. Pero la fase más interesante ocurre a partir de este momento...
Supongamos que el jugador "A" hizo la última oferta de 0.95 después de que "B" hubiera ofrecido 0.90. Entonces "B" tiene dos opciones: puede aceptar perder 0.90 o puede ofrecer 1.00 y "salir hecho". El mismo análisis puede hacerlo "A" en caso de realizar "B" su oferta de 1.00: puede perder 0.95 u ofrecer 1.05 y perder 0.05... Esto lleva a una competencia en la que las pérdidas son potencialmente ilimitadas.
Uno podría pensar que este juego carece de relevancia práctica en si y que solo interesa como modelo de otras competencias que suceden en la realidad, pero eso sería incorrecto. Pueden verse más detalles acerca de Swoopo y su modelo de negocios en múltiples sitios. Quién dice que la teoría de juegos no es redituable? :-D
miércoles, 3 de diciembre de 2008
Lissajous II
234.435 = 0.234435 ∙ 103
3.14159... = 0.314159... ∙ 101
1024 = 0.1024 ∙ 104
Claramente podemos observar que el primer dígito del número aparece como el primer decimal en esta forma de representación. Utilizando algunas funciones tales como
{x} = la parte fraccionaria de x, igual a x - ⌊x⌋,
podemos expresar esto como
pd(x) = ⌊10{log10 x}⌋,
donde pd(x) es la función que devuelve el primer dígito del número (esta expresión está limitada a numeros positivos, pero son los que interesan en nuestro caso). Esto nos indica que el primer dígito será:
1 si 0 ≤ {log10 x} < log10 2
2 si log10 2 ≤ {log10 x} < log10 3
...
9 si log10 9 ≤ {log10 x} < 1
donde pd(x) es la función que devuelve el primer dígito del número (esta expresión está limitada a numeros positivos, pero son los que interesan en nuestro caso). Esto nos indica que el primer dígito será:
1 si 0 ≤ {log10 x} < log10 2
2 si log10 2 ≤ {log10 x} < log10 3
...
9 si log10 9 ≤ {log10 x} < 1
Por lo tanto, la determinación de la primera cifra de la expansión decimal de un número se reduce a encontrar en cual de estos intervalos cae la parte fraccionarial de su logaritmo en base 10. Si aplicamos esto a las potencias de dos tenemos que
{log10 2n} = {n log10 2}.
Por consiguiente, la determinación de los posibles valores de los primeros dígitos de las potencias de dos se reduce a encontrar los sectores del intervalo [0, 1) donde caen las partes fraccionarias de los múltiplos de log10 2. Encontrar cuáles son estos sectores y cuál es la conexión de todo esto con las figuras de Lissajous quedará para el próximo post por razones de tiempo :-)
martes, 25 de noviembre de 2008
Lissajous I
Es bien conocido que las representaciones decimales de las potencias de diez comienzan con un dígito '1' y terminan con un dígito '0' (exceptuando el caso trivial de 10 = 1; se supondrán exponentes no nulos en el resto del post). Lo mismo sucederá, cualquiera sea el valor de n, con las representaciones en base n de las potencias de n.
Lo que no es tan claro es el comportamiento de los dígitos en una base dada, por ejemplo 10, de las potencias de un número distinto a la base. Si consideramos el caso de las potencias de 2 expresadas en base 10, podemos ver que terminarán en un dígito par ya que son números pares. Pensando un poco más, podemos ver que nunca terminarán en '0', ya que para ello deberían ser múltiplos de 10 y, por lo tanto, múltiplos de 5. Pero ciertamente quedaría en duda qué otros valores particulares podrán tomar los últimos dígitos...
Los que memorizamos potencias de dos como parte de nuestra actividad académica/profesional :-) podemos ver que:
21 = 2
22 = 4
24 = 16
23 = 8
y que, por lo tanto, todos los otros dígitos pares aparecen al final de las potencias de dos. Pero este es un proceso de enumeración exhaustiva, claramente insatisfactorio a la hora de obtener entendimiento de un proceso.
La primera incógnita que quedará planteada para el próximo post es determinar "que regla" siguen estos dígitos y, de mayor interés, qué regla siguen los dígitos más significativos; por ejemplo, puede una potencia de dos empezar con 9? El otro interrogante será ver que conexión tiene esto con las figuras de Lissajous...
Lo que no es tan claro es el comportamiento de los dígitos en una base dada, por ejemplo 10, de las potencias de un número distinto a la base. Si consideramos el caso de las potencias de 2 expresadas en base 10, podemos ver que terminarán en un dígito par ya que son números pares. Pensando un poco más, podemos ver que nunca terminarán en '0', ya que para ello deberían ser múltiplos de 10 y, por lo tanto, múltiplos de 5. Pero ciertamente quedaría en duda qué otros valores particulares podrán tomar los últimos dígitos...
Los que memorizamos potencias de dos como parte de nuestra actividad académica/profesional :-) podemos ver que:
21 = 2
22 = 4
24 = 16
23 = 8
y que, por lo tanto, todos los otros dígitos pares aparecen al final de las potencias de dos. Pero este es un proceso de enumeración exhaustiva, claramente insatisfactorio a la hora de obtener entendimiento de un proceso.
La primera incógnita que quedará planteada para el próximo post es determinar "que regla" siguen estos dígitos y, de mayor interés, qué regla siguen los dígitos más significativos; por ejemplo, puede una potencia de dos empezar con 9? El otro interrogante será ver que conexión tiene esto con las figuras de Lissajous...
sábado, 18 de octubre de 2008
Sistemas de ecuaciones booleanos
Hace unos días un compañero de la facultad (hola Guille!) me comentaba sobre una clase de problemas que suelen aparecer en los parciales de Matemática Discreta (al menos en la FIUBA). Recordaba que estos problemas consistían en encontrar una función booleana que de como resultado 1 si y solo si los valores de sus parámetros satisfacen un sistema de ecuaciones booleano y eso me hizo recordar un "método" que había desarrollado cuando la había cursado (aunque creo que no tuve ocasión de usarlo en el parcial).
Nota: Las "barras" que se suelen utilizarse para indicar complemento no se expresan fácilmente en HTML. Esto puede resolverse utilizando el operador "¬". Las otras dos operaciones pueden expresarse por "∧" (AND) y "∨" (OR). Por simplicidad, podemos asumir que "∧" tiene prioridad sobre "∨".
Para empezar podemos demostrar que dada una variable y satisfaciendo x ∧ y = 0 y x ∨ y = 1 sabemos que y = ¬x (o sea la unicidad del complemento). Una forma es viendo que:
(1) x ∨ y = 1 (Hipótesis)
(2) ¬x ∧ (x ∨ y) = ¬x ∧ 1 (Aplico la misma operación a ambos miembros)
(3) ¬x ∧ (x ∨ y) = ¬x (Definición de 1)
(4) ¬x ∧ x ∨ ¬x ∧ y = ¬x (Propiedad distributiva)
(5) 0 ∨ ¬x ∧ y = ¬x (Definición de complemento)
(6) x ∧ y = 0 (Hipótesis)
(7) x ∧ y ∨ ¬x ∧ y = ¬x (Reemplazando 6 en 5)
(8) (x ∨ ¬x) ∧ y = ¬x (Propiedad distributiva)
(9) 1 ∧ y = ¬x (Definición de complemento)
(10) y = ¬x (Definición de 1)
Otro "lema" que es útil indica que dados x e y tales que x ∧ y = 1, puede decirse que x = 1 y que y = 1. Una forma de demostrarlo es la siguiente:
(1) x ∧ y = 1 (Hipótesis)
(2) x ∧ y ∨ x ∧ ¬y = 1 ∨ x ∧ ¬y (Aplico la misma operación a ambos miembros)
(3) x ∧ y ∨ x ∧ ¬y = 1 (Propiedad absorbente)
(4) x ∧ (y ∨ ¬y) = 1 (Propiedad distributiva)
(5) x ∧ 1 = 1 (Definición de complemento)
(6) x = 1 (Definición de 1)
Por simetría podemos ver que y = 1 y podemos evitar demostrar la propiedad absorbente para poder llegar alguna vez al tema a tratar :-)
Ahora, podemos ver a todo sistema de ecuaciones como una serie de igualdades entre funciones que requieren satisfacerse. Por ejemplo:
f1(x, y, ...) = g1(x, y, ...)
f2(x, y, ...) = g2(x, y, ...)
f3(x, y, ...) = g3(x, y, ...)
...
Ahora, como sabemos que x ∧ y = 0 y x ∨ y = 1 implican x = ¬y y que x ∧ y = 1 implica que tanto x como y son iguales a 1, podemos expresar una igualdad arbitraria a = b como ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 aplicando lo siguiente:
Ida
(1) a = b (Hipótesis)
(2) a = ¬(¬b) (Propiedad involutiva del complemento)
(3) a ∧ ¬b = 0 (Definición de complemento)
(4) a ∨ ¬b = 1 (Definición de complemento)
(5) ¬(a ∧ ¬b) = ¬0 (Aplico la misma operación a ambos miembros)
(6) ¬(a ∧ ¬b) = 1 (Aplico ¬0 = 1)
(7) ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 (Aplico ∧ miembro a miembro sobre 4 y 6)
Vuelta
(1) ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 (Hipótesis)
(2) ¬(a ∧ ¬b) = 1 (Propiedad demostrada anteriormente)
(3) a ∨ ¬b = 1 (De 1 por propiedad demostrada anteriormente)
(4) ¬¬(a ∧ ¬b) = ¬1 (Aplico la misma operación a ambos miembros)
(5) a ∧ ¬b = ¬1 (Propiedad involutiva del complemento)
(6) a ∧ ¬b = 0 (Aplico ¬1 = 0)
(7) a = ¬¬b (Aplico otra propiedad demostrada anteriormente sobre 3 y 6)
(8) a = b (Propiedad involutiva del complemento)
Si omitimos que no demostramos ni la propiedad involutiva del complemento ni que ¬0 = 1 (las demostraciones son simples, quedan como ejercicio para el lector :-), sabemos como transformar una ecuación arbitraria en una igualada a 1. Ahora podemos aplicar que x ∧ y = 1 implica que x = y = 1 para expresar el sistema de ecuaciones anterior como:
¬(f1(x, y, z, ...) ∧ ¬g1(x, y, z, ...)) ∧
(f1(x, y, z, ...) ∨ ¬g1(x, y, z, ...)) ∧
¬(f2(x, y, z, ...) ∧ ¬g2(x, y, z, ...)) ∧
(f2(x, y, z, ...) ∨ ¬g2(x, y, z, ...)) ∧
¬(f3(x, y, z, ...) ∧ ¬g3(x, y, z, ...)) ∧
(f3(x, y, z, ...) ∨ ¬g3(x, y, z, ...)) ∧
... = 1
Esto cumple en forma automática el objetivo del problema aunque puede ser algo tedioso...
Nota: Las "barras" que se suelen utilizarse para indicar complemento no se expresan fácilmente en HTML. Esto puede resolverse utilizando el operador "¬". Las otras dos operaciones pueden expresarse por "∧" (AND) y "∨" (OR). Por simplicidad, podemos asumir que "∧" tiene prioridad sobre "∨".
Para empezar podemos demostrar que dada una variable y satisfaciendo x ∧ y = 0 y x ∨ y = 1 sabemos que y = ¬x (o sea la unicidad del complemento). Una forma es viendo que:
(1) x ∨ y = 1 (Hipótesis)
(2) ¬x ∧ (x ∨ y) = ¬x ∧ 1 (Aplico la misma operación a ambos miembros)
(3) ¬x ∧ (x ∨ y) = ¬x (Definición de 1)
(4) ¬x ∧ x ∨ ¬x ∧ y = ¬x (Propiedad distributiva)
(5) 0 ∨ ¬x ∧ y = ¬x (Definición de complemento)
(6) x ∧ y = 0 (Hipótesis)
(7) x ∧ y ∨ ¬x ∧ y = ¬x (Reemplazando 6 en 5)
(8) (x ∨ ¬x) ∧ y = ¬x (Propiedad distributiva)
(9) 1 ∧ y = ¬x (Definición de complemento)
(10) y = ¬x (Definición de 1)
Otro "lema" que es útil indica que dados x e y tales que x ∧ y = 1, puede decirse que x = 1 y que y = 1. Una forma de demostrarlo es la siguiente:
(1) x ∧ y = 1 (Hipótesis)
(2) x ∧ y ∨ x ∧ ¬y = 1 ∨ x ∧ ¬y (Aplico la misma operación a ambos miembros)
(3) x ∧ y ∨ x ∧ ¬y = 1 (Propiedad absorbente)
(4) x ∧ (y ∨ ¬y) = 1 (Propiedad distributiva)
(5) x ∧ 1 = 1 (Definición de complemento)
(6) x = 1 (Definición de 1)
Por simetría podemos ver que y = 1 y podemos evitar demostrar la propiedad absorbente para poder llegar alguna vez al tema a tratar :-)
Ahora, podemos ver a todo sistema de ecuaciones como una serie de igualdades entre funciones que requieren satisfacerse. Por ejemplo:
f1(x, y, ...) = g1(x, y, ...)
f2(x, y, ...) = g2(x, y, ...)
f3(x, y, ...) = g3(x, y, ...)
...
Ahora, como sabemos que x ∧ y = 0 y x ∨ y = 1 implican x = ¬y y que x ∧ y = 1 implica que tanto x como y son iguales a 1, podemos expresar una igualdad arbitraria a = b como ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 aplicando lo siguiente:
Ida
(1) a = b (Hipótesis)
(2) a = ¬(¬b) (Propiedad involutiva del complemento)
(3) a ∧ ¬b = 0 (Definición de complemento)
(4) a ∨ ¬b = 1 (Definición de complemento)
(5) ¬(a ∧ ¬b) = ¬0 (Aplico la misma operación a ambos miembros)
(6) ¬(a ∧ ¬b) = 1 (Aplico ¬0 = 1)
(7) ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 (Aplico ∧ miembro a miembro sobre 4 y 6)
Vuelta
(1) ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 (Hipótesis)
(2) ¬(a ∧ ¬b) = 1 (Propiedad demostrada anteriormente)
(3) a ∨ ¬b = 1 (De 1 por propiedad demostrada anteriormente)
(4) ¬¬(a ∧ ¬b) = ¬1 (Aplico la misma operación a ambos miembros)
(5) a ∧ ¬b = ¬1 (Propiedad involutiva del complemento)
(6) a ∧ ¬b = 0 (Aplico ¬1 = 0)
(7) a = ¬¬b (Aplico otra propiedad demostrada anteriormente sobre 3 y 6)
(8) a = b (Propiedad involutiva del complemento)
Si omitimos que no demostramos ni la propiedad involutiva del complemento ni que ¬0 = 1 (las demostraciones son simples, quedan como ejercicio para el lector :-), sabemos como transformar una ecuación arbitraria en una igualada a 1. Ahora podemos aplicar que x ∧ y = 1 implica que x = y = 1 para expresar el sistema de ecuaciones anterior como:
¬(f1(x, y, z, ...) ∧ ¬g1(x, y, z, ...)) ∧
(f1(x, y, z, ...) ∨ ¬g1(x, y, z, ...)) ∧
¬(f2(x, y, z, ...) ∧ ¬g2(x, y, z, ...)) ∧
(f2(x, y, z, ...) ∨ ¬g2(x, y, z, ...)) ∧
¬(f3(x, y, z, ...) ∧ ¬g3(x, y, z, ...)) ∧
(f3(x, y, z, ...) ∨ ¬g3(x, y, z, ...)) ∧
... = 1
Esto cumple en forma automática el objetivo del problema aunque puede ser algo tedioso...
miércoles, 2 de julio de 2008
Un problema de probabilidad
En un juego, se presentan a una persona dos sobres. Sabe que uno de ellos contiene una cantidad desconocida de dinero 'A', y que el otro contiene el doble de esa cantidad, pero el jugador desconoce "cuál es cual". Se le dice que puede llevarse solo uno de los sobres y que debe llevarse el último sobre que abra.
La pregunta es: después de haber elegido y abierto un sobre, le conviene cambiarlo por el otro?
La respuesta intuitiva es "no", ya que ver el contenido del sobre no nos permite discriminar entre el caso en que elegimos el sobre con la cantidad A y el caso en que elegimos el sobre con al cantidad 2A. Al no tener evidencia proveniente de ver el contenido del sobre, el intercambio nos sería indiferente.
Ahora supongamos que calculamos el valor esperado del contenido del sobre no abierto, al que denominaremos "sobre 2". Si llamamos B al contenido del sobre abierto, el sobre 2 puede tener contenido B/2 o 2B. Asumiendo la indiferencia mencionada anteriormente, el valor esperado del contenido del sobre 2 sería:
E(contenido sobre 2) = 1/2 B/2 + 1/2 2B = B/4 + B = 5/4 B
Esto implicaría que siempre nos sería conveniente realizar el intercambio!
Más detalles sobre el problema y sus implicaciones en Wikipedia...
La pregunta es: después de haber elegido y abierto un sobre, le conviene cambiarlo por el otro?
La respuesta intuitiva es "no", ya que ver el contenido del sobre no nos permite discriminar entre el caso en que elegimos el sobre con la cantidad A y el caso en que elegimos el sobre con al cantidad 2A. Al no tener evidencia proveniente de ver el contenido del sobre, el intercambio nos sería indiferente.
Ahora supongamos que calculamos el valor esperado del contenido del sobre no abierto, al que denominaremos "sobre 2". Si llamamos B al contenido del sobre abierto, el sobre 2 puede tener contenido B/2 o 2B. Asumiendo la indiferencia mencionada anteriormente, el valor esperado del contenido del sobre 2 sería:
E(contenido sobre 2) = 1/2 B/2 + 1/2 2B = B/4 + B = 5/4 B
Esto implicaría que siempre nos sería conveniente realizar el intercambio!
Más detalles sobre el problema y sus implicaciones en Wikipedia...
Suscribirse a:
Entradas (Atom)