OlimpíadasDivisibilidade - Dúvida em questão do POTI

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 ]

Avatar do usuário
Autor do Tópico
Ardovino
Avançado
Mensagens: 118
Registrado em: Ter 07 Dez, 2010 20:22
Última visita: 20-11-20
Jan 2019 12 14:56

Divisibilidade - Dúvida em questão do POTI

Mensagem não lida por Ardovino »

Boa Tarde pessoal, tudo bem ?

Então, eu tava vendo uma videoaula do POTI sobre divisibilidade, essa aqui:

https://www.youtube.com/watch?v=dbSi0vqBIhY

Ele apresenta o Lema:

Se d | a e d | b ----> d | ax + by

Beleza. Mas acontece que ele usa isso nos problemas de uma forma como se estivesse garantido da volta, por exemplo, no ultimo problema ele quer descobrir qual o maior n para o qual n+10 divide n^3+100.

Aí ele faz:
Bom, n^3 + 1000 = (n+10)(...)
Logo, n+10 divide n^3+1000

Então vamos descobrir esse n com essas duas infos e o Lema:
n+10 | n^3 + 1000
n+10 | n^3 + 100

Usando o Lema subtraindo as "equações":
n+10 | 900, logo o maior n que encaixa é 890.


Beleza, mas provar isso não teria que ser possível verificar a volta ?:
Que seria:
n+10 | 900 ------> n+10 | n^3 + 1000
---------------------- n+10 | n^3 + 100

??
Se alguém puder esclarecer, fico agradecido. Valeu ! :)




Auto Excluído (ID:12031)
6 - Doutor
Última visita: 31-12-69
Jan 2019 12 15:08

Re: Divisibilidade - Dúvida em questão do POTI

Mensagem não lida por Auto Excluído (ID:12031) »

não, ele só está usando a ida, mas usa [tex3]x=1[/tex3] e [tex3]y=-1[/tex3] , nada demais




Avatar do usuário
Autor do Tópico
Ardovino
Avançado
Mensagens: 118
Registrado em: Ter 07 Dez, 2010 20:22
Última visita: 20-11-20
Jan 2019 12 15:17

Re: Divisibilidade - Dúvida em questão do POTI

Mensagem não lida por Ardovino »

sousóeu escreveu:
Sáb 12 Jan, 2019 15:08
não, ele só está usando a ida, mas usa [tex3]x=1[/tex3] e [tex3]y=-1[/tex3] , nada demais
eu sei que ele só está usando a ida
mas para provar isso não teria de se provar a volta?

Quero dizer, a lógica de provar que n = 890 seria de n+10|900 chegar que n divide aquelas duas outras coisas, aí sim teria provado que esse eh um valor válido.

Ou verificando que ele vale nas duas, o que é complicado nesse caso.

Tipo com equações, vc não pode só ter a ida, tem de ter a volta para provar que sua solução é aquela.

Não tô certo ?



Avatar do usuário
Autor do Tópico
Ardovino
Avançado
Mensagens: 118
Registrado em: Ter 07 Dez, 2010 20:22
Última visita: 20-11-20
Jan 2019 12 15:20

Re: Divisibilidade - Dúvida em questão do POTI

Mensagem não lida por Ardovino »

n+10|900 --------> n | n^3 + 1000 e n | n^3 + 100

eu acho que só teria provado mesmo se conseguisse fazer isso, ou verificar que 890 é um valor que funciona.



Auto Excluído (ID:12031)
6 - Doutor
Última visita: 31-12-69
Jan 2019 12 15:23

Re: Divisibilidade - Dúvida em questão do POTI

Mensagem não lida por Auto Excluído (ID:12031) »

não, ele está assumindo que existe o [tex3]n[/tex3] para tentar encontrá-lo.

Tudo bem, pode-se verificar depois se funciona mesmo.

Mas se existir tal [tex3]n[/tex3] então [tex3]n+10[/tex3] divide [tex3]900[/tex3]



Avatar do usuário
Autor do Tópico
Ardovino
Avançado
Mensagens: 118
Registrado em: Ter 07 Dez, 2010 20:22
Última visita: 20-11-20
Jan 2019 12 15:28

Re: Divisibilidade - Dúvida em questão do POTI

Mensagem não lida por Ardovino »

tipo a divide b e a divide c

tá, blz, então esse a divide b-c

aí observando que a divide b-c eu posso chegar a conclusao sobre quem pode ser a.

mas sei lá se esse a divide b e c em separado.

Não está certa a lógica ?

Tipo, nesse caso aí quando chega na conclusão que se existe esse n então n+10 | 900, tem vários n's possíveis, como eh que vou saber que o 890 funciona para dividir b e c, tá ligado ?


É... achei meio incerto isso, mas blz



Auto Excluído (ID:12031)
6 - Doutor
Última visita: 31-12-69
Jan 2019 12 15:33

Re: Divisibilidade - Dúvida em questão do POTI

Mensagem não lida por Auto Excluído (ID:12031) »

Ardovino escreveu:
Sáb 12 Jan, 2019 15:28
tipo a divide b e a divide c

mas sei lá se esse a divide b e c em separado.
acho meio contraditório essas duas linhas aqui



Auto Excluído (ID:12031)
6 - Doutor
Última visita: 31-12-69
Jan 2019 12 15:38

Re: Divisibilidade - Dúvida em questão do POTI

Mensagem não lida por Auto Excluído (ID:12031) »

eu entendi o que você está falando:

se ele divide a diferença não necessariamente divide em separado

no geral isso é verdade, pra isso você confere depois.

No caso imagina que [tex3]d[/tex3] com certeza divide [tex3]a[/tex3] , se [tex3]d[/tex3] divide [tex3]a-b[/tex3]

então [tex3]d[/tex3] divide [tex3](-1)*(a-b) + a = b[/tex3]



Avatar do usuário
Autor do Tópico
Ardovino
Avançado
Mensagens: 118
Registrado em: Ter 07 Dez, 2010 20:22
Última visita: 20-11-20
Jan 2019 12 15:50

Re: Divisibilidade - Dúvida em questão do POTI

Mensagem não lida por Ardovino »

então, eu entendi direitinho o que ele fez.
só não concordo com essa conclusão rápida de que n é 890 sem nem testar.

n+10 podia ser outro numero que dividisse 900, ou sei lá, nem existir um que funcionasse nos carinhas em separado.

Do jeito que ele fez parece que é óbvio que todos os n's que funcionam na ultima tem de funcionar nos caras em separado e o maior que funciona realmente é o 890. Sei lá, pra mim isso nao é obvio.

Consegue achar algum exemplo que faça não funcionar ? Tipo, achar duas expressoezinhas que vc some e chegue conclua que o n tem de ser algm que não funciona nos dois em separado ? kkkk

eu fico meio estressado com esses detalhes



Auto Excluído (ID:12031)
6 - Doutor
Última visita: 31-12-69
Jan 2019 12 15:56

Re: Divisibilidade - Dúvida em questão do POTI

Mensagem não lida por Auto Excluído (ID:12031) »

nesse caso, todos os divisores de 900 devem funcionar.

Pois todos divisores de 900 (menos 10) satisfazem: [tex3]d +10 \vert d^3 + 1000[/tex3] e [tex3]d+10 |900[/tex3]

então [tex3]d+10 \vert d^3 + 1000 - 900 = d^3 + 100[/tex3]

[tex3]90-10 = 80[/tex3]
então
[tex3]n = 80[/tex3] funciona
porque [tex3]80^3 = 512000[/tex3]
e [tex3]90 \vert 512100[/tex3] já que [tex3]512100 = 90 \cdot 5690[/tex3]

Última edição: Auto Excluído (ID:12031) (Sáb 12 Jan, 2019 16:03). Total de 1 vez.



Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Olimpíadas”