Suma interesante

Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021
Mensajes: 98
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 7
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Suma interesante

Mensaje sin leer por Fedex »

Para un entero positivo $n$, sea $s(n)$ la suma de los dígitos de $n$ en representación binaria.
Encontrar el valor de:$$s(1)+s(2)+s(3)+\ldots +s\left (2^k\right )$$Para todo entero positivo $k$.
Última edición por Fedex el Sab 15 Ago, 2020 6:44 pm, editado 1 vez en total.
1  
$\frac{9}{1^2} \binom{20}{18}$

Avatar de Usuario
¿hola?

OFO - Mención-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber OFO - Jurado-OFO 2021
Mensajes: 154
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 7
Nivel: Exolímpico
Contactar:

Re: Suma interesante

Mensaje sin leer por ¿hola? »

Spoiler: mostrar
Los números menores a $2^k$ tendrán $k$ dígitos (si tienen menos rellenamos con $0$ a la izquierda hasta que tengan $k$), es fácil ver que para cualquier posición habrá $2^{k-1}$ números con un $1$ en esa posición y $2^{k-1}$ números con un $0$, por lo que la suma de las sumas de dígitos sera $1*2^{k-1}*k+0*2^{k-1}*k$ mas $s(2^k)=1$, o sea $2^{k-1}k+1$ para todo $k$.
2  
Yes, he who

Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1015
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Re: Suma interesante

Mensaje sin leer por Matías V5 »

Fedex escribió:
Sab 15 Ago, 2020 1:25 pm
Para un entero positivo $n$, sea $s(n)$ la suma de los dígitos de $n$ en representación binaria.
Encontrar el valor de:$$s(1)+s(2)+\ldots +s\left (2^k\right )$$Para todo entero positivo $k$.
Si sólo ponés esos términos de la suma no se entiende si es todos los naturales hasta $2^k$ o sólo las potencias de $2$!
(Claro que si fuera el segundo caso sería bastante aburrido...)
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=SoRiOoqao5Y

Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021
Mensajes: 98
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 7
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Suma interesante

Mensaje sin leer por Fedex »

Corregido y dejo una solución .
Spoiler: mostrar
Llamamos $S_k = s(1) + ... + s(2^k)$
Para fabricar una relacion entre $S_k$ y $S_{k+1}$ usamos estas $2$ cosas:
- $s(2^a) = 1$
- Para todo $x < 2^a$ tenemos que $s(2^a+x) = s(x) + 1$
Entonces:
$S_{k+1} = \sum_{i=1}^{2^{k+1}} s(i) = \sum_{i=1}^{2^k} s(i) + \sum_{i=1}^{2^k-1}s(2^k+i) \; + \; s(2^{k+1}) = S_k + \sum_{i=1}^{2^k-1}[s(i)+1] \; + \; 1 = S_k + S_k - s(2^k) + 2^k - 1 +1 = 2S_k + 2^k - 1$
Esto nos queda definido como:
$S_1= s(1) + s(2) = 2$
$S_{k+1} = 2S_k + 2^k - 1$
Después de jugar un poco conjeturamos que $S_k = 2^{k-1}k +1$
Y lo vamos a probar por inducción:
Para el caso base $k=1$ y $S_1 = 2^{0}1+1 = 2$ cierto.
Luego si $S_k = 2^{k-1}k +1$ entonces $S_{k+1} = 2S_k + 2^k - 1 = 2^{k}k + 2 + 2^k - 1 = 2^{k}(k+1) + 1$
Concluimos con el paso inductivo y estamos. :D
Luego $s(1) + ... + s(2^k) = 2^{k-1}k + 1$
2  
$\frac{9}{1^2} \binom{20}{18}$

Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021
Mensajes: 222
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 6
Nivel: 3

Re: Suma interesante

Mensaje sin leer por Sandy »

Spoiler: mostrar
Hagamos algo más divertido y emparejemos cada número con su "opuesto". Está claro que queremos la suma de los dígitos de los números con $k$ o menos dígitos $+s\left (2^k\right )$.
Digamos que cada número con $k$ dígitos o menos en binario tiene $k$ dígitos (rellenando con $0$s a la izquierda).

Sea $n$ un número y $n'$ ese número tras intercambiar los $0$ por $1$ y los $1$ por $0$.
Es fácil ver que $n+n'=2^k-1=\underbrace{11\ldots 11}_{k}$ y $s(n)+s(n')=s(n+n')$, ya que al sumarlos no hay ningún acarreo de dígitos (donde $n$ tiene $1$, $n'$ tiene $0$ y viceversa).
Sumando también el $0$, ya que $s(0)=0$ tenemos los números del intervalo $\left [0, 2^k-1\right ]$, en $2^{k-1}$ parejas tales que $s(n)+s(n')=k$.
Luego $\sum \limits _{i=1}^{2^k} s(i)=k2^{k-1}+s\left (2^k\right )=k2^{k-1}+1$.
1  
$u=tan\left(\frac{x}{2}\right)$
$\frac{2}{1+u^2}du=dx$

Responder