March 11, 2010 by mchouza

Otra forma de pensar Taylor

En primer lugar, en el post anterior había dejado planteado el siguiente problema:

Dado un conjunto de 51 números dentro del intervalo 1-100 (incluyendo los extremos), demostrar que existen al menos dos números en ese conjunto que no comparten ningún divisor (a excepción de 1, obviamente).

Así que, antes de empezar con el tema en sí de este post, no puedo hacer menos que presentar mi demostración 😉

El problema de los 51 números

La prueba que pensé se divide en dos pasos:

Paso 1: Determinar que al menos dos de los 51 números deben ser adyacentes.
Paso 2: Determinar que dos números adyacentes no comparten divisores no triviales.

Paso 1

Es intuitivamente razonable que, dados 51 números en un intervalo de 100, al menos dos deben ser adyacentes. ~~Pero como la demostración que encontré no es muy elegante, la separé en una página auxiliar.~~ (Dejo la primera demostración como ejemplo de cuanto más complejo de lo necesario puede hacerse algo…)

Definamos 100 variables 0-1 x₁, x₂, …, x₁₀₀ para representar el subconjunto en cuestión. Claramente la condición sobre la cantidad de elementos puede representarse como

$\displaystyle \sum_{i=1}^{100} x_i = 51$

Si agrupamos la suma en 50 pares obtenemos

$\displaystyle \sum_{i=0}^{49} x_{2i+1} + x_{2i+2} = \sum_{i=0}^{49} y_i = 51$

Esto implica que el valor medio de los y_i es 51/50 = 1.02 > 1. Pero como los y_i solo pueden tomar los valores enteros 0, 1 y 2, eso implica que existe al menos un y_i que vale 2. En consecuencia, existen necesariamente en el subconjunto dos números adyacentes.

Paso 2

Es bien conocido, y la base del algoritmo de Euclides, que

$\mathrm{gcd}(a, b) = \mathrm{gcd}(a, b \% a)$ ,

donde $\%$ se utiliza para indicar reducción modular al estilo C.

Ahora, si dos números a y b son adyacentes, entonces podemos decir sin pérdida de generalidad que b = a + 1. Por lo tanto:

$\mathrm{gcd}(a, b) = \mathrm{gcd}(a, a+1) = \mathrm{gcd}(a, (a+1) \% a) = \mathrm{gcd}(a, 1) = 1$ .

Por ende, dos números adyacentes no pueden tener factores en común.

Conclusión

Como los 51 números en {1, 2, …, 100} deben incluir al menos un par de números adyacentes y los números adyacentes no tienen factores en común, entonces los 51 números en {1, 2, …, 100} deben incluir al menos un par de números sin factores comunes.

Taylor

Las demostraciones normales del Teorema de Taylor siempre me parecieron poco motivadas: son indudablemente correctas, pero no queda claro porqué uno iría por ese camino. Hace unos años encontré una demostración que, aunque no me cabe duda que debe haber sido conocida por los egipcios :-P, nunca vi en otro lado.

Para simplificar realicemos la expansión alrededor de cero (serie de Maclaurin). No cambia los resultados pero disminuye el “ruido” en las expresiones.

La idea básica es utilizar el hecho de que toda función derivable $f(x)$ puede ser representada en función de su valor en 0 y su derivada del siguiente modo:

$\displaystyle f(x) = f(0) + \int_0^x dx_1 f'(x_1)$

Si la función puede ser derivada múltiples veces, el proceso puede ser aplicado en forma recursiva:

$\displaystyle f'(x) = f'(0) + \int_0^x dx_1 f''(x_1)$

$\displaystyle f''(x) = f''(0) + \int_0^x dx_1 f'''(x_1)$

$\displaystyle \ldots$

Combinando estas representaciones podemos representar a una función en término de su valor, el de las n-1 primeras derivadas en cero y su derivada n-ésima:

$\displaystyle f(x) = f(0) + \int_0^x dx_1 \left( f'(0) + \int_0^{x_1} dx_2 \left( f''(0) + \ldots \right) \right)$

Para poder simplificar estas expresiones es necesario resolver integrales de la forma

$\displaystyle \int_0^x dx_1 \int_0^{x_1} dx_2 \ldots \int_0^{x_{n-1}} dx_n$ .

Esto podría hacerse por inducción pero, como estoy un poco quemado de utilizar esa técnica, podemos hacerlo por inspección simplemente:

$\displaystyle \int_0^x dx_1 = x$

$\displaystyle \int_0^x dx_1 \int_0^{x_1} dx_2 = \int_0^x dx_1 x_1 = \frac{x^2}{2}$

$\displaystyle \int_0^x dx_1 \int_0^{x_1} dx_2 \int_0^{x_3} dx_3 = \int_0^x dx_1 \frac{x_1^2}{2} = \frac{x^3}{3 \cdot 2}$

$\displaystyle \int_0^x dx_1 \int_0^{x_1} dx_2 \int_0^{x_3} dx_3 \int_0^{x_4} dx_4 = \int_0^x dx_1 \frac{x_1^3}{3 \cdot 2} = \frac{x^4}{4 \cdot 3 \cdot 2}$

Observando como opera esta progresión, no es difícil observar (o demostrar por inducción) que

$\displaystyle \int_0^x dx_1 \int_0^{x_1} dx_2 \ldots \int_0^{x_{n-1}} dx_n = \frac{x^n}{n!}$ .

Si aplicamos esto a la expresión anterior de $f(x)$ obtendremos

$\displaystyle f(x) = f(0) + f'(0) x + f''(0) \frac{x^2}{2} + \ldots + \int_0^x dx_1 \ldots \int_0^{x_{n-1}} dx_n f^{(n)}(x_n)$ ,

donde $f^{(n)}$ representa la derivada n-ésima de $f$ .

Acotando la última integral, podemos ver que

$\displaystyle \left| \int_0^{x_{n-1}} dx_n f^{(n)}(x_n) \right| < \int_0^{x_{n-1}} dx_n M = M x_{n-1}$ ,

siendo $M$ una cota del valor absoluto de $f^{(n)}(x)$ en el intervalo $[0, x_{n-1}]$ (supongo $x > 0$ sin pérdida de generalidad). Eso implica que

$\displaystyle \left| \int_0^x dx_1 \ldots \int_0^{x_{n-1}} dx_n f^{(n)}(x_n) \right| < M \int_0^x dx_1 \ldots \int_0^{x_{n-1}} dx_n$ ,

donde $M$ es ahora una cota del valor absoluto de $f^{(n)}(x)$ en el intervalo $[0, x]$ . Esta última integral podemos evaluarla explíctamente, dándonos una cota explícita para este último término en función de $x$ y una cota para $f^{(n)}$ en el intervalo $[0, x]$ :

$\displaystyle \left| \int_0^x dx_1 \ldots \int_0^{x_{n-1}} dx_n f^{(n)}(x_n) \right| < M \frac{x^n}{n!}$ .

Combinando todos estos resultados, y usando la nomenclatura $f^{(0)} = f$ por consistencia, podemos decir que, si $f$ es n veces derivable en un entorno de 0,

$\displaystyle f(x) = \sum_{i=0}^{n-1} \frac{f^{(i)}(0)}{i!} + Err(x)$ ,

estando el término de error $Err(x)$ acotado del siguiente modo:

$\displaystyle |Err(x)| = \left| \int_0^x dx_1 \ldots \int_0^{x_{n-1}} dx_n f^{(n)}(x_n) \right| < M \frac{x^n}{n!}$ .

Esto significa que, si asumimos que la derivada n-ésima toma valores $O(1)$ , truncar la serie después del término con la derivada de orden n-1 nos dejará una aproximación $O(x^n)$ a la función.

Próximo post

Con algo de suerte, será sobre la detección de cubos…

March 7, 2010 by mchouza

Una respuesta y otro problema

[Continuacion de Excusas et cetera]

Además de las soluciones de Demian y Guille, armé 5 soluciones propias con distintas características. Pueden verse todos los tests realizados a estas soluciones en el repositorio SVN “asociado” a este blog.

La solución de Guille fallaba a causa del problema identificado por Demian y puede verse a mi solución 4 como una adaptación del algoritmo recursivo de Guille para realizar el bubble sort completo. Aunque bubble sort suele ser duramente criticado, es de hecho óptimo (en las circunstancias apropiadas, ver Improved Bounds on Sorting by Length-Weighted Reversals, Lemma 59 😀 ).

Mis soluciones

A continuación muestro las distintas soluciones que planteé, cada una demostrando algo en particular.

Solución 1 – Arrays

Esta es una solución simple, esencialmente idéntica a la primera de Demian.

void f1(int* a, size_t n)
{
    size_t i = 0, j;
    for (j = 0; j < n; j++)
        if (a[j])
            a[i++] = a[j];
    for (; i < n; i++)
        a[i] = 0;
}

Solución 2 – Punteros

Esta es una adaptación simple de la Solución 1 para utilizar punteros.

void f2(int* p, size_t n)
{
    int *q, *r;
    for (q = p, r = p + n; q < r; q++)
        if (*q)
            *p++ = *q;
    for (; p < r; p++)
        *p = 0;
}

Solución 3 – Obfuscated

Esta es una versión optimizada para ser difícil de entender, empleando solo una definición y un “statement”.

void f3(int* p, size_t n)
{
    int *q = p, *r = p + n;
    while ((r - p) *
           (r - q ? *q ? (*p++ = *q++) : ++q - p : (*p++ = 0) + 1));
}

Solución 4 – Recursiva

Esta es la solución de Guille, adaptada para realizar una pasada completa de “burbujeo” en cada llamada recursiva. De las soluciones que encontré, es la única que no requiere variables adicionales (aunque obviamente utiliza múltiples instancias del stack frame).

void f4(int* p, size_t n)
{
    if (n == 0)
        return;
    f4(p + 1, n - 1);
    while (n >= 2)
    {
        if (!p[0] && p[1])
        {
            /* xor swap */
            /* Proof:
               p0' = p0 ^ p1
               p1f = p1 ^ p0'
                   = p1 ^ p0 ^ p1
                   = p0
               p0f = p0' ^ p1f
                   = p0 ^ p1 ^ p0
                   = p1
            */
            p[0] ^= p[1];
            p[1] ^= p[0];
            p[0] ^= p[1];
        }
        p++;
        n--;
    }
}

Solución 5 – Utilizando solo una variable extra

Esta solución es una “mezcla” de las soluciones 1 y 2 modificada para utilizar solo una variable temporal. Dudo que sea posible resolver el problema sin variables temporales extras (aparte de los parámetros), pero no parece simple probarlo…

void f8(int* a, size_t n)
{
    size_t j;
    for (j = 0; j < n; j++)
    {
        if (a[j])
            a[0] = a[j], a++, j--, n--;
    }
    for (j = 0; j < n; j++)
        a[j] = 0;
}

Un problema matemático

Hace unos días vi en el blog de Michael Nielsen un interesante problema:

Dado un conjunto de 51 números dentro del intervalo 1-100 (incluyendo los extremos), demostrar que existen al menos dos números en ese conjunto que no comparten ningún divisor (a excepción de 1, obviamente).

(No, no vi inmediatamente la respuesta 😀 )

March 2, 2010 by mchouza

Excusas et cetera

Originalmente tenía pensado publicar la primera parte de la respuesta al post sobre detección de cubos este fin de semana pasado, pero los videos de Susskind y Coleman sobre QFT se interpusieron 😀

Siempre creí que las clases expositivas eran bastante redundantes pero, cuando el material es dificultoso como en este caso, el inevitable “unpacking” que ocurre al explicar los temas “en vivo” se vuelve una ventaja importante. Los videos de Susskind son bastante fáciles de seguir para los que fueron siguiendo la serie en general, pero a veces pueden resultar un poco “handwavy”. Los de Coleman son bastante más rigurosos pero tienen mala calidad de filmación (incluso para 1975) y presuponen más conocimientos matemáticos y de mecánica cuántica de los que tengo, lo que me dificulta seguirlos.

Para no dejar todo en la nada, ofrezco un problema de programación C inspirado en uno visto (si no recuerdo mal) en algún comentario en el blog de Eric Raymond:

Enunciado:

Dado un vector de enteros, implementar una función que mueva “en el lugar” los ceros al final del vector dejando los otros enteros en el orden original. El prototipo de la función deberá ser:

void foo(int* a, size_t n).

Ejemplos de efectos sobre el vector pasado por parámetro:

{5, 0, 4, 0, 0, 3, 0, 0, 0, 2} --> {5, 4, 3, 2, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 1, 2, 3, 0, 4} --> {1, 2, 3, 4, 0, 0, 0, 0}

Algunas respuestas a esto, salvando fuerza mayor, este fin de semana. Ustedes pueden dejar otras respuestas en los comentarios que serán debidamente analizadas… 😀

Spin Foam

Just another WordPress.com weblog

Monthly Archives: March 2010