Olimpíadas(Torneio das Cidades) Teoria dos números

Aqui devem ser postados problemas Olímpicos. Informe a olimpíada e o ano no título do tópico. Exemplo: (OBM - 2008).

Moderador: [ Moderadores TTB ]

Autor do Tópico
Deleted User 23699
6 - Doutor
Última visita: 31-12-69
Ago 2021 13 10:47

(Torneio das Cidades) Teoria dos números

Mensagem não lida por Deleted User 23699 »

Para todo inteiro de (n+1) a 2n, inclusive (n natural), calculamos o maior divisor ímpar e somamos todos esses divisores. Prove que a soma obtida é n².




Avatar do usuário
leozitz
2 - Nerd
Mensagens: 331
Registrado em: Qui 06 Jan, 2022 16:26
Última visita: 26-02-24
Jun 2022 27 16:04

Re: (Torneio das Cidades) Teoria dos números

Mensagem não lida por leozitz »

vamos usar indução.
f(x) = maior divisor ímpar de x.

por hipótese [tex3]\sum_{k = n+1}^{2n}f(k) = n^2[/tex3] e queremos descobrir [tex3]\sum_{k = n+2}^{2n+2}f(k)[/tex3] .

[tex3]\sum_{k = n+2}^{2n+2}f(k) = f(2n + 2) + f(2n + 1) + n^2 - f(n+1) \\ \sum_{k = n+2} = f(2(n+1)) - f(n+1) + 2n + 1 + n^2[/tex3]
como por definição a função f(x) ignora os fatores 2, a gente tem que [tex3]f(2a) = f(a)[/tex3]
então aquilo é igual a [tex3]2n + 1 + n^2 = (n+1)^2[/tex3]
agora a base é tranquilo verificar(verifique! kkkkkk) fica provado por indução




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Olimpíadas”