jueves, 27 de mayo de 2010

Pista para el Problema del Dia 23 de mayo

Irving y Diego han solucionado el inciso a, pero nadie ha hecho el inciso b), así que les daré una pista para una de las soluciones, una solución que creo les ayudará en cuestión de una buena técnica para la IMO (y la ibero).

Supongamos que tenemos un triángulo equilátero. Sin pérdida de generalidad un vértice está en el círculo con centro en el origen. Ahora, digamos que otro vértice está en el círculo con centro en(a,b) donde a y b son enteros no negativos (sin pérdida de generalidad de nuevo).
Ahora, supongamos que los vértices son exactamente esos puntos con coordenadas enteras. Calculen donde caería el tercer vértice (hay dos opciones, escojan su favorita de las dos). Ahora demuestren que si los vértices no están en puntos con coordenadas enteras, el tercer vértice quedara muy cerca de ese punto.
Con esta información, pueden saber que tan cerca tiene que estar ese punto de un punto con coordenadas enteras. Ahora pueden usar fracciones continuas y ponerle una cota al asunto.

2 comentarios:

IrvinG dijo...

Hola,
Yo no estoy seguro de saber cómo usar fracciones continuas para lo de la cota, de hecho nunca he usado fracciones continuas, para ningún problema. Podrías poner algunos ejemplos sencillos en los que podamos aplicar fracciones continuas? Para más o menos ver cómo es el método.

Quique12 dijo...

Las fracciones continuas te dan una manera de aproximar irracionales.

Por ejemplo, encontremos la fracción continua de la raíz cuadrada de 2.

Para facilitar notación, escribire a = raíz de 2.
Nota que raíz de 2 es mayor a 1 y menor a 2. Es decir 1 < a < 2.

Entonces a = 1 + a-1 = 1 + (a-1)(a+1)/(a+1) = 1 + (a^2-1)/(a+1) = 1 + 1/(a+1) = 1 + 1/(2 + a-1) = 1 + 1/(2 + 1/(2 + ...)

Entonces encontramos la fracción continua de a.
Ahora si te paras en cualquier momento, encuentras fracciones aproximadas a 2. Llamemoslas p_k/q_k.

p_1/q_1 = 1
p_2/q_2 = 1 + 1/2 = 3/2
p_3/q_3 = 1 + 1/(2+1/2) = 7/5
p_4/q_4 = 1 + 1/(2+1/(2+1/2)) = 17/12
p_5/1_5 = 41/29
p_6/q_6 = 99/70

Y así te la llevas. A estas fracciones las llamamos "convergentes de la fracción continua de a".

Ahora mencionaré un par de teoremas poderosos:

Teorema 1: La siguiente desigualdad se cumple:
|a - p_k/q_k| < 1/(q_k q_{k+1})
|a - p_k/q_k| > 1/(q_k (q_k + q_{k+1}))

En particular |a - p_k/q_k| < 1/q_k^2.

Teorema 2: Si x es un número real y |x - p/q| < 1/(2q^2), entonces p/q es una convergente de la fracción continua de x.


Nota que puedes usar estos dos teoremas para acotar cuando tienes que k*a está cerca de un entero (para k entero).
Ejemplo si sabemos que |k*a - z| < 1/100 para algún entero z, entonces |a - z/k| < 1/k*100.
Si k es de tal manera que 1/(k*100) < 1/(2 k^2), es decir k < 50, entonces sabemos que z/k es una convergente de a. Y pues puedes usar esto para decir, el máximo k tal que z/k es convergente y k < 50 es 41/29. En este caso |a - 41/29| > 1/(q_k*(q_k+q_{k+1}) = 1/(29*(29+70)) = 1/(29*99).
Por lo tanto |29a - 41| > 1/99. Lo cual nos lleva a una contradicción (porque habíamos asumido que |k*a-z| < 1/100 con k < 50. Pero 1/99 > 1/100 así que tenemos una contradicción y concluimos que k>=50 es necesario para que |k*a - z| < 1/100.

Espero esto te haya ayudado, si está confusa la notación, lo puedo escribir en latex más tarde.

Publicar un comentario