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,y \ge 0$ 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 = (a-1)(b-1)-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 $111\ldots1$ 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 = (a-1)(b-1) - 1 = 2(7)-1 = 13$. Entonces en teoría podemos representar todos los números de la forma $n + k$ para todo $k\ge 14$. Un problema es que tenemos una restricción extra en $x$ y $y$. Sabemos que $x + y \le n$. 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\times 2 + 8\times 1$, $15 = 3\times 5$, $16 = 8\times 2$, $17 = 3\times 3 + 8\times 1$, $18 = 3\times 6$, $19 = 3\times 1 + 8\times 2$, $20 = 3\times 4 + 8\times 1$, $21 = 3\times 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 + y \le n$ entonces tenemos una restricción. La pregunta es que tan alto podemos llegar. Supongamos que $n\ge 7$ 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 $n-7$ veces y luego usar las últimas 7. Eso implica que podemos generar todos los números entre 14 y $8(n-7) + 21 = 8n - 35$.

Por lo tanto hemos demostrado que si $n\ge 7$ y $m\in\{14,15,\ldots, 8n-35\}$ entonces existen $x$ y $y$ enteros no-negativos tales que $x + y\le n$ 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 $9n - 35$ (si $n\ge 7$). 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 $9n-35$ 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 $4m-4$. Ya que si $m-r$ es cuadrado entonces $4m-4r$ es cuadrado. Por lo tanto basta checar que $9n -35 \ge (n+13)4 = 4n + 52$. Por lo tanto basta checar que $5n \ge 87$. Entonces basta que $n \ge 18$ para garantizar que hay un cuadrado. Los casos chicos se pueden talachear. Los $n \ge 7$ se puede checar el intervalo $(n+14, 9n-35)$ 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,\ldots,1600\} \rightarrow \{1,2,\ldots,1600\}$ tal que $f^{2005}(x) = x$ para $x = 1,2,\ldots 1600$ y $f(1) = 1$. (Nota: $f^{2005}(x)$ significa $f(f(f(f(f(\ldots(f(x))))\ldots)$ 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,\ldots,n\} \rightarrow \{1,2,\ldots,n\}$ satisface $f^{2005}(x) = x$, para $x = 1,2,\ldots,n$ y $f(1) = 1$ y tiene otro punto fijo.