OlimpíadasAIME - 2002 - Teoria dos Números Tópico resolvido

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
Auto Excluído (ID:17906)
5 - Mestre
Última visita: 31-12-69
Mai 2017 30 16:16

AIME - 2002 - Teoria dos Números

Mensagem não lida por Auto Excluído (ID:17906) » Ter 30 Mai, 2017 16:16

Sabe-se que, para todos os inteiros positivos [tex3]k[/tex3] ,
[tex3]1^2 + 2^2 + 3^2 + ... + k^2 = \frac{k(k + 1)(2k + 1)}{6}.[/tex3]
Encontre o menor número inteiro positivo [tex3]k[/tex3] de tal forma que [tex3]1^2 + 2^2 + 3^2 + ... + k^2[/tex3] é múltiplo de [tex3]200[/tex3] .

Última edição: Auto Excluído (ID:17906) (Ter 30 Mai, 2017 16:16). Total de 1 vez.



Avatar do usuário
undefinied3
5 - Mestre
Mensagens: 1251
Registrado em: Dom 02 Ago, 2015 13:51
Última visita: 22-10-19
Agradeceu: 134
Agradeceram: 1111
Jun 2017 21 21:41

Re: AIME - 2002 - Teoria dos Números

Mensagem não lida por undefinied3 » Qua 21 Jun, 2017 21:41

[tex3]200=2^3.5^2[/tex3]
[tex3]200t = \frac{k(k+1)(2k+1)}{6}[/tex3]
Então [tex3]k(k+1)(2k+1)[/tex3] deve conter pelo menos 4 fatores 2 e 2 fatores 5. O menor número com 4 fatores 2 é 16, e o menor com 2 fatores 5 é 25.
Supondo k par, temos k+1 ímpar e 2k+1 ímpar, de modo que os fatores 2 viriam exclusivamente do fator k naquela fórmula. Segue que basta verificar qual a menor potência de 2 maior ou igual 16 que forneceria, com os outros fatores, múltiplos de 5 suficientes. Para k+1 ter fator 5, k deve terminar em 4, e para 2k+1 ter fator 5, k deve terminar em 2, ou seja, não precisamos testar nenhuma potência de 2 que não satisfaça uma das condições
k=32 não fornece
k=64 não fornece
k=512 satisfaz
Mas isso não é suficiente para afirmar que k=512 é menor possível, precisamos ver k ímpar, de modo que k+1 é que fornecerá os fatores 2. Aqui, basta analisar [tex3]k=2^n-1[/tex3] . Para que 2k+1 tenha fatores 2, k deve terminar em 7, mas por outro lado o próprio k pode dar fatores 5 se terminar em 0 ou 5. Devemos testar então [tex3]k=2^n-1 \geq 15[/tex3] tais que terminem em 0, 5 ou 7
k=15 não fornece
k=127 não fornece
k=255 não satisfaz
k=511 não satisfaz
Qualquer outro k será maior que nossa tentiva com k par.
Assim, creio que o menor k é 512.

Última edição: undefinied3 (Qua 21 Jun, 2017 21:41). Total de 1 vez.


Ocupado com início do ano no ITA. Estarei fortemente inativo nesses primeiros meses do ano, então busquem outro moderador para ajudar caso possível.

Avatar do usuário
undefinied3
5 - Mestre
Mensagens: 1251
Registrado em: Dom 02 Ago, 2015 13:51
Última visita: 22-10-19
Agradeceu: 134
Agradeceram: 1111
Jun 2017 21 21:59

Re: AIME - 2002 - Teoria dos Números

Mensagem não lida por undefinied3 » Qua 21 Jun, 2017 21:59

Isso tá insuficiente, [tex3]2^4.3[/tex3] teria fatores 2 suficientes e é menor que 512. Falta uma certa análise ainda, mas sabemos que [tex3]k \leq 512[/tex3]

Para que k+1 possua os fatores 5: [tex3]k \equiv 4 \rightarrow 16k' \equiv 4 \rightarrow 4k' \equiv 1 \rightarrow k' \equiv 4 \ (mod \ 5)[/tex3] , então [tex3]k=2^4k'=16(5k''+4)=80k''+64'[/tex3]
Para que [tex3]2k+1[/tex3] possua fatores 5: [tex3]2k \equiv 4 \rightarrow k \equiv 2 \rightarrow 16k'\equiv 2 \rightarrow 8k'\equiv 1 \rightarrow k' \equiv 2 \ (mod \ 5)[/tex3] , então [tex3]k=2^4k'=16(5k''+2)=80k''+32[/tex3]
Nossas possibilidades com [tex3]k \leq 512[/tex3] são:
32, 64, 112, 144, 192, 224, 272 e algumas outras.
Voltando na fórmula, 32 não irá satisfazer, 64 também não, 112 por outro lado, funciona:
[tex3]\frac{112.113.225}{6}=474600=2373*200[/tex3]

Agora é verificar se k ímpar daria algo menor:
[tex3]k+1=16k' \rightarrow k=16k'-1 \leq 511[/tex3]
Para que k possua fatores 5: [tex3]16k'-1 \equiv 0 \rightarrow 16k' \equiv 1 \rightarrow k' \equiv 1 \ (mod \ 5 )[/tex3] , então [tex3]k=16(5k''+1)-1=80k ''+15[/tex3]
Para que 2k+1 possua fatores 5: [tex3]32k'-1 \equiv 0 \rightarrow 32k' \equiv 1 \rightarrow k' \equiv 3 \ (mod \ 5)[/tex3] , então [tex3]k=16(5k''+3)-1=80k''+47[/tex3]
As possibilidades são 15, 47, 95. Nenhuma satisfaz.

Concluimos que o verdadeiro menor k possível é 112. Eu e minha afobação em concluir as questões sem analisar tudo adequadamente...

Última edição: undefinied3 (Qua 21 Jun, 2017 21:59). Total de 1 vez.


Ocupado com início do ano no ITA. Estarei fortemente inativo nesses primeiros meses do ano, então busquem outro moderador para ajudar caso possível.

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg
  • Nova mensagem (AIME-1985) Teoria dos números
    por undefinied3 » Qui 22 Jun, 2017 12:23 » em Olimpíadas
    3 Respostas
    653 Exibições
    Última msg por undefinied3
    Seg 24 Jul, 2017 18:02
  • Nova mensagem AIME - 1996 - Raciocínio Lógico
    por Auto Excluído (ID:17906) » Dom 21 Mai, 2017 10:51 » em Olimpíadas
    1 Respostas
    427 Exibições
    Última msg por Lonel
    Sáb 10 Jun, 2017 00:08
  • Nova mensagem (AIME-1990) - Equação do segundo grau
    por undefinied3 » Qui 22 Jun, 2017 12:04 » em Olimpíadas
    1 Respostas
    458 Exibições
    Última msg por Andre13000
    Qui 22 Jun, 2017 16:10
  • Nova mensagem (AIME-2006) - Fatoração
    por undefinied3 » Qui 22 Jun, 2017 12:07 » em Olimpíadas
    1 Respostas
    399 Exibições
    Última msg por Auto Excluído (ID:17906)
    Qui 22 Jun, 2017 15:53
  • Nova mensagem (AIME-2013) Polinômios
    por undefinied3 » Qui 22 Jun, 2017 12:10 » em Olimpíadas
    1 Respostas
    382 Exibições
    Última msg por Andre13000
    Qui 22 Jun, 2017 15:08

Voltar para “Olimpíadas”