viernes, 23 de marzo de 2012
Problema del dia: Viernes
Sean $a_k< a_{k-1}<\cdots< a_1< n$ enteros positivos tales que $m.c.m(a_i,a_j)\le n$ para todo $i$, $j$ entre $1$ y $k$. Demuestre que $ia_i\le n$.
Suscribirse a:
Comentarios de la entrada (Atom)
6 comentarios:
Ésto es un problema de un selectivo del año pasado, ¿no?
Creo que el del año pasado de Guanajutato era que para todo $i, j$ con $i\neq j$ se tenía que $a_{i}-a_{j}$ dividía a $a_{i}$, y había que probar que se cumplía $ia_{i}\leq ja_{j}$ o algo así.
Esta interesante el problema, aunque algo raro... algún hint?
Tenemos que $a_{i}$ para $i\leq k$ se puede escribir como $a_{i}=\frac{x_{i}a_{k}}{y_{i}}$ con $(x_{i},y_{i})=1$, $y_{i}\mid a_{k}$. Entonces, si $a_{k}=y_{i}l$, $[a_{i},a_{x}]=[\frac{x_{i}y_{i}l}{y_{i}},y_{i}l]$ $=[x_{i}l,y_{i}l]=l[x_{i},y_{i}]$ $=lx_{i}y_{i}$ (pues $(x_{i},y_{i})=1$) $=x_{i}a_{k}\leq n$.
Supongamos que $ka_{k}>n$. Entonces, $x_{i}a_{k}\leq n<ka_{k}\Rightarrow x_{i}<k$ $\Rightarrow x_{i}\leq k-1$. Además, como $a_{i}$ es mayor que $a_{k}$ para $i\leq k$, $a_{k}<\frac{x_{i}a_{k}}{y_{i}}\Rightarrow y_{i}\leq x_{i}-1$. Es claro que para $x_{i}$ fijo, el menor valor posible de $a_{i}$ es $\frac{x_{i}}{x_{i}-1}$, y entre todos los números de la forma $\frac{x_{i}}{x_{i}-1}$ con $x_{i}\leq k-1$, es evidente que el mínimo es $\frac{k-1}{k-2}$, pues $\frac{k-1}{k-2}\leq \frac{x_{i}}{x_{i}-1}$ $\Leftrightarrow (k-1)(x_{i}-1)\leq (k-2)(x_{i})$ $\Leftrightarrow x\leq k-1$, que es cierto. Entonces, $a_{i}\geq \frac{(k-1)a_{k}}{k-2}$ para $i\leq k$, en particular $a_{k-1}=\geq \frac{(k-1)a_{k}}{k-2}$ $\Rightarrow \frac{a_{k-1}}{a_{k}\geq \frac{k-1}{k-2}\geq \frac{k}{k-1}}$ $\Rightarrow ka_{k}\leq (k-1)a_{k-1}$. Siguiendo un argumento inductivo, obtenemos que $ka_{k}\leq (k-1)a_{k-1}\leq ...\leq 2a_{2}\leq a_{1}<n$, que contradice la suposición de que $n<ka_{k}$. Entonces, $ka_{k}\leq n$.
Me equivoqué en una parte del latex, ésta es la versión correcta:
Tenemos que $a_{i}$ para $i\leq k$ se puede escribir como $a_{i}=\frac{x_{i}a_{k}}{y_{i}}$ con $(x_{i},y_{i})=1$, $y_{i}\mid a_{k}$. Entonces, si $a_{k}=y_{i}l$, $[a_{i},a_{x}]=[\frac{x_{i}y_{i}l}{y_{i}},y_{i}l]$ $=[x_{i}l,y_{i}l]=l[x_{i},y_{i}]$ $=lx_{i}y_{i}$ (pues $(x_{i},y_{i})=1$) $=x_{i}a_{k}\leq n$.
Supongamos que $ka_{k}>n$. Entonces, $x_{i}a_{k}\leq n<ka_{k}\Rightarrow x_{i}<k$ $\Rightarrow x_{i}\leq k-1$. Además, como $a_{i}$ es mayor que $a_{k}$ para $i\leq k$, $a_{k}<\frac{x_{i}a_{k}}{y_{i}}\Rightarrow y_{i}\leq x_{i}-1$. Es claro que para $x_{i}$ fijo, el menor valor posible de $a_{i}$ es $\frac{x_{i}}{x_{i}-1}$, y entre todos los números de la forma $\frac{x_{i}}{x_{i}-1}$ con $x_{i}\leq k-1$, es evidente que el mínimo es $\frac{k-1}{k-2}$, pues $\frac{k-1}{k-2}\leq \frac{x_{i}}{x_{i}-1}$ $\Leftrightarrow (k-1)(x_{i}-1)\leq (k-2)(x_{i})$ $\Leftrightarrow x\leq k-1$, que es cierto. Entonces, $a_{i}\geq \frac{(k-1)a_{k}}{k-2}$ para $i\leq k$, en particular $a_{k-1}=\geq \frac{(k-1)a_{k}}{k-2}$ $\Rightarrow \frac{a_{k-1}}{a_{k}}\geq \frac{k-1}{k-2}\geq \frac{k}{k-1}}$ $\Rightarrow ka_{k}\leq (k-1)a_{k-1}$. Siguiendo un argumento inductivo, obtenemos que $ka_{k}\leq (k-1)a_{k-1}\leq ...\leq 2a_{2}\leq a_{1}<n$, que contradice la suposición de que $n<ka_{k}$. Entonces, $ka_{k}\leq n$.
Pues el hint es mas o menos la idea de enrique, hacer un argumento inductivo sobre "k" y usar la definicion de minimo comun multiplo.
Publicar un comentario