Re: [obm-l] Problema 2 da OBM U

[Anderson Torres]

OPA! Tem um problema no meu problema!

Em 18 de novembro de 2017 16:48, Anderson Torres
 escreveu:
> Em 15 de novembro de 2017 15:01, Otávio Araújo
>  escreveu:
>> Alguém poderia me ajudar no problema 2 da segunda fase da obm u desse ano? O
>> enunciado é o seguinte:
>> "Fixados os inteiros positivos a e b, mostre que o conjunto dos divisores
>> primos dos termos da sequencia
>> an = a · 2017^n + b · 2016^n
>> é infinito."
>
> Não é difícil difícil, apenas precisa ter a ideia certa. Aqui eu fui
> um pouco mais formalista do que o necessário, mas a ideia é que se
> construirmos uma sequência dessas com poucos primos, eles explodem.
>
> Caso I: o conjunto {p_1,p_2,...} de todos os primos que aparecem em
> todas as fatorações de a_n é infinito. Neste caso, o problema acaba
> antes mesmo de começar.
>
> Caso II: o conjunto {p_1,p_2,...,p_k} de todos os primos que aparecem
> em todas as fatorações de a_n é finito. Vamos trabalhar apenas com
> esses primos, a não ser que seja dito algo contrário.
>
> Assim sendo, podemos fatorar cada a_n da seguinte forma:
>
> a_n = p_1^(e(1,n)) * p_2^(e(2,n)) * p_3^(e(3,n)) * ... * p_k^(e(k,n))
>
> A cada a_n, vamos associar a maior dessas potências. Por exemplo, 72 =
> 2^3 * 3^2 estaria associada a 3^2, pois 3^2 = 9 > 8 = 2^3.
>
> LEMA: Seja M_n = MDC(a*2017^n, b*2016^n). Então M_n é limitada.
>
> De fato, se tentarmos fatorar, os fatores de 2017 não aparecem em 2016
> e vice-versa, dado serem primos entre si. Logo os fatores de 2017 só
> podem aparecer em b, e os fatores de 2016 só podem aparecer em a.
> Portanto, M_n = MDC(a,2016^n) * MDC(b,2017^n) | ab, logo, limitado.
>
> Vamos dividir nossa sequência em fitas de tamanho (K+1):
>
> a_(0*k+0), a_(0*k+1),...,a_(0*k+k)
> a_(1*k+0), a_(1*k+1),...,a_(1*k+k)
> a_(2*k+0), a_(2*k+1),...,a_(2*k+k)
> a_(3*k+0), a_(3*k+1),...,a_(3*k+k)
> a_(4*k+0), a_(4*k+1),...,a_(4*k+k)
> a_(5*k+0), a_(5*k+1),...,a_(5*k+k)
> ... ... ...
>
> Se aplicarmos o princípio das gavetas em cada fita separadamente,
> podemos dizer que para cada fita existe um primo tal que potências
> desse primo aparecem (pelo menos) duas vezes entre os associados.
> Vamos então anotar este primo para cada faixa:
>
> a_(0*k+0), a_(0*k+1),...,a_(0*k+k)
> a_(1*k+0), a_(1*k+1),...,a_(1*k+k)
> a_(2*k+0), a_(2*k+1),...,a_(2*k+k)
> a_(3*k+0), a_(3*k+1),...,a_(3*k+k)
> a_(4*k+0), a_(4*k+1),...,a_(4*k+k)
> a_(5*k+0), a_(5*k+1),...,a_(5*k+k)
>
>
> Como o número de faixas é infinito e o número de possíveis primos
> associados é finito, então existe um primo tal que infinitas faixas
> tenham potências desse mesmo primo associadas.
>

Esta parte é falsa, pois eu não demonstrei que as fitas com o primo P
são consecutivas, aliás é capaz que elas não sejam.

Mas isso pouco abala a demonstração, pois em cada fita existirão dois
caras com o fator P, e a distância entre eles é limitada.

> Com esse raciocínio, nós demonstramos que existe uma sub-sequência de
> a, chamemos ela de A, tal que todas as potências associadas a A são
> potências de um mesmo primo p. Além disso, a distância entre os A
> consecutivos na sequência original a é no máximo 2(k+1), afinal o pior
> que pode acontecer é que pegamos dois índices que ficavam em extremos
> opostos de faixas distintas.
>
> Pois bem, peguemos dos A_t consecutivos, a saber, a_t, e a_(t+v).
> Podemos dizer que existe um u máximo tal que p^u | a_t e p^u |
> a_(t+v). Logo,
>
> p^u | a_(t+v) - 2017^v * a_t = b * 2016^t * (2017^v-2016^v) | M_t *
> (2017^v-2016^v)
>
> Mas isto implica p^u <= M_t * (2017^v-2016^v) <= ab *
> (2017^(2k+2)-2016^(2k+2)), ou seja, p^u é limitado.
>
> Porém, a_t = p_1^(e(1,t)) * p_2^(e(2,t)) * p_3^(e(3,t)) * ... *
> p_k^(e(k,t)) <= p^u * p^u * p^u * ... * p^u = (p^u)^k, o que implica
> que (p^u) é ilimitado (pois a_t é ilimitado).
>
> E isto é um absurdo! Logo, o nosso caso II não se sustenta - e ficamos
> com o caso I apenas!
>
>>
>> --
>> Esta mensagem foi verificada pelo sistema de antivírus e
>> acredita-se estar livre de perigo.
>
> Já que você diz...

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.


=
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

Re: [obm-l] Problema 2 da OBM U

[Anderson Torres]

Em 15 de novembro de 2017 15:01, Otávio Araújo
 escreveu:
> Alguém poderia me ajudar no problema 2 da segunda fase da obm u desse ano? O
> enunciado é o seguinte:
> "Fixados os inteiros positivos a e b, mostre que o conjunto dos divisores
> primos dos termos da sequencia
> an = a · 2017^n + b · 2016^n
> é infinito."

Não é difícil difícil, apenas precisa ter a ideia certa. Aqui eu fui
um pouco mais formalista do que o necessário, mas a ideia é que se
construirmos uma sequência dessas com poucos primos, eles explodem.

Caso I: o conjunto {p_1,p_2,...} de todos os primos que aparecem em
todas as fatorações de a_n é infinito. Neste caso, o problema acaba
antes mesmo de começar.

Caso II: o conjunto {p_1,p_2,...,p_k} de todos os primos que aparecem
em todas as fatorações de a_n é finito. Vamos trabalhar apenas com
esses primos, a não ser que seja dito algo contrário.

Assim sendo, podemos fatorar cada a_n da seguinte forma:

a_n = p_1^(e(1,n)) * p_2^(e(2,n)) * p_3^(e(3,n)) * ... * p_k^(e(k,n))

A cada a_n, vamos associar a maior dessas potências. Por exemplo, 72 =
2^3 * 3^2 estaria associada a 3^2, pois 3^2 = 9 > 8 = 2^3.

LEMA: Seja M_n = MDC(a*2017^n, b*2016^n). Então M_n é limitada.

De fato, se tentarmos fatorar, os fatores de 2017 não aparecem em 2016
e vice-versa, dado serem primos entre si. Logo os fatores de 2017 só
podem aparecer em b, e os fatores de 2016 só podem aparecer em a.
Portanto, M_n = MDC(a,2016^n) * MDC(b,2017^n) | ab, logo, limitado.

Vamos dividir nossa sequência em fitas de tamanho (K+1):

a_(0*k+0), a_(0*k+1),...,a_(0*k+k)
a_(1*k+0), a_(1*k+1),...,a_(1*k+k)
a_(2*k+0), a_(2*k+1),...,a_(2*k+k)
a_(3*k+0), a_(3*k+1),...,a_(3*k+k)
a_(4*k+0), a_(4*k+1),...,a_(4*k+k)
a_(5*k+0), a_(5*k+1),...,a_(5*k+k)
... ... ...

Se aplicarmos o princípio das gavetas em cada fita separadamente,
podemos dizer que para cada fita existe um primo tal que potências
desse primo aparecem (pelo menos) duas vezes entre os associados.
Vamos então anotar este primo para cada faixa:

a_(0*k+0), a_(0*k+1),...,a_(0*k+k)
a_(1*k+0), a_(1*k+1),...,a_(1*k+k)
a_(2*k+0), a_(2*k+1),...,a_(2*k+k)
a_(3*k+0), a_(3*k+1),...,a_(3*k+k)
a_(4*k+0), a_(4*k+1),...,a_(4*k+k)
a_(5*k+0), a_(5*k+1),...,a_(5*k+k)


Como o número de faixas é infinito e o número de possíveis primos
associados é finito, então existe um primo tal que infinitas faixas
tenham potências desse mesmo primo associadas.

Com esse raciocínio, nós demonstramos que existe uma sub-sequência de
a, chamemos ela de A, tal que todas as potências associadas a A são
potências de um mesmo primo p. Além disso, a distância entre os A
consecutivos na sequência original a é no máximo 2(k+1), afinal o pior
que pode acontecer é que pegamos dois índices que ficavam em extremos
opostos de faixas distintas.

Pois bem, peguemos dos A_t consecutivos, a saber, a_t, e a_(t+v).
Podemos dizer que existe um u máximo tal que p^u | a_t e p^u |
a_(t+v). Logo,

p^u | a_(t+v) - 2017^v * a_t = b * 2016^t * (2017^v-2016^v) | M_t *
(2017^v-2016^v)

Mas isto implica p^u <= M_t * (2017^v-2016^v) <= ab *
(2017^(2k+2)-2016^(2k+2)), ou seja, p^u é limitado.

Porém, a_t = p_1^(e(1,t)) * p_2^(e(2,t)) * p_3^(e(3,t)) * ... *
p_k^(e(k,t)) <= p^u * p^u * p^u * ... * p^u = (p^u)^k, o que implica
que (p^u) é ilimitado (pois a_t é ilimitado).

E isto é um absurdo! Logo, o nosso caso II não se sustenta - e ficamos
com o caso I apenas!

>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.

Já que você diz...

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.


=
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=