Olimpíadas

Mensagem não lida por **Cássio** » 20 Mai 2012, 01:24

Calcule

[tex3]\sum_{n=1}^{1997}\lfloor\sqrt{n}\rfloor[/tex3]

Mensagem não lida por **poti** » 20 Mai 2012, 12:05

Oi Cássio.

[tex3]\lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor = 3.1[/tex3]

[tex3]\lfloor \sqrt{4} \rfloor + \lfloor \sqrt{5} \rfloor + \lfloor \sqrt{6} \rfloor + \lfloor \sqrt{7} \rfloor + \lfloor \sqrt{8} \rfloor = 5.2[/tex3]

[tex3]\lfloor \sqrt{9} \rfloor + \lfloor \sqrt{10} \rfloor + \lfloor \sqrt{11} \rfloor + \lfloor \sqrt{12} \rfloor + \lfloor \sqrt{13} \rfloor + \lfloor \sqrt{14} \rfloor + \lfloor \sqrt{15} \rfloor + \lfloor \sqrt{15} \rfloor = 7.3[/tex3]

Deu pra pegar a jogada ?

O que você quer é [tex3]\sum_{k=1}^{1997} k(2k + 1)[/tex3] . Desenvolvendo:

[tex3]\sum_{k=1}^{1997} (2k^2 + k) = 2\sum_{k=1}^{1997} k^2 + \sum_{k=1}^{1997} k[/tex3]

[tex3]2.\frac{1997.1998.3995}{6} + \frac{1997.1998}{2}[/tex3]

[tex3]5315352993[/tex3]

É isso ?

Grande Abraço!

Olá Poti...

Pela tua solução você está dizendo que [tex3]\lfloor \sqrt{n} \rfloor =n(2n+1)[/tex3] .

Veja que para [tex3]n=1[/tex3]
[tex3]\lfloor \sqrt{1} \rfloor =1\cdot (2\cdot 1+1)[/tex3]
[tex3]1\neq 3[/tex3]

Resposta

[tex3]\text{Gabarito:}\, 58542[/tex3]

Grande abraço meu amigo.

Mensagem não lida por **poti** » 20 Mai 2012, 13:50

Tem toda razão. Na verdade o somatório é esse, mas o índice não vai até 1997.

[tex3]44^2 = 1936[/tex3] é o menor quadrado perfeito antes de [tex3]1997[/tex3] . Veja que o número de termos aumenta como uma PA de [tex3]r = 2[/tex3] e [tex3]a_1 = 3[/tex3] . O último termo a ser somado é sempre o anterior ao próximo quadrado perfeito.

Sendo assim:

[tex3]a_{43} = 3 + (43 - 1).2[/tex3]
[tex3]\boxed{a_{43} = 87}[/tex3]

Isso significa que vamos somar 87 termos na última soma antes do [tex3]44^2[/tex3] . Veja também que os termos a serem somados segue o que eu já tinha falado.

[tex3]43 = 2n+1[/tex3]
[tex3]\boxed{n = 21}[/tex3]

Então temos que somar [tex3]\boxed{\sum_{k=1}^{21} k.(2k+1)} + 22.(1997 - 1936)[/tex3] :

[tex3]\frac{2.21.22.43}{6} + \frac{21.22}{2} + 22.61[/tex3]

[tex3]6622 + 231 + 1342 = \boxed{8195}[/tex3]

Onde eu errei agora ?

Realmente Poti, o somatório está correto o problema está nos limites.

[tex3]\lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor = 3.1[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]\lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor = 3.1[/tex3]

[tex3]\lfloor \sqrt{4} \rfloor + \lfloor \sqrt{5} \rfloor + \lfloor \sqrt{6} \rfloor + \lfloor \sqrt{7} \rfloor + \lfloor \sqrt{8} \rfloor = 5.2[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]\lfloor \sqrt{4} \rfloor + \lfloor \sqrt{5} \rfloor + \lfloor \sqrt{6} \rfloor + \lfloor \sqrt{7} \rfloor + \lfloor \sqrt{8} \rfloor = 5.2[/tex3]

[tex3]\lfloor \sqrt{9} \rfloor + \lfloor \sqrt{10} \rfloor + \lfloor \sqrt{11} \rfloor + \lfloor \sqrt{12} \rfloor + \lfloor \sqrt{13} \rfloor + \lfloor \sqrt{14} \rfloor + \lfloor \sqrt{15} \rfloor + \lfloor \sqrt{15} \rfloor = 7.3[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]\lfloor \sqrt{9} \rfloor + \lfloor \sqrt{10} \rfloor + \lfloor \sqrt{11} \rfloor + \lfloor \sqrt{12} \rfloor + \lfloor \sqrt{13} \rfloor + \lfloor \sqrt{14} \rfloor + \lfloor \sqrt{15} \rfloor + \lfloor \sqrt{15} \rfloor = 7.3[/tex3]

Continuando teríamos,
[tex3]\vdots[/tex3]
[tex3]\left\lfloor \sqrt{\underbrace{1849}_{43^2}}\right \rfloor + \lfloor \sqrt{1850} \rfloor + \cdots +\lfloor \sqrt{1935} \rfloor[/tex3]
[tex3]\left\lfloor \sqrt{\underbrace{1936}_{44^2}}\right \rfloor + \lfloor \sqrt{1937} \rfloor + \cdots +\lfloor \sqrt{1997} \rfloor[/tex3]

Percebe que o primeiro termo de cada ssequência é formado por um quadrado perfeito e o valor da soma de cada sequência e formado pelo produto do quadrado perfeito pela quantidade de ternos da sequência.

Sendo assim, a soma desejada vale
[tex3]1\cdot 3+2\cdot 5+3\cdot 7+\cdots +x[/tex3]

Onde [tex3]x[/tex3] vale [tex3]44[/tex3] vezes o números de termos da última sequência.
[tex3]1977-1936 +1=62[/tex3] termos

Assim temos,
[tex3]S=1\cdot 3+2\cdot 5+3\cdot 7+\cdots +\underbrace{44\cdot 62}_{2728}=2728+\sum_{k=1}^{43}k(2k+1)[/tex3]
[tex3]S=2728+2\cdot \sum_{k=1}^{43}k^2 +\sum_{k=1}^{43}k[/tex3]
[tex3]S=2728+\frac{2\cdot 43\cdot 44\cdot 87}{6} + \frac{43\cdot 44}{2}[/tex3]
[tex3]S=2728+54868+946[/tex3]
[tex3]\boxed{S=58542}[/tex3]

Abraço.

Mensagem não lida por **poti** » 24 Mai 2012, 23:03

Folheando o livro de Matemática Concreta do Knuth eu achei essa soma.

[tex3]\sum_{0 \leq k < n}\lfloor \sqrt{k} \rfloor = na - \frac{a^3}{3} - \frac{a^2}{2} - \frac{a}{6}[/tex3] , onde [tex3]a = \lfloor \sqrt{n} \rfloor[/tex3] .

(Veja que a soma é [tex3]< n[/tex3] , então pegamos um a mais pra ficar igual a soma do exercício)
Tomando [tex3]n = 1998[/tex3] , ficamos com [tex3]a = 44[/tex3] .

[tex3]\sum_{0 \leq k < n}\lfloor \sqrt{k} \rfloor = 1998.44 - \frac{44^3}{3} - \frac{44^2}{2} - \frac{44}{6}[/tex3]

[tex3]\sum_{0 \leq k < n}\lfloor \sqrt{k} \rfloor = \boxed{58542}[/tex3]

Se alguém ainda se interessar pelo exercício, posso tentar demonstrar essa fórmula aqui.

Grande Abraço!

Mensagem não lida por **Cássio** » 26 Mai 2012, 14:30

Seria interessante. Demonstre, por favor.

Mensagem não lida por **Cássio** » 27 Ago 2012, 15:23

Estudando a função piso, notei como encontrar uma fórmula para [tex3]\displaystyle\sum_{k=1}^{n}\lfloor\sqrt k\rfloor.[/tex3]

Primeiro, notemos que [tex3]\lfloor\sqrt k\rfloor=t,\ t\in\mathbb{Z_+^*},[/tex3] se [tex3]t^2\le k<(t+1)^2.[/tex3]

Então, vamos contar quantos inteiros positivos [tex3]k[/tex3] têm [tex3]\lfloor \sqrt k\rfloor=t.[/tex3] A quantidade que queremos é a quantidade de inteiros entre [tex3]t^2[/tex3] e [tex3](t+1)^2,[/tex3] incluindo [tex3]t^2[/tex3] e excluindo [tex3](t+1)^2.[/tex3] Essa contagem é fácil de fazer. Seja [tex3]Q_t[/tex3] a quantidade de inteiros positivos [tex3]k[/tex3] tais que [tex3]\lfloor \sqrt k\rfloor=t.[/tex3] Então temos:

[tex3]Q_t=[(t+1)^2-1]-t^2+1=2t+1.[/tex3]

Ou seja, sempre existem [tex3]2t+1[/tex3] inteiros positivos que têm o piso igual a [tex3]t.[/tex3] Mas se o valor [tex3]t[/tex3] está contado [tex3]2t+1[/tex3] vezes, então a soma de todos os pisos iguais a [tex3]t[/tex3] é [tex3]t\cdot Q_t=t(2t+1).[/tex3]

Vamos procurar o quadrado perfeito mais próximo de [tex3]n.[/tex3] Mas é fácil notar que este quadrado é [tex3]\left(\lfloor \sqrt n\rfloor\right)^2.[/tex3] Vamos também dividir o raciocínio:

1 - Procuraremos calcular a soma de todos os pisos até [tex3]\lfloor \sqrt n\rfloor -1.[/tex3] Por definição, isto é [tex3]\displaystyle\sum_{j=1}^{{\lfloor \sqrt n\rfloor -1}}Q_j.[/tex3]

2 - Procurar quantos números têm o piso igual a [tex3]\lfloor \sqrt n\rfloor.[/tex3] Mas isto é fácil. Basta observar que o primeiro número que tem piso igual a [tex3]\lfloor \sqrt n\rfloor[/tex3] é [tex3]\left(\lfloor \sqrt n\rfloor\right)^2.[/tex3] Então a quantidade de números que queremos é [tex3]n-\left(\lfloor \sqrt n\rfloor\right)^2+1.[/tex3] Logo, a soma de todos esses pisos vale [tex3]\lfloor \sqrt n\rfloor \cdot (n-\left(\lfloor \sqrt n\rfloor\right)^2+1).[/tex3]

Vamos voltar à parte 1. Queremos calcular [tex3]\displaystyle\sum_{j=1}^{{\lfloor \sqrt n\rfloor -1}}Q_j.[/tex3] Vimos que [tex3]Q_j=j(2j+1).[/tex3] Como [tex3]\lfloor \sqrt n\rfloor -1\in\mathbb{Z},[/tex3] vamos chamá-lo de [tex3]m[/tex3] e tentar encontrar uma fórmula para [tex3]\displaystyle\sum_{j=1}^{m}Q_j=\displaystyle\sum_{j=1}^{m}j(2j+1).[/tex3] (Não vou mostrar o método para encontrar a fórmula desta soma porque só vai deixar a solução maior do que já está, e bem tediosa. Mas posso mostrar em outro tópico, caso alguém se interesse.)

A fórmula para [tex3]\displaystyle\sum_{j=1}^{m}j(2j+1)[/tex3] é [tex3]\displaystyle\sum_{j=1}^{m}j(2j+1)=\dfrac{m(m+1)(4m+5)}{6}[/tex3] (Já a demonstração desta fórmula é facilmente feita por Indução finita sobre [tex3]m.)[/tex3]
Ou seja:
[tex3]\displaystyle\sum_{j=1}^{{\lfloor \sqrt n\rfloor -1}}Q_j=\dfrac{(\lfloor \sqrt n\rfloor -1)(\lfloor \sqrt n\rfloor)(4\lfloor \sqrt n\rfloor +1)}{6}[/tex3]

Então, agora temos toda a nossa soma em função de [tex3]n[/tex3] e [tex3]\lfloor \sqrt n\rfloor:[/tex3]

[tex3]\boxed{\boxed{\displaystyle\sum_{k=1}^{n}\lfloor\sqrt k\rfloor=\dfrac{(\lfloor \sqrt n\rfloor -1)(\lfloor \sqrt n\rfloor)(4\lfloor \sqrt n\rfloor +1)}{6}+\lfloor \sqrt n\rfloor \cdot (n-\left(\lfloor \sqrt n\rfloor\right)^2+1)}}[/tex3]

Olimpíadas ⇒ (Mercosul - 1997) Função Piso II Tópico resolvido

(Mercosul - 1997) Função Piso II

Re: (Mercosul - 1997) Função Piso II

Re: (Mercosul - 1997) Função Piso II

Re: (Mercosul - 1997) Função Piso II

Re: (Mercosul - 1997) Função Piso II

Re: (Mercosul - 1997) Função Piso II

Re: (Mercosul - 1997) Função Piso II

Re: (Mercosul - 1997) Função Piso II

Crie uma conta ou entre para participar dessa discussão

Crie uma nova conta

Entrar

Olimpíadas ⇒ (Mercosul - 1997) Função Piso II Tópico resolvido

Crie uma conta ou entre para participar dessa discussão

Crie uma nova conta

Entrar

EntrarcRegistrar