Olimpíadas ⇒ AIME - 2002 - Teoria dos Números

[Auto Excluído (ID:17906)]

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].

[undefinied3]

[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.

[undefinied3]

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...