martes, 30 de septiembre de 2014

Números de Frobenius

Un teorema clásico de teoría de números es el siguiente: Sean a y b enteros positivos tales que (a,b)=1. Entonces para cualquier entero n, existen enteros x y y tales que ax+by=n.
Pero que tal si sólo se vale usar enteros no negativos para x y y. Entonces ax+by no necesariamente puede tomar el valor de todo entero. El siguiente teorema responde que números se pueden representar de la forma ax+by:


TEOREMA: Sean a y b enteros positivos tales que (a,b)=1. Existe un número máximo m llamado número de Frobenius de a y b que satisface que para todo entero n>m, existen enteros x,y0 tales que ax+by=n,
y no existen enteros x y y tales que ax+by=m.
Es decir, los números suficientemente grandes pueden escribirse de la forma ax+by donde x y y son mayores o iguales a 0. La demostración del teorema se los dejo como ejercicio. Como pista les digo que m=(a1)(b1)1.

Les platico un ejemplo de una aplicación de este teorema:
Consideremos el problema 1 del examen de desempate: "Un número compa es tal que no tiene dígitos cero y la suma de los cuadrados de cada uno de sus dígitos es un cuadrado perfecto. (Por ejemplo, 122 y 34 cada uno es compa pero 304 y 12 ninguno lo es). Demostrar que para cada n>1 existe un número compa con exactamente n dígitos."

Los que lo resolvieron (de los que revise) usaron la idea de usar que para n cuadrado, se pueden poner puros 5's y luego cambiar un 5 por 34 y así probar que se puede n+1. Seguir cambiando 5's por 34's uno por uno hasta llegar al siguiente cuadrado. Luego se tendría que demostrar que el siguiente cuadrado llega antes de que se acaben los 5's. La idea es muy bonita y sencilla. Pero que tal si uno está atrapado en el problema y no se le ocurren ideas. Aquí les platico mi solución por "fuerza bruta" usando Frobenius:

Sea n el entero para el que queremos encontrar un número compade n dígitos. Empezamos con el número 1111 con n 1's. Si es cuadrado que bueno, pero si no es cuadrado haber que hacemos. Notemos que cambiar un 1 por un 2 cambia la suma por 3. Cambiar un 1 por un 3 cambia la suma por 8. Entonces si cambiamos x 1's por 2's y y 1's por 3's, la suma total es n+3x+8y. Por el teorema mencionado, existe un m tal que 3x+8y=k para todo k>m. Como mencione m=(a1)(b1)1=2(7)1=13. Entonces en teoría podemos representar todos los números de la forma n+k para todo k14. Un problema es que tenemos una restricción extra en x y y. Sabemos que x+yn. Entonces tenemos que trabajar un poco más.

Notemos que los números del 14 al 21 se pueden representar con 3's y 8's de la siguiente manera: 14=3×2+8×1, 15=3×5, 16=8×2, 17=3×3+8×1, 18=3×6, 19=3×1+8×2, 20=3×4+8×1, 21=3×7. De estos casos el que necesitó más 3's y 8's es 21 que necesito 7 cosas (7 3's para ser exactos). Sabemos que Frobenius garantiza que podemos representar de 14 para arriba como 3x+8y si no hay restricción en x y y, pero como x+yn entonces tenemos una restricción. La pregunta es que tan alto podemos llegar. Supongamos que n7 para que podamos garantizar los números del 14 al 21. Ahora queremos llegar más lejos. Si tenemos un número mayor a 21, podemos restarle 8 muchas veces hasta que este en el intervalo entre 15 y 22. Luego con 7 números podemos terminar. Por lo tanto podemos restar 8 hasta n7 veces y luego usar las últimas 7. Eso implica que podemos generar todos los números entre 14 y 8(n7)+21=8n35.

Por lo tanto hemos demostrado que si n7 y m{14,15,,8n35} entonces existen x y y enteros no-negativos tales que x+yn y 3x+8y=m.
Por lo tanto cambiando 1's por 2's y 3's podemos generar cualquier número entre n+14 y 9n35 (si n7). De hecho podemos generar un poco más, ya que también podemos generar n, n+3, n+6, n+8 y n+11, pero esta información no la usaremos.

Si podemos garantizar que hay un cuadrado entre n+14 y 9n35 entonces ya tenemos un compa de n dígitos. Una solución fácil (y sobrada) es notar que si m no es cuadrado entonces existe un cuadrado entre m y 4m4. Ya que si mr es cuadrado entonces 4m4r es cuadrado. Por lo tanto basta checar que 9n35(n+13)4=4n+52. Por lo tanto basta checar que 5n87. Entonces basta que n18 para garantizar que hay un cuadrado. Los casos chicos se pueden talachear. Los n7 se puede checar el intervalo (n+14,9n35) y verificar que si hay un cuadrado por allí (para n=7,8,9,10,11, el cuadrado es 25, para n=12,13,14,15,16,17 el cuadrado es 36). Y los casos menores a 7 se encuentran uno por 1. n=2 tenemos 34. n=3 tenemos 122. n=4 tenemos 1111. n=5 tenemos 11123. n=6 tenemos 111112. Y listo!


Ahora que tenemos un ejemplo del uso de Frobenius, aquí va un problema de la lista corta del 2004 usado como selectivo para la IMO en Italia en el 2005:

IMO Shortlist 2004
Sea f:{1,2,,1600}{1,2,,1600} tal que f2005(x)=x para x=1,2,1600 y f(1)=1. (Nota: f2005(x) significa f(f(f(f(f((f(x))))) 2005 veces).
a) Demuestra que f tiene al menos otro punto fijo (además de f(1)=1).
b) Determina los n>1600 que satisfacen que cualquier f:{1,2,,n}{1,2,,n} satisface f2005(x)=x, para x=1,2,,n y f(1)=1 y tiene otro punto fijo.

1 comentario:

  1. Puse un post con la demostracion de la existencia del numero de frobenius, lo del problema de la shorlist la subo despues

    ResponderBorrar