OMA Foros

FOFO ANIVERSARIO: 14 AÑOS
COSMIC FOFO

OMA Foros cumple 14 años y ya está en edad de OMA! Para festejar que por fin va a conocer a Floricia, vamos a hacer nuevamente una edición de la/el FOFO para todos los olímpicos que transitan por la más bella Olimpíada...

¿Qué es el FOFO?
Es como un falso OFO (y OFO es la competencia online que hacemos durante el verano, también conocido como el falso FOFO).

¿Cuándo se llevará a cabo?
La competencia se llevará a cabo desde el Viernes 11 de Octubre a las 00:00 hs hasta el Domingo 13 de Octubre a las 23:59 hs.

¿Cómo me inscribo?
Comentando en este post "me inscribo" o algo similar.

¿Cómo es el sistema?
Cuando sea la competencia vamos a proponer una cierta cantidad de problemas. Estos problemas se van a publicar el Viernes 11 de Octubre a las 00:00 hs aquí en el foro en un post CERRADO (nadie va a poder responder en el propio post). La solución a cada problema la deberán enviar por mensaje privado a quien figure como autor del post (que además será el encargado de corregir dicha solución). Tendrán tiempo para enviar soluciones hasta el Domingo 13 de Octubre a las 23:59 hs. Se pueden consultar apuntes y material de Internet, pero no está permitido utilizar software para pensar problemas. Recomendamos fuertemente enviar soluciones escritas en $\LaTeX$. Pueden leer aquí como utilizarlo.

¿Cómo es el sistema de corrección?
Los puntajes consisten en un número entero entre 0 y 7.

¿Cómo me entero de cómo me fue?
Una vez concluido el período de envío de soluciones se publicará una lista con los primeros puestos. Los participantes que obtengan mayor puntaje recibirán una medallita especial, y los demás que también tengan un buen desempeño recibirán una mención especial.

¿Pueden participar ex-olímpicos?
No pueden participar ex-olímpicos. Es sólo para actuales participantes de olimpíadas.

¿Se pueden consultar apuntes, material en Internet, o usar software específico para pensar los problemas de geometría?
Se pueden consultar apuntes y material de Internet, pero no está permitido utilizar software para pensar problemas. Sí está permitido, y recomendamos fuertemente, incluir en las soluciones a los problemas de geometría figuras de análisis (las cuales pueden hacer utilizando algún software, como Geogebra).

Si

p y

q son enteros positivos y

\frac{1}{1}-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+...-\frac{1}{1318}+\frac{1}{1319}=\frac{p}{q} \Rightarrow 1979|p.

Uno fácil.

Se da un triángulo acutángulo en el que los tres ángulos miden un número entero de grados y el ángulo mayor es cinco veces el ángulo menor. Hallar los ángulos.

El Lema de Mihai, Lema de Hensel, o "Lema Lifting the exponent" es un poderoso recurso en problemas de Teoría de Números.

El enunciado dice lo siguiente:

Sea

p un primo impar y

a un entero positivo, tales que la mayor potencia de

p que divide a

a-1 sea

p^x con

x > 0. Si la mayor potencia de

p que divide a

n es

p^y, entonces la mayor potencia de

p que divide a

a^n-1 es

p^{x+y}.

Sea

p un primo impar y

a un entero positivo, tales que la mayor potencia de

p que divide a

a+1 sea

p^x con

x > 0. Si la mayor potencia de

p que divide a

n (con

n impar) es

p^y, entonces la mayor potencia de

p que divide a

a^n+1 es

p^{x+y}.

En otros términos, decimos que

a^k \parallel b si

a^k \mid b pero

a^{k+1} \nmid b, y entonces el Lema queda:

Si

p es un primo impar, y

p^x\parallel a-1 con

x>0 y

p^y \parallel n. Entonces

p^{x+y} \parallel a^n-1.

Si

p es un primo impar y

p^x\parallel a+1 con

x>0 y

p^y\parallel n con

n impar, entonces

p^{x+y} \parallel a^n+1.

(Hay otras versiones más generalizadas y otros casos más particulares de este lema, pero nos quedamos, por el momento, sólo con el lema original).

Un problema que puede ser resuelto de manera rápida con este lema:

Olimpíada Rioplatense 2004, Segundo Nivel, Problema 2:

Encontrar todos los valores enteros estrictamente positivos de

k,

n y

p que satisfacen la siguiente ecuación:

\displaystyle{5^k - 3^n = p^2}

Solución:

Spoiler: mostrar: Rápidamente, módulo 3, tenemos que 5^k \equiv p^2 \equiv 1 \pmod{3}, de donde se ve que k es par. Sea k=2a.
Además, en módulo 4, se tiene que p^2 + 3^{n} \equiv 1 \pmod{4}, y como p es par, se tiene que 3^n \equiv 1 \pmod{4}, de donde n también es par. Sea n=2b.

Nuestra ecuación ahora es 5^{2a} - 3^{2b} = p^2, entonces 5^{2a} = p^2 + 3^{2b}, por lo que \{p, 3^b, 5^a\} forman una terna pitagórica. Entonces existen dos números x,y coprimos tales que 2xy=p, x^2-y^2=3^b y x^2+y^2=5^a. Notemos que (x+y)(x-y)=3^b, por lo que x+y y x-y son potencias de 3, y esto nos dice que su suma es múltiplo de 3, entonces 2x es múltiplo de 3, por lo que x es múltiplo de 3, y de ésto se sigue que y también, pero esto implica que x^2+y^2=5^a es múltiplo de 3, absurdo. Entonces, x-y=1.

Entonces, tenemos que x^2-y^2=3^b \Rightarrow x^2-(x-1)^2=2x-1=3^b. (1)

Además x^2+(x-1)^2 = 5^a \Rightarrow 2x^2-2x+1=5^a. Entonces 2\cdot 5^a -1 = 4x^2-4x+1=(2x-1)^2 (2).

De (1) y (2), tenemos que 2 \cdot 5^a - 1 = 3^{2b} \Rightarrow 2 \cdot 5^a = 9^b+1.

Módulo 10, es fácil ver que b es impar, por lo que podemos aplicar nuestro lema.

Notemos que 5 es un primo impar, y que el mayor r tal que 5^r \mid 9+1 es 1. Sea 5^d la mayor potencia de 5 que divide a b, entonces la mayor potencia que divide a 9^b+1 es 5^{d+1}, pero entonces 5^{d+1} = 5^a, por lo que d+1=a.

Si d > 0 tenemos que 2 \cdot 5^a = 9^b + 1 \geq 9^{5^d} + 1 > 10 \cdot 5^d = 2 \cdot 5^{d+1} = 2 \cdot 5^a, absurdo.

Entonces d=0, por lo que a=1, por lo que b=1. Además, teníamos que k=2a y que n=2b, así que k=2 y b=2, finalmente, se obtiene que p=2. Y hemos encontrado todas las soluciones.

Otro problema que sale con este lema es el siguiente, del selectivo de IMO del año 2000.

Spoiler: mostrar: Decimos que un número natural es alternado de orden n si sus últimas n cifras se alternan en paridad. Por ejemplo, son alternados de orden 4 los números 1092, 6721, 541092, 31092, y no son alternados de orden 4 los números 8072, 3418072, 7123345, 125.

Demostrar que para cada entero positivo n existe un entero positivo k tal que 5^k es un número alternado de orden n.

Y otro problema, de la IMO de ese mismo año:

Spoiler: mostrar: ¿Existe un entero positivo n con exactamente 2000 divisores primos, tal que n \mid 2^n+1?

Una recurrencia lineal de grado

k es una sucesión definida del siguiente modo:

Se define arbitrariamente para A_i (0\leq i\leq k-1)
Si n\geq k entonces \displaystyle A_n=\sum_{i=1}^{k} c_{k-i}A_{n-i} (los c_j son números fijos).

Por ejemplo Fibonacci es una recurrencia lineal de grado

2:

F_0=0
F_1=1
F_n=F_{n-1}+F_{n-2}

La idea es encontrar una forma general de resolver recurrencias lineales, o sea de encontrar una fórmula.

a) Hallar una fórmula para

F_0=0,

F_1=1,

F_n=2F_{n-1}-F_{n-2}.

b) Hallar una fórmula para

F_0=0,

F_1=1,

F_n=6F_{n-1}-9F_{n-2}.

OMA Foros

Ver último mensaje sin leer FOFO 14 Años

IMO telescopica del 79' (?)

Triangulo Acutangulo

Lema de Hensel (Lifting the exponent)

Recurrencias

Mas recurrencias