Torneo de fronteras 1997- Nivel 2 Problema 3

bruno
Mensajes: 228
Registrado: Vie 17 Dic, 2010 12:50 am

Torneo de fronteras 1997- Nivel 2 Problema 3

Mensaje sin leer por bruno »

Se consideran los puntos del plano [math] con sus dos coordenadas enteras. Diremos que [math] es visible desde [math] si el segmento [math] no contiene otros puntos de coordenadas enteras además de [math] y [math].
Determinar cuántos puntos [math] de coordenadas enteras de la forma [math] con [math] son visibles desde [math].
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Torneo de fronteras 1997- Nivel 2 Problema 3

Mensaje sin leer por Ivan »

La idea es notar que [math] es visible desde [math] si y solamente si la fracción [math] es irreducible.

Entonces buscamos los [math] que son coprimos con [math].

La cantidad de números coprimos con [math] menores o iguales que [math] es [math].

Estamos contando de más el [math].

Entonces la respuesta es [math].
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Avatar de Usuario
Martín Vacas Vignolo
Mensajes: 404
Registrado: Mié 15 Dic, 2010 6:57 pm
Nivel: Exolímpico

Re: Torneo de fronteras 1997- Nivel 2 Problema 3

Mensaje sin leer por Martín Vacas Vignolo »

Spoiler: mostrar
Lema: [math].

Demostración:
Sea [math] la proyección de [math] sobre el eje [math]. Entonces el triángulo [math] es rectángulo en [math].
[math]: Si [math], sean [math] y [math]. Entonces el triángulo de vértices [math], [math] y [math] es semejante al triángulo [math] y tiene vértices de coordenadas enteras, o sea que [math] "no dejaría ver" a [math].
[math]: Si [math] no es visible, existe un punto [math] que lo tapa, hacemos la proyección sobre el eje [math] y tenemos un triángulo semejante, por lo tanto existe la constante que necesitamos.

Entonces los que andan son los coprimos con [math].
[math]
Responder