Uno muy bonito de máximo entero.

Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
OFO - Medalla de Plata-OFO 2022
Mensajes: 826
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 6

Uno muy bonito de máximo entero.

Mensaje sin leer por Emerson Soriano »

Sean [math], [math] y [math] enteros positivos arbitrarios. Probar que
[math]
Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: Uno muy bonito de máximo entero.

Mensaje sin leer por Matías »

Spoiler: mostrar
Vamos a demostrarlo por inducción en función de $n$:

Si $n=1$ tenemos que probar que $min(x,m)=\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,1)$
Si $x\geq m$ tenemos que $min(x,m)=m$ y que $min(\lfloor\frac{x}{i}\rfloor,1)=1$ $\forall 1\leq i\leq m$, por lo tanto $\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,1)=m$
Si $x<m$ tenemos que $min(x,m)=x$ y que $min(\lfloor\frac{x}{i}\rfloor,1)=1$ $\forall 1\leq i\leq x$ y $min(\lfloor\frac{x}{i}\rfloor,1)=0$ $\forall x<i\leq m$ así que $\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,1)=x$

Ahora bien, sabiendo que $\sum_{i=1}^{n} min(\lfloor\frac{x}{i}\rfloor,m)=\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,n)$ para cierto $n$, vamos a demostrar que para $n+1$ también se cumple que $\sum_{i=1}^{n+1} min(\lfloor\frac{x}{i}\rfloor,m)=\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,n+1)$
Como $\sum_{i=1}^{n+1} min(\lfloor\frac{x}{i}\rfloor,m)=\sum_{i=1}^{n} min(\lfloor\frac{x}{i}\rfloor,m)+min(\lfloor\frac{x}{n+1}\rfloor,m)=\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,n)+min(\lfloor\frac{x}{n+1}\rfloor,m)$ debemos probar que $\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,n+1)-\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,n)=min(\lfloor\frac{x}{n+1}\rfloor,m)$
Tenemos que $min(\lfloor\frac{x}{i}\rfloor,n+1)-min(\lfloor\frac{x}{i}\rfloor,n)=1$ si $\frac{x}{i}\geq n+1$ y $min(\lfloor\frac{x}{i}\rfloor,n+1)-min(\lfloor\frac{x}{i}\rfloor,n)=0$ si $\frac{x}{i}<n+1$
Si $\frac{x}{n+1}\geq m$ tenemos que $min(\lfloor\frac{x}{n+1}\rfloor,m)=m$ y como $\frac{x}{m}\geq n+1$ entonces $\frac{x}{i}\geq n+1$ $\forall 1\leq i\leq m$, por lo tanto $\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,n+1)-\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,n)=m$
Si $\frac{x}{n+1}<m$ tenemos que $min(\lfloor\frac{x}{n+1}\rfloor,m)=\lfloor\frac{x}{n+1}\rfloor$ y como $\frac{x}{\lfloor\frac{x}{n+1}\rfloor}\geq\frac{x}{\frac{x}{n+1}}=n+1$ y $\frac{x}{\lfloor\frac{x}{n+1}\rfloor+1}<\frac{x}{\frac{x}{n+1}}=n+1$ entonces $min(\lfloor\frac{x}{i}\rfloor,n+1)-min(\lfloor\frac{x}{i}\rfloor,n)=1$ $\forall 1\leq i\leq \lfloor\frac{x}{n+1}\rfloor$ y $min(\lfloor\frac{x}{i}\rfloor,n+1)-min(\lfloor\frac{x}{i}\rfloor,n)=0$ $\forall \lfloor\frac{x}{n+1}\rfloor<i\leq m$ por lo tanto $\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,n+1)-\sum_{i=1}^{m} min(\lfloor\frac{x}{i}\rfloor,n)=\lfloor\frac{x}{n+1}\rfloor$
Responder