Olimpíadas

Um número a de três cifras é raro se existe um número b de duas cifras tal que ao dividir a por b, o resto é igual ao cubo do quociente. Por exemplo, 100 é raro porque ao dividi-lo por 46, o quociente é 2 e o resto é 8 (2^3). Quantos números raros de três cifras existem?

Resposta

113

Mensagem não lida por **παθμ** » 20 Out 2023, 11:44

[tex3]a=bq+q^3 \Longrightarrow a=q(b+q^2).[/tex3]

Precisamos analisar os valores de [tex3]q[/tex3] caso a caso. Note que sempre devemos ter [tex3]b>q^3.[/tex3]

Caso q=1: [tex3]a=b+1.[/tex3]

Nesse caso, o único valor permitido de [tex3]b[/tex3] é [tex3]99[/tex3] , já que [tex3]a<100[/tex3] para todos os outros valores. Contamos 1 número raro para esse caso (o número 100).

Caso q=2: [tex3]a=2(b+4).[/tex3]

Para que [tex3]a \geq 100,[/tex3] devemos ter [tex3]2(b+4) \geq 100 \Longrightarrow b \geq 46.[/tex3] Lembrando que [tex3]b \leq 99,[/tex3] há [tex3]99-46+1=54[/tex3] valores possíveis de [tex3]b.[/tex3] Porém, [tex3]a=100[/tex3] resulta de [tex3]b=46[/tex3] nesse caso, e esse número raro já foi contado. Então, até o momento, nosso contador é [tex3]54-1=53.[/tex3]

Caso q=3: [tex3]a=3(b+9).[/tex3]

Devemos ter [tex3]b>3^3 \Longrightarrow b \geq 28.[/tex3] Isso já garante que [tex3]a \geq 100.[/tex3] Então, com [tex3]28 \leq b \leq 99,[/tex3] temos [tex3]99-28+1=72[/tex3] valores possíveis de [tex3]b[/tex3] para esse caso. Mas agora precisamos determinar quantos valores de [tex3]a[/tex3] estamos contando aqui que já foram contados anteriormente (mais especificamente no caso q=2).

No presente caso, veja que estamos contando todos os múltiplos de 3 de [tex3]111[/tex3] até [tex3]324.[/tex3] No caso q=2, nós contamos alguns desses números. A primeira condição para isso ter ocorrido é [tex3]2(b+4) \equiv 0 \pmod{3} \Longrightarrow b+4 \equiv 0 \Longrightarrow b \equiv 2 \pmod{3},[/tex3] então isso ocorreu para valores de b da forma [tex3]b=3k+2.[/tex3]

No caso 2, o menor valor de [tex3]k,[/tex3] tal como definido acima, para que tenhamos [tex3]a \geq 111[/tex3] é [tex3]k=17.[/tex3] Ademais, o maior valor de [tex3]k[/tex3] para o qual temos [tex3]b \leq 99[/tex3] é [tex3]k=32[/tex3] (para o qual temos [tex3]a=204[/tex3] ). Ou seja, os valors de [tex3]b[/tex3] no caso q=2 para o qual nós contamos números que estão contidos no caso 3 são [tex3]3 \times 17+2, \; 3 \times 18+2, \; 3 \times 19+2, \; ..., \; 3 \times 32+2.[/tex3] Ou seja, são [tex3]32-17+1=16[/tex3] valores de [tex3]b,[/tex3] implicando em [tex3]16[/tex3] valores de [tex3]a[/tex3] que são comuns aos casos q=2 e q=3.

Por isso, nosso contador até o momento é [tex3]53+(72-16)=109.[/tex3]

Caso q=4: [tex3]a=4(b+64).[/tex3]

Devemos ter [tex3]b \geq 65[/tex3] e [tex3]b \leq 99,[/tex3] o que resulta em [tex3]99-65+1=35[/tex3] valores de [tex3]a.[/tex3] Felizmente, para todos os valores de [tex3]b[/tex3] permitidos no caso q=4, os valores de [tex3]a[/tex3] são maiores do que todos os contados anteriormente, então não precisamos nos preocupar com repetições.

Para os casos [tex3]q \geq 5,[/tex3] precisaríamos ter [tex3]b >125,[/tex3] absurdo.

A quantidade de números raros é, então: [tex3]109+35=\boxed{144}[/tex3]

Seu gabarito está incorreto. Eu até fiz um programa bem simples em Python para verificar minha resposta, e o output do programa é 144:

Código: Selecionar todos

contador=0
for a in range(100, 1000):
    for b in range(10, 100):
        r=a%b
        q=int(a/b)
        if r==q**3:
            contador+=1
            break
print(contador)

Olimpíadas ⇒ (Argentina) Propriedades da divisibilidade Tópico resolvido

(Argentina) Propriedades da divisibilidade

Re: (Argentina) Propriedades da divisibilidade

Crie uma conta ou entre para participar dessa discussão

Crie uma nova conta

Entrar