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
Olimpíadas ⇒ (Goiás) Congruência Tópico resolvido
Moderador: [ Moderadores TTB ]
-
Deleted User 23699
- Última visita: 31-12-69
Set 2020
02
11:58
(Goiás) Congruência
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?
b) 7142
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?
b) 7142
-
παθμ
- Mensagens: 896
- Registrado em: 08 Abr 2023, 17:28
- Última visita: 30-04-24
- Localização: Evanston, IL
- Agradeceram: 3 vezes
Out 2023
19
22:54
Re: (Goiás) Congruência
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.
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]
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.
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]
Última edição: παθμ (19 Out 2023, 23:33). Total de 2 vezes.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
