Olimpíadas

a) Estude o comportamento do resto da divisão por 7 de [tex3]2^x-x^2[/tex3] sendo x um número inteiro positivo menor ou igual a 10000.
b) Quantos são os inteiros positivos [tex3]x\leq 10000[/tex3] tais que a diferença [tex3]2^x-x^2[/tex3] não é divisível por 7?

Resposta

b) 7142

Mensagem não lida por **παθμ** » 19 Out 2023, 22:54

Restos de 2^x: [tex3]2^1 \equiv2, \; 2^2 \equiv 4, \; 2^3 \equiv 1,[/tex3] depois disso cicla.

Restos de x^2: [tex3]1^2 \equiv 1, \; 2^2 \equiv 4, \; 3^2 \equiv 2, \; 4^2 \equiv 2, \; 5^2 \equiv 4, \; 6^2 \equiv 1, \; 7^2 \equiv 0,[/tex3] depos disso cicla (já que 8 é congruente a 1, 9 é congruente a 2, ...).

Os restos de [tex3]2^x[/tex3] são representados na sequência de período 3 (2, 4, 1, 2, 4, 1, 2, 4, 1, ...) (Sequência A)

Os restos de [tex3]x^2[/tex3] são representados na sequência de período 7 (1, 4, 2, 2, 4, 1, 0, 1, 4, 2, 2, 4, 1, 0, 1, 4, 2, 2, 4, 1, 0, ...) (Sequência B)

Então, encaixando os restos de [tex3]2^x[/tex3] e [tex3]x^2[/tex3] para cada valor de [tex3]x,[/tex3] formamos a sequência de tuplas, na forma (resto de x^2, resto de 2^x):

[tex3](1,2),(4,4),(2,1),(2,2),...[/tex3] (Sequência C)

Vamos encontrar o período dessa sequência. Para isso, vamos encontrar o menor valor de [tex3]n>1[/tex3] para o qual a n-ésima tupla da sequência C é igual a (1,2), em que esse algarismo 1 veio obrigatoriamente de uma posição da forma [tex3]7q+1[/tex3] da sequência B, [tex3]q[/tex3] inteiro.

Ou seja, queremos o menor inteiro [tex3]n>1[/tex3] tal que [tex3]n=7q+1[/tex3] e [tex3]n=3m+1 \Longrightarrow 7q=3m[/tex3] , com "q" e "m" inteiros.

Claramente devemos ter [tex3]m=7, \; q=3[/tex3] e [tex3]n=22.[/tex3] Ou seja, a sequência C tem período 21.

Vamos contar quantas vezes o resto de [tex3]2^x-x^2[/tex3] é zero em um período. Ou seja, quantas vezes em um período os dois elementos das tuplas da sequência C são iguais.

Off Topic

Um jeito fácil de contar isso é pegar uma folha de papel na horizontal e escrever os 21 primeiros termos da sequência A, e depois acima ou abaixo escrever, nas mesmas posições horizontais, os elementos da sequência B. Isso é bem mais rápido do que escrever (1,2), (4,4), (2,1), ... porque escrevendo uma sequência de cada vez você rapidamente decora o padrão.

Observamos que, a cada período, o resto de [tex3]2^x-x^2[/tex3] por 7 é zero 6 vezes.

Ou seja, de 1 a 21 contamos 6, de 22 a 42 contamos mais 6, de 43 a 63 contamos mais 6, assim por diante.

Temos [tex3] \left\lfloor \frac{10000}{21} \right\rfloor=476.[/tex3] Assim, há 476 intervalos de tamanho [tex3]21[/tex3] de 1 a 10000.

[tex3]476 \times 21=9996.[/tex3]

Então, de [tex3]x=1[/tex3] a [tex3]x=9996,[/tex3] há [tex3]476 \times 6=2856[/tex3] ocorrências em que o resto é zero.

De [tex3]x=9997[/tex3] a [tex3]x=10000,[/tex3] basta escrever os 4 primeiros elementos de um período da sequência C:

(1,2), (4,4), (2,1), (2,2). Ou seja, o resto é zero duas vezes.

No total há [tex3]2856+2=2858[/tex3] valores de [tex3]x[/tex3] para o qual o resto é zero.

[tex3]10000-2858=\boxed{7142}[/tex3]

Olimpíadas ⇒ (Goiás) Congruência Tópico resolvido

(Goiás) Congruência

Re: (Goiás) Congruência

Crie uma conta ou entre para participar dessa discussão

Crie uma nova conta

Entrar