Uno muy bonito de máximo entero.

Avatar de Usuario
Emerson Soriano

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

Uno muy bonito de máximo entero.

Mensaje sin leer por Emerson Soriano » Jue 11 Ago, 2016 6:11 pm

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

Matías

OFO - Medalla de Bronce FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
Mensajes: 95
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 4
Nivel: 2

Re: Uno muy bonito de máximo entero.

Mensaje sin leer por Matías » Dom 14 Ene, 2018 3:15 am

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