OlimpíadasConjuntos Tópico resolvido

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 ]

Autor do Tópico
goncalves3718
3 - Destaque
Mensagens: 816
Registrado em: Qui 26 Dez, 2019 15:26
Última visita: 11-04-23
Jan 2021 31 09:32

Conjuntos

Mensagem não lida por goncalves3718 »

Seja [tex3]A[/tex3] um conjunto de inteiros positivos satisfazendo:

a) Se [tex3]a ∈ A[/tex3] , então todos os divisores positivos de a estão em [tex3]A[/tex3] .
b) Se [tex3]a, b ∈ A[/tex3] , com [tex3]1 < a < b,[/tex3] então [tex3]1 + ab ∈ A[/tex3] .

Prove que se [tex3]A[/tex3] tem pelo menos três elementos, então [tex3]A[/tex3] é o conjunto dos números naturais.




Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 5114
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 17-04-23
Fev 2021 01 09:37

Re: Conjuntos

Mensagem não lida por csmarcelo »

O enunciado está certinho?




Autor do Tópico
goncalves3718
3 - Destaque
Mensagens: 816
Registrado em: Qui 26 Dez, 2019 15:26
Última visita: 11-04-23
Fev 2021 01 14:14

Re: Conjuntos

Mensagem não lida por goncalves3718 »

Sim! Acabei de verificar :D



Avatar do usuário
Ittalo25
5 - Mestre
Mensagens: 2349
Registrado em: Seg 18 Nov, 2013 22:11
Última visita: 27-03-24
Fev 2021 01 23:54

Re: Conjuntos

Mensagem não lida por Ittalo25 »

é uma afirmação bem forte, não sei se é o suficiente para provar mas pensei nisso:
FelipeMartin,
Resposta

Se existe um primo p que não pertence a A, então os múltiplos de p também não pertencerão a A e portanto A não será o conjunto dos naturais.
Então suponha que não existam múltiplo de p no conjunto.

Mas então:
[tex3]ab+1 \neq 0 \mod(p)[/tex3]
[tex3](ab)^2 \neq 1 \mod(p)[/tex3]
[tex3](ab-1) \cdot (ab+1) \neq 0 \mod(p)[/tex3]
Por suposição [tex3]ab+1 \neq 0 \mod(p)[/tex3] , então dá para simplificar:
[tex3]ab-1 \neq 0 \mod(p)[/tex3]
[tex3]ab \neq 1 \mod(p)[/tex3]

Mas por suposição [tex3]mdc(a,p)=mdc(b,p) = 1 [/tex3] , então pelo teorema de Bezout existem inteiros positivos x e y tais que:
[tex3]ax-py = 1 [/tex3]
[tex3]ax \equiv1 \mod(p) [/tex3]
Então x não pertence a A (se pertencesse bastaria fazer [tex3]b=x [/tex3] e seria contradição para [tex3]ab \neq 1 \mod(p)[/tex3] )
Como x não pertence a A, então [tex3]x\equiv 0 \mod(p)\rightarrow ax \equiv 0 \mod(p) [/tex3]
Contradição.
Última edição: Ittalo25 (Ter 02 Fev, 2021 00:19). Total de 2 vezes.


Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]

FelipeMartin
4 - Sabe Tudo
Mensagens: 2196
Registrado em: Sáb 04 Jul, 2020 10:47
Última visita: 27-03-24
Fev 2021 02 01:43

Re: Conjuntos

Mensagem não lida por FelipeMartin »

Ittalo25, acho que [tex3]ab + 1 \neq 0 \mod p[/tex3] não implica [tex3]ab \neq 1 \mod p[/tex3] e você não usou que A tem três elementos. Mas gostei da ideia dos números primos no conjunto, acho que ela é o caminho. O fato de a e b estarem em A enquanto p não está garante aqueles seus dois mdcs.

O problema está na sua contradição do x que, ao meu ver, não é uma contradição uma vez que podemos ter [tex3]ax =1 \mod p[/tex3]


φως εσύ και καρδιά μου εγώ πόσο σ' αγαπώ.

Avatar do usuário
leozitz
2 - Nerd
Mensagens: 331
Registrado em: Qui 06 Jan, 2022 16:26
Última visita: 26-02-24
Jan 2022 14 12:29

Re: Conjuntos

Mensagem não lida por leozitz »

vamos usar indução.
1º caso) n composto > 5:
nesse caso n = ab, onde todos os números {1, 2, ..., ab-1} estão em A, suponha a diferente de b.
consigo ab + 1 e depois junto ab+1 com ab-1 já que por hipótese a, b estão em A, no caso de [tex3]n = a^2[/tex3]
[tex3]a^2 = (a-1)(a+1) + 1[/tex3]

2º caso) [tex3]n = p[/tex3]
nesse caso a gente simplesmente pega 2 e um número k tal que 2k + 1 = p, claro que pra isso precisamos de k > 2

vamos conseguir agora 1, 2, 3, 4, 5.
é claro que 2 está em A, o 1 tbm, digamos que outro número da hipótese seja x
[tex3]x\equiv 0\pmod{3}\implies 3\in A[/tex3]
[tex3]x\equiv 1\pmod{3}\implies 2x+1\equiv0\pmod{3}[/tex3]
[tex3]x\equiv2\pmod{3}\implies2x+1\equiv2(\mod3)[/tex3] esse caso eu faço ali em baixo

as congruências aqui são mod 5
[tex3]x\equiv 1(\mod5)\implies 2x+1\equiv3\implies x(2x+1)+1\equiv4\implies
x(x(2x+1)+1) + 1\equiv 0[/tex3]
[tex3]x\equiv 2\implies 2x+1\equiv 0[/tex3]
[tex3]x\equiv 3\implies2x+1\equiv2\implies 2(2x+1)+1\equiv 0[/tex3]
[tex3]x\equiv 4\implies 2x + 1 \equiv 4\implies x(2x+1)+1\equiv 2[/tex3] junta com o 2 e acaba
ok, eu consegui o 5 agr consigo o 3 pq [tex3]2\cdot5+1 = 11[/tex3] junta 5 e 11 e consegue o 7, junta 7 e 2 e consegue o 3
agr fica faltando o 4 que na verdade eu já achei pq 4|56
rascunho

aqui fala oq eu estava tentando fazer no segundo caso KKKKKKKKKKKKK, só fui ver depois de ter achado esse "argumento" que podia fazer como na solução, n precisa ler se n quiser.

por hipótese A = {1, 2, ..., p-1} eu tive a ideia de conseguir gerar as potencias de um número para depois conseguir [tex3]a^k\equiv 1 \pmod {p}[/tex3] e juntar com p-1 se eu conseguisse todas as potencia de um número esse k iria existir.
vamos pegar um número fixo x, digamos x = 2, agora a gente pode juntar ele com {3, ..., p-1} que tem p-1-3+1 = p-3 valores
vamos olhar agora para os resíduos de 2b + 1 onde b está naquele conjunto, esse conjunto assume p - 3 valores, um para cada b ai agora tem alguns valores que se algum desses resíduos for igual da ruim
no final das contas ficou + parecido com um argumento extremal do que com indução




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

Voltar para “Olimpíadas”