EGMO 2018 - P2

Avatar de Usuario
Violeta

OFO - Mención FOFO 7 años - Medalla Especial OFO - Medalla de Bronce FOFO 8 años - Mención Especial
Mensajes: 401
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 4
Ubicación: Puerto Rico

EGMO 2018 - P2

Mensaje sin leer por Violeta » Vie 13 Abr, 2018 9:40 pm

Sea $A = \{ 1+\frac{1}{k} : k = 1,2,3,\ldots \}$.

a) Probar que cada entero $x \geq 2$ se puede escribir como el producto de uno o mas elementos en $A$, no necesariamente distintos.

b) Para cada entero $x \geq 2$, sea $f(x)$ la cantidad minima de elementos de $A$, no necesariamente distintos, que se deben multiplicar para obtener $x$ como resultado.

Probar que existen infinitas parejas de enteros positivos $(x,y)$ tal que $f(xy) < f(x) + f(y)$
Para todo [math], existen [math] primos en sucesión aritmética.

Avatar de Usuario
Emerson Soriano

OFO - Mención OFO - Medalla de Oro OFO - Medalla de Plata OFO - Medalla de Bronce
Mensajes: 790
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 4

Re: EGMO 2018 - P2

Mensaje sin leer por Emerson Soriano » Vie 13 Abr, 2018 11:43 pm

Parte a)
Spoiler: mostrar
Sea $n\geqslant 2$ un número entero, entonces
$(1+\dfrac{1}{n})(1+\dfrac{1}{n+1})\cdots (1+\dfrac{1}{n^{2}-1})=\dfrac{n+1}{n}\cdot \dfrac{n+2}{n+1}\cdots\dfrac{n^{2}}{n^{2}-1}=n.$
Por lo tanto, $n$ se puede expresar como el producto de uno o más elementos de $A$, no necesariamente distintos.$\blacksquare $
Parte b)
Spoiler: mostrar
Comenzamos este inciso enunciando y demostrando los siguientes Lemas.

Lema 1. Si $a$ y $b$ son números enteros, con $a$, $b\geqslant 2$, entonces $f(ab)\leqslant f(a)+f(b)$.

Prueba. Como $a$ se puede expresar como el producto de $f(a)$ elementos de $A$ y $b$ se puede expresar como el producto de $f(b)$ elementos de $A$, no necesariamente distintos, entonces $ab$ se puede expresar como el producto de $f(a)+f(b)$ elementos de $A$, luego, como $f(ab)$ es el menor entero positivo tal que $ab$ se puede expresar como el producto de $f(ab)$ elementos de $A$, no necesariamente distintos, entonces $f(ab)\leqslant f(a)+f(b)$.$\blacksquare $


Lema 2. Si $k$ es un entero positivo, entonces $f(2^{k})=k$.

Prueba. Considere que $f(2^{k})=m$, entonces existen enteros positivos $a_1$, $a_2$, ... , $a_m$, no necesariamente distintos, tales que
$2^{k}=(1+\frac{1}{a_1})(1+\frac{1}{a_2})\cdots (1+\frac{1}{a_m}).$
Sabemos que $1+\dfrac{1}{a_i}\leqslant 2$ para todo $i=1$, $2$, ... , $m$. Luego, si $m<k$, entonces
$2^{k}=(1+\frac{1}{a_1})(1+\frac{1}{a_2})\cdots (1+\frac{1}{a_m})<2^{k},$
lo cual es una contradicción. Por lo tanto, $m\geqslant k$.

Por otro lado, notemos que
$2^{k}=\underset{k \:\: \text{factores}}{\underbrace{(1+\frac{1}{1})(1+\frac{1}{1})\cdots (1+\frac{1}{1})}}.$
Como $m$ es mínimo por definición, tenemos que $m\leqslant k$. Por lo tanto, $m=k$.$\blacksquare $


Lema 3. Si $k$ es un entero positivo, entonces $f(2^{k}+1)=k+1.$

Prueba. Sea $f(2^{k}+1)=t$, entonces existen enteros positivos $b_1$, $b_2$, ... , $b_t$, no necesariamente distintos, tales que
$2^{k}+1=(1+\frac{1}{b_1})(1+\frac{1}{b_2})\cdots (1+\frac{1}{b_t}).$
Es claro que $1+\dfrac{1}{a_i}\leqslant 2$ para todo $i=1$, $2$, ... , $m$. Luego, si $t\leqslant k$, entonces
$2^{k}+1=(1+\frac{1}{b_1})(1+\frac{1}{b_2})\cdots (1+\frac{1}{b_t})\leqslant 2^{k},$
lo cual es una contradicción. Por lo tanto, $t\geqslant k+1$.

Observemos que $2^{k}+1$ se puede expresar como el producto de $k+1$ elementos de $A$, no necesariamente distintos:
$2^{k}+1=(1+\frac{1}{2^{k}})\cdot \underset{k \:\: \text{factores}}{\underbrace{(1+\frac{1}{1})(1+\frac{1}{1})\cdots (1+\frac{1}{1})}}.$
Como $t$ es mínimo por definición, tenemos que $t\leqslant k+1$. Por lo tanto, $t=k+1$.$\blacksquare $


Lema 4. Si $a$ y $b$ son enteros positivos, entonces $f(2^{a}(2^{b}+1))=a+b+1$.

Prueba. Usando los Lemas $1$, $2$ y $3$, tenemos que
$f(2^{a}(2^{b}+1))\leqslant f(2^{a})+f(2^{b}+1)=a+b+1.$
Si $f(2^{a}(2^{b}+1))\leqslant a+b$, entonces $2^{a}(2^{b}+1)$ se podría expresar como el producto de a lo sumo $a+b$ elementos de $A$, no necesariamente distintos, pero como cada uno de esos factores es menor o igual que $2$ se tendría que dicho producto es menor o igual que $2^{a+b}$, pero esto implicaría que $2^{a}(2^{b}+1)\leqslant 2^{a+b}$, lo cual es una contradicción. Por lo tanto, $2^{a}(2^{b}+1)=a+b+1$.$\blacksquare $


Con respecto al problema, vamos a calcular el valor de $f(11)$. En efecto, claramente $f(11)\geqslant 4$, pues si $f(11)\leqslant 3$, entonces $11$ se podría expresar como el producto de a lo sumo tres elementos de $A$, no necesariamente distintos, pero como cada uno de esos factores es menor o igual que $2$ se tendría que $11$ es menor o igual que $8$, lo cual es una contradicción. Además,
$11=(1+\frac{1}{10})(1+\frac{1}{4})(1+\frac{1}{1})(1+\frac{1}{1})(1+\frac{1}{1}),$
lo cual significa que $f(11)\leqslant 5$. Así, tenemos que $f(11)=4$ o $5$.

Supongamos que $f(11)=4$, entonces existen enteros positivos $a\leqslant b\leqslant c\leqslant d$ tales que
$11=(1+\frac{1}{a})(1+\frac{1}{b})(1+\frac{1}{c})(1+\frac{1}{d}).$
Si $d=1$, entonces $a=b=c=d=1$, pero entonces se tendría que $11=16$, lo cual es absurdo. Por lo tanto, $d\geqslant 2$.

Notemos que
$1+\frac{1}{d}=\frac{11}{(1+\dfrac{1}{a})(1+\dfrac{1}{b})(1+\dfrac{1}{c})}\geqslant \frac{11}{8}.$
Así, $1+\dfrac{1}{d}\geqslant \dfrac{11}{8}$, concluyendo que $d\leqslant 2$. Por lo tanto, $d=2$.

Si $c=2$, entonces se tendría que
$11=(1+\frac{1}{a})(1+\frac{1}{b})(1+\frac{1}{c})(1+\frac{1}{d})\leqslant 2\cdot 2\cdot \frac{3}{2}\cdot \frac{3}{2}=9,$
lo cual es una contradicción. Por lo tanto, $a=b=c=1$ y $d=2$, pero entonces
$11=(1+\frac{1}{1})(1+\frac{1}{1})(1+\frac{1}{1})(1+\frac{1}{2})=12,$
lo cual también es una contradicción. Así, concluimos que $f(11)=5$.


Ahora, para cada entero positivo $n$, tomemos la pareja $(x_n, y_n)=(3\cdot 2^{n}, 11)$. Notemos que
$f(x_n)+f(y_n)=f(3\cdot 2^{n})+f(11)=f(2^{n}(2^{1}+1))+f(11)=(n+2)+5=n+7.$
También notemos que
$f(x_ny_n)=f(3\cdot 2^{n}\cdot 11)=f(2^{n}\cdot 33)=f(2^{n}(2^{5}+1))=n+6.$
Por lo tanto, $f(x_ny_n)<f(x_n)+f(y_n)$. Como $n$ varía en todos los enteros positivos, concluimos que hay infinitas parejas que satisfacen lo pedido.


Responder