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.

Solución Problema 1 del 30 de septiembre

Solucion geometria 28 de septiembre

Solución números 30/9

Números (2) 30 de Septiembre (Arturo)

1. Encontrar todas las parejas $p,q$ de primos tales que $(p-q)^{3}=p+q$

2. Los números $p,q$ son primos y satisfacen
\[\frac{p}{{p+1}}+\frac{{q+1}}{q}=\frac{{2n}}{{n+2}}\]
para algún entero positivo $n$. Encuentra todos los posibles valores de $q-p$

Tiempo recomendado para resolver el problema: 1) 30 minutos 2) 1hr y media

Dato interesante: Triangulos rectangulos / puntos medios

Una propiedad interesante que les he recalcado cada vez que puedo es cuando tienen un triangulo rectángulo y su punto medio (de la hipotenusa). Se generan segmentos iguales (dado que el punto medio es el centro del circuncírculo) Pero la propiedad también funciona a la inversa, por lo que les puede ayudar a visualizar cosas mas rápido (e.g. el paso (1) de la solución).
Aunque este problema estaba fácil y muchas veces pueden darse cuenta de eso por angulitos, el hecho que sea información que puedan obtener rápidamente les puede servir antes de tapizar el dibujo de angulitos. (como verán en mi dibujo prácticamente no use angulitos a pesar que hay MONTON de angulitos iguales.) Y a lo mejor no lo usan al instante, pero marcar ese angulo recto les puede facilitar para obtener mas cosas.

Solución geo 28/9

Solución álgebra 27/9

Solución combi 26/9

Problema del día 29/09/2014 (Payan)

Se quiere colocar alrededor de un circulo de modo que satisfaga la siguiente propiedad: los valores absolutos de las diferencias de números vecinos son todos distintos.
a)¿Es posible colocar los números del 1 al 2009 de modo que cumpla la propiedad?
b)¿Es posible suprimir alguno de los números del 1 al  2009 de modo que los 2008 restantes se puedan acomodar cumpliendo la propiedad?

Solución problema de Algebra 27 de septiembre

Solucion al problema de alonso del 28 de septiembre

Solcuion al problema de pepe del 27 de septiembre

Geometria 28/septiembre (Alonso)

Let be a convex quadrangle, the intersection of lines and , the intersection of lines and and the intersection of diagonals and . Show that if then is the bisector of and is the bisector of .

Sea ABCD un cuadrilatero convexo, p la interseccion de AB y CD, Q la interseccion de AD y BC y O la interseccion de las diagonales AC y BD.Prueba que si POQ=90 entonces PO is bisectriz de OD y OQ es bisectriz de AOB

Problema de Álgebra, 27 de septiembre (Pepe).

Encontrar todas las parejas de enteros no negativos $(m,n)$ que cumplen $3*2^m+1=n^2$.

Problema del día. Combinatoria. (Antonio)

Sea un entero positivo. Encuentra el menor entero con la siguiente propiedad; Dados cualesquiera numeros reales     tal que y   para , es posible dividir estos numeros en conjuntos (algunos de ellos tal vez vacios)  tal que la suma de los numeros en cada conjunto es a lo mas .

Solución problema 25 de septiembre

PROOBLEMA DEL DIA 25 DE SEPTIEMBRE (Enrique)

El triangulo equilátero ABC está inscrito en una circunferencia y en el arco BC se toma un punto arbitrario M. Demostrar que AM=BM+CM

Tiempo recomendado para el problema: 45 minutos

Leccion de vectores

En el intensivo les puse unos problemas que planeaba resolver usando vectores, y que por el relajo de tanto examen (y el cansancio subsecuente por estar viejo), ya no comente las soluciones.
Me gustaría que le echaran un ojo a esta lección,

Sum of vectors connecting the center of mass of a n-sided polygon with its vertices


ahí (o en los links de lo que van usando) viene lo que prácticamente quería que viéramos.

Recuerden comentar en cada post (aunque sea un "leído y entendido claramente" en el caso de no ser un problema que tengan que resolver), y claro si tienen otro tipo de comentarios, preguntas, son bienvenidos.

Panda

Funciones

Encontremos todas las funciones f : Q → R que cumplen con las siguientes condiciones, f(xy) = xf(y) + yf(x) y f(x + y) = f(x2) + f(y2), para x,y ∈ Q.