[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Re: AJUDA produtório
Ola Andre e demais colegas
desta lista ... OBM-L,
Tudo Legal ? Estou tomando a liberdade de remeter esta resposta tambem para
a lista OBM-L, pois o problema tambem pode ser do interesse de outras
pessoas.
Eu nao conhece o problema a que voce se refere, citado pelo Prof da UFF. O
problema que o Frederico me propos era o seguinte :
Considere N inteiros I1, I2, I3, ..., In tais que Ii < Ij sempre
i < j e seja "P" o produto de todas as diferencas da forma (Ij - Ii)
nas quais i < j. Caracterize o maior natural "D" que sempre dividira "P",
Quais quer que sejam os Ii's escolhidos.
A IDEIA DA SOLUCAO : Descobrir a decomposicao de "D" em fatores primos. Vou
fazer alguns casos para voce assimilar o raciocinio. Depois passo a
generalizacao.
FATOR PRIMO 2 :
Cada um dos Ii ou e congruo a 0 ou e congruo a 1 modulo 2, Isto e,
ou Ii==0(mod2) ou Ii==1(mod2), . Segue que os conjuntos :
C0 = {conjunto dos Ii tais que Ii==0(mod2) }
C1 = {conjunto dos Ii tais que Ii==1(mod2) }
Estao bem definidos e sao, evidentemente, disjuntos, pois um inteiro
qualquer nao pode ser, simultanemanete, congruo a 0 e a 1. Mais ainda, os
conjuntos C0 e C1 constituem uma particao de {I1, I2, ...,In}, pois :
Co intersecao C1 = vazio
C0 uniao C1 = { I1, I2, ..., In }
Portanto, se chamarmos o numero de elementos de C0 e C1, respectivamente, de
E0 e E1, teremos :
E0 + E1 = numero de elementos de {I1, I2, ...,In}
E0 + E1 = N
Agora, pense assim : Uma diferenca qualquer entre dois inteiros de
{I1,I2,...,In} so pode ser uma diferenca ENTRE DOIS INTEIROS DE C0, ENTRE
DOIS INTEIROS DE C1 ou ENTRE UM INTEIROS DE C0 E UM INTEIRO DE C1.
Nos dois primeiros casos o resultado sera um multiplo de 2, no terceiro caso
nao. Segue que haverao tantas diferencas mutiplos de 2 quanto forem a soma
das diferencas que se poderao fazer SOMENTE COM ELEMENTOS DE C0 e SOMENTE
COM ELEMENTOS DE C1.
1) Pelo que vimos, C0 tem E0 elementos. Segue que BINOM(E0,2) e o total de
diferencas que se pode fazer com os seus elementos de C0 e que atendem as
condicoes do problema.
2) Igualmente, C1 tem E1 elementos. Segue que BINOM(E1,2) e o total de
diferencas que se pode fazer com os seus elementos de C1 e que atendem as
condicoes do problema.
Portanto,
S = BINOM(E0,2)+ BINOM(E1,2)
e o total de diferencas MULTIPLO DE 2 que sao geradas quando, ao
escolhermos os inteiros I1, I2, ..., In "E0" desses inteiros forem congruos
a o modulo 2 e "E1" deles for congruo a 1 modulo 2.
Bom, ate aqui acho que esta bem claro. Acho mesmo que fui prolixo. Mas,
vamos la.
Nos nao sabemos como sera a escolha dos Ii ... Alguem pode escolher de forma
que E0=0 e E1=N, ou E0=1 e E1=N-1, ..., ou E0=N e E1=0. Todavia, independe
da forma como a pessoa escolher os Ii, a formula "S" acima dara o numero de
fatores 2 que, com certeza, ira parecer ... Portanto, se tomarmos o MINIMO
QUE AQUELA EXPRESSAO ASSUME quando E0 e E1 assumem todos os valores
possiveis - de (E0,E1)=(N,0) ate (E0,E1)=(0,N)-NAO DEPENDEREMOS MAIS DA
ESCOLHA DOS Ii's.
Deve ter ficado claro, agora, que :
S2 = MIN {BINOM(E0,2)+ BINOM(E1,2), E0+E1=N }
E a MAIOR POTENCIA de 2 que SEMPRE DIVIDIRA "P", QUAISQUER QUE SEJAM OS N
INTEIROS I1, I2, ..., In ESCOLHIDOS ( Ii < Ij se i < j )
FATOR PRIMO 3 :
Voce aqui e identico ...
Cada um dos Ii ou e congruo a 0 ou e congruo a 1 ou e congruo a 2 modulo 3,
Isto e, ou Ii==0(mod3) ou Ii==1(mod3) ou Ii==1(mod3) . Segue que os
conjuntos :
C0 = {conjunto dos Ii tais que Ii==0(mod3) }
C1 = {conjunto dos Ii tais que Ii==1(mod3) }
C2 = {conjunto dos Ii tais que Ii==2(mod3) }
Estao bem definidos e sao, evidentemente, disjuntos, pois um inteiro
qualquer nao pode ser, simultanemanete, pertencer a dois ou mais dos
conjuntos acima. Mais ainda, os conjuntos C0, C1 e C2 constituem uma
particao de
{ I1, I2, I3 ..., In }, pois :
Ci intersecao Cj = vazio, para quaisquer i ,j em { 0.1.2 } com i # j
C0 uniao C1 uniao C2 = { I1, I2, I3 ..., In }
Portanto, se chamarmos o numero de elementos de C0, C1 e C2 ,
respectivamente, de E0, E1 e E2, teremos :
E0 + E1+E2 = numero de elementos de {I1, I2, ...,In}
E0 + E1+ E2 = N
E0, E1, E2 inteiros nao-negativos
Agora, basta re-pensar assim : Uma diferenca qualquer entre dois inteiros de
{I1,I2,...,In} so pode ser uma diferenca ENTRE DOIS INTEIROS DE C0, ENTRE
DOIS INTEIROS DE C1 ou ENTRE DOIS INTEIROS DE C2 OU ENTRE UM INTEIROS DE Ci
E UM INTEIRO DE Cj com I # J e I, J em {0,1,2}
Nos tres primeiros casos o resultado sera um multiplo de 3, nos demais casos
nao. Segue que haverao tantas diferencas mutiplos de 3 quanto forem a soma
das diferencas que se poderao fazer SOMENTE COM ELEMENTOS DE C0 e SOMENTE
COM ELEMENTOS DE C1 e SOMENTE COM OS ELEMENTOS DE C2.
1) Pelo que vimos, C0 tem E0 elementos. Segue que BINOM(E0,2) e o total de
diferencas que se pode fazer com os seus elementos de C0 e que atendem as
condicoes do problema.
2) Igualmente, C1 tem E1 elementos. Segue que BINOM(E1,2) e o total de
diferencas que se pode fazer com os seus elementos de C1 e que atendem as
condicoes do problema.
3) Igualmente, C2 tem E2 elementos. Segue que BINOM(E2,2) e o total de
diferencas que se pode fazer com os seus elementos de C2 e que atendem as
condicoes do problema.
Portanto,
S = BINOM(E0,2)+ BINOM(E1,2) + BINOM(E2,2)
e o total de diferencas MULTIPLO DE 3 que sao geradas quando, ao
escolhermos os inteiros I1, I2, ..., In, "E0" desses inteiros forem
congruos a ZERO modulo 3 e "E1" deles for congruo a 1 modulo 3 e "E2" forem
congruos a 2 modulo 3. .
Bom, ate aqui acho que esta bem claro. Acho mesmo que fui prolixo. Mas,
vamos la.
Nos nao sabemos como sera a escolha dos Ii ... Alguem pode escolher de forma
que E0=0 e E1=0 e E2=N, ou E0=0 e E1=1 e E2=N-1, ..., ou E0=N e E1=0 e E2=0.
Todavia, independe da forma como a pessoa escolher os Ii, a formula "S"
acima dara o numero de fatores 3 que, com certeza, ira parecer ... Portanto,
se tomarmos o MINIMO QUE AQUELA EXPRESSAO ASSUME quando E0, E1 e E2
assumem todos os valores possiveis - de (E0,E1,E2)=(0,0,N ) ate
(E0,E1,E2)=(N,0,0)-NAO DEPENDEREMOS MAIS DA ESCOLHA DOS Ii's.
Deve ter ficado claro, agora, que :
S3 = MIN {BINOM(E0,2)+ BINOM(E1,2)+BINOM(e2,2), E0+E1+E2=N }
E a MAIOR POTENCIA de 3 que SEMPRE DIVIDIRA "P", QUAISQUER QUE SEJAM OS N
INTEIROS I1, I2, ..., In ESCOLHIDOS ( Ii < Ij se i < j )
O MAIOR FATOR PRIMO A SE CONSIDERAR
Para ver qual o maior fator primo a ser considerado, quando escolhemos N
inteiros, basta notar que para cada primo Q precisamos determinar o minimo
de uma expressao
S=BINOM(E0,2) + BINOM(E1,2) + ... + BINOM(Eq-1,2)
com "Q" parcelas ( de E0 ate Eq-1 ) e sendo E0+E1+...+Eq-1=N. Se Q >= N a
equacao E0+E1+...+Eq-1=N admitira uma solucao na qual Ei=0 ou Ei=1 para
qualquer i em {0, 1, ... ,q-1 }, ou seja,
S=BINOM(E0,2) + BINOM(E1,2) + ... + BINOM(Eq-1,2)
admitira o minimo ZERO e, portanto, havera uma escolha dos Ii em que nao
surgira um fator primo Q. Daqui segue necessariamente que o ultimo fator
primo que precisamos considerar e O MAIOR PRIMO MENOR QUE "N", pois, neste
caso, precisaremos distribuir N em Q parcelas e como N > Q havera ao menos
uma parcela >= 2 e o minimo de S sera, pelo menos, 1.
Seja portanto "Q" o ultimo primo considerado. O valor de "D" que procuramos
sera :
D=(2^S2)*(3^S3)*(5^S5)*(7^S7)*...*(Q^Sq)
Esse e O MAIOR NUMERO NATURAL "D" QUE SEMPRE DIVIDIRA "P" INDEPENDE DA
ESCOLHA DOS Ii's
Bom, eu vou ficar por aqui ... Antes, porem, algumas observacoes :
1) Voce vai precisar determinar os minimos das funcoes S descritas acima.
Esse problema tem o merito de trazer a cena esta funcoes, muito uteis em
outras circunstancias. Mas isso fica pra voce. Todavia, vou dizer : O
demonio de Socrates esta soprando em minha orelha que o minimo ocorre quando
a distribuicao de N nas parcelas Ei e a mais uniforme possivel ... Ou seja,
se sao "Q" parcelas, coloque a parte inteira de N/Q em cada parcela e
distribua o RESTO de N/Q acrescentando UMA UNIDADE no maior numero possivel
de parcelas.
3) Novidade e Flexibilidade com numeros binomiais voce vai encontrar na
MATEMATICA QUANTICA. Eu sinto que esta e uma interpretacao poderosa, que
nos permitira compreender e manifestar fenomenos matematicos que ainda nao
conseguimos explicar ou sequer perceber... O Livro do Prof Nicolau sobre
esse tema esta disponivel e voce pode le-lo em :
http://www.mat.puc-rio.br/~nicolau/publ/publ.html
clicar em TOPICOS DE MATEMATICA QUANTICA
3)Voce pode publicar suas conjecturas aqui, nesta lista. E obrigado pelos
elogios.
Com os melhores votos
de paz profunda, sou
Paulo Santa Rita
3,1458,101202
>From: André Silva <matemandreca@ig.com.br>
>To: "Paulo Santa Rita" <p_ssr@hotmail.com>
>Subject: AJUDA produtório
>Date: Tue, 10 Dec 2002 11:43:10 -0200
>
>Caro Paulo,
> é sempre um prazer, ver suas contribuiçòes à lista. Não sou assíduo,
>mas sempre que posso acompanho a movimentação e invariavelmente sua
>presença é sempre muito esclarecedora. Não lhe escrevo só para elogiá-lo.
>Recentemente escreveu ao Frederico Gomes indicando a solução de um problema
>que não tive acesso ao enunciado. Nela, se não estou delirando - isto é
>comum :) - há um "esboço" de como calcularmos o menor expoente de um primo
>que divide o produto de n inteiros. Se é realmente por aí, gostaria que
>voce, se puder, me enviasse com mais detalhes o problema e sua solução. O
>fato é que um professor da UFF me disse a uns seis meses atrás que ninguém
>havia provado que entre dois quadrados há sempre um inteiro primo. Pensando
>sobre este problema esbarrei no cálculo do expoente de um primo, tal que
>este divide o produto de n inteiros. Desde já agradeço por sua atenção.
> Paulo, gostaria de saber se realmente este problema está em aberto,
>ou se pelo menos estava até vc pensar nele!?!
>
>Abraços,
>André Silva (RJ)
_________________________________________________________________
MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================